憂鬱な午後のひととき


4月25日_
『カブキの日』(小林恭二)
能や狂言は大学のときにそこそこ見てたけど歌舞伎は見たことが無い. ので細かいところはどこまでほんとの話か判断つかないけど, 普通の世界から徐々に魑魅魍魎の世界に移る後半のはちゃめちゃさは森見登美彦っぽくてすがすがしい(って『カブキの日』は10年以上前の本だが).
4月23日_

mfence vs. lockプレフィックス

前回の続き. 3番目の例が実際に起こることを見てみよう.

  mov(ptr [eax + offset_A], 1);
  ; --*
  mov(edx, ptr [eax + offset_B]);
  mov(ptr [eax + offset_r1], edx);
  mov(ptr [eax + offset_B], 1);
  ; --*
  mov(edx, ptr [eax + offset_A]);
  mov(ptr [eax + offset_r2], edx);

この二つのコードを別々のスレッドで走らせて(r1, r2)の結果を収集する. コードはfence.cpp

C++11のthreadを使ってるのでgcc 4.5やVC2011で試す.

g++ -O3 -fno-operator-names -fomit-frame-pointer -lpthread -std=c++0x fence.cpp

実行すると

mode:  none num=  754907  4086050  5158292      751 clk=124.126Mclk
mode:mfence num=       0        0 10000000        0 clk=619.118Mclk
mode:  lock num=       0  9959040    26074    14886 clk=417.443Mclk

の様に表示される. mode:noneのときは順序制御をしていないとき. num=のあとの4つの数字は 順に(r1, r2) = (0, 0), (1, 0), (0, 1), (1, 1)が発生した回数を示す. (0, 0)の状態が何度か発生していることが分かる.

mode:mfenceやmode:lockは上のコードの(*)の部分にそれらのコードを挿入したときのパターンをしめす. こちらは(0, 0)の状態が発生していない.

さてg++ 4.7.0はstd::atomic<int> a; a.store(1, std::memory_order_seq_cst);や__sync_synchronize()の生成コードにmfenceを使う. ところがi_saintさんに教えていただいたのだが, VCのMemoryBarrierはlock命令(64bit)やxchg命令(32bit)を使う[MemoryBarrier].

MemoryBarrierの実体である__faststorefenceには faster store fence than the sfence とあるので試してみたのが上のlockである.

// 32bit
mov(ebx, 1);
xchg(ptr [eax + offset_A], ebx);

// 64bit
mov(ptr [eax + offset_A], 1);
db(0xf0); or(dword [rsp], 0);

xchgはlockプレフィックス(0xf0)がなくてもlockがかかる. 64bitでは明示的に0xf0をつけた.

Intel 64 and IA-32 Architectures Software Developer's Manual Volum3 3[March 2012] の8.2.3.9 Loads and Stores Are Not Reordered with Locked Instructionsによるとこれで正しく順序が保たれるはず.

まあいい加減なベンチマークなのでどれだけ当てになるのかわからないけど, いくつかの環境で試すと

lock benchmark [Mclk]
i7-2600K(64bit) 32bit Xeon X5650(64bit) 32bit Core2Duo(64bit) 32bit
none 61 62 62 123 161 304
mfence 431 654 654 618 312 266
lock/xchg 221 272 272 405 419 439

となった. Core2Duoではmfenceの方が速いが, Sandy BridgeやWestmereではmfenceよりもlockやxchgの方が速かった.

4月21日_

Intel 64 and IA-32 Architectures Software Developer's Manual Volum3 3[March 2012]の 8.2.2 Memory Ordering in P6 and More Recent Processor Familiesから抜粋.

Core 2 Duo, Atom, Core Duo, Pentium 4, P6はprocessor-ordered memory-ordering modelを利用する. 1個の論理プロセッサでの順序の原理:

  1. readに続くread(これをR→Rと書くことにする)の順序は変わらない
  2. readに続くwriteの(R→W)の順序は変わらない
  3. 一部の命令を除いてW→Wの順序は変わらない
  4. 同じ場所へのW→Rの順序は変わらない
  5. 異なる場所へのW→Rの順序は変わるかもしれない
  6. W→sfence→Wの順序は変わらない
  7. R→lfence→R, Wの順序は変わらない
  8. R, W→mfence→R, Wの順序は変わらない

複数プロセッサでは

  1. 各プロセッサは1個のプロセッサの順序の原理に従う
  2. あるプロセッサの書き込みは他の全てのプロセッサにとって同じ順序で見える
  3. あるプロセッサの書き込みと別のプロセッサの書き込みの順序は保存されない

思っていたよりも順序に関して強いルールだった(大昔見たときと違うような気が*). それでいくつか具体例が書いてあって(これも大昔見たときは無かった気がする…)昨日の一つ目の例

A = B = 0
<プロセッサ0>   <プロセッサ1>
mov [A], 1       mov r1, [B]
mov [B], 1       mov r2, [A]

において(r1, r2) = (1, 0)は「起こらない」とあった. つまりB = 1になっていたらA = 1も保証される. よってここにlfenceは要らない.

(*)昔のマニュアルには「初期のPentium 4, XeonについてはR→Rは投機実行により任意の順序で実行される」とあった. その場合は(1, 0)が起こり得る. kosakiさんのページのコメント蘭にあるように昔は違ってたのか, マニュアルが間違ってたのかどうなんだろう.

次のような書き込みについても

A = B = 0
<プロセッサ0>   <プロセッサ1>
mov r1, [A]      mov r2, [B]
mov [B], 1       mov [A], 1

において(r1, r2) = (1, 1)は起こらない. ただ3番目の例の

A = B = 0
<プロセッサ0>   <プロセッサ1>
mov [A], 1      mov [B], 1
mov r1, [B]     mov r2, [A]

においては昨日書いていたように(r1, r2) = (0, 0)は起こり得るようだ. したがってそれを避けたいならきちんと順序づける方法をとらないといけない.

1個の論理プロセッサのルール3の「一部の命令を除いてW→Wの順序は変わらない」の 「一部の命令」としてはたとえばrep stosdがある. たとえば上の一つ目の例を次のように変更すると

int A[2] = {0, 0};
<プロセッサ0>   <プロセッサ1>
rep:stsdでAを    mov r1, A[1]
1で埋める        mov r2, A[0]

この場合は順序が入れ代わって(r1, r2) = (1, 0)というのは起こり得るようだ.

4月20日_

最小例で理解するfence命令

4/21追記:w_oさんにその例でlfenceやsfenceは不要と言われたので出直してきます. すいません. 以下は間違ってます. 21日の記事も参照.

(Intelのマニュアルから) > プログラム順序の中でLFENCE命令よりも前に実行されたすべてのLOAD命令は,LFENCEの後に実行されるLOAD命令よりも先に読み出しを行うことを確実にする …って言われてもすぐには分からない. 単純な例で理解しよう.

メモリA, Bが0の状態からA = 1, B = 1の順序で変わったとする. そのとき別のスレッドでB, Aの値を観測しそれぞれr1, r2とする.

  load r1, ptr [B]
  load r2, ptr [A]

さて(r1, r2)の取り得るパターンはなんだろう.

Aが1に変わる前に2回続けて読んでいれば(r1, r2) = (0, 0). 二つのload命令の間でAが1に変われば(0, 1). A, Bが1に変わってから読んでいれば(1, 1). つまり(r1, r2) = (0, 0), (0, 1), (1, 1)の3通り.

(r1, r2) = (1, 0)は起こり得ない. ところが, この常識的な答えはCPUが一つしか無かった時代のものでCPUが複数あると崩壊する. (1, 0)がありえるのだ.

「そんなおかしなことがあっては困る」という人のために導入されたのがlfence命令だ. これはこの命令の前後のload命令の順序を保証する.

  load r1, ptr [B]
  lfence
  load r2, ptr [A]

このコードでは安心して(r1, r2) = (1, 0)が起こらないと言える.

同様のことが書き込みに対しても発生する. A = B = 0とする.

  store ptr [A], 1
  store ptr [B], 1

というコードを実行したとする. そのとき別スレッドでB, Aの値をこの順序で読んだとしよう. それを(r1, r2)とする. CPUが一つしかない場合は(r1, r2) = (0, 0), (0, 1), (1, 1)の3通りしかない. しかし複数CPUの場合は(r1, r2) = (1, 0)が起こり得る.

「そんなことがあっては困る」という場合にはsfenceを挟むと書き込み順序が保存される.

  store ptr [A], 1
  sfence
  store ptr [B], 1

こうすると(r1, r2) = (0, 1)は起こらない. もう少し複雑なケースを考えてみよう. A = B = 0とする. 互いに値を設定しつつ別の値を読む.

  スレッド1     スレッド2
  [A] ← 1      [B] ← 1
  r1 ← [B]     r2 ← [A]

この場合, (r1, r2)の取り得るパターンは何だろう. スレッド1が先に走るとr1 = 0で, スレッド2ではr2 = 1. つまり(r1, r2) = (0, 1). 逆にスレッド2が先に走れば(1, 0). まざって走ると(1, 1).

だが流石に(0, 0)はなさげ.

しかし今までの流れからすると想像できるように複数CPUではやっぱり(0, 0)も起こり得る. これを防ぐにはlfenceとsfenceを挟めばよいのだろうか.

  スレッド1      スレッド2
  [A] ← 1      [B] ← 1
  lfence        lfence
  sfence        sfence
  r1 ← [B]     r2 ← [A]

実はこれでは駄目なのだ. lfenceはあくまでそれを挟むloadの順序を保証する, sfenceはそれを挟むwriteの順序を保証するだけの命令. loadとstoreの順序は保証しない(r2 ← [A]がするっと上に行って[B] ← 1の前に処理されうる).

「それでは困る」という人のためにmfenceがある. これを挟めば(0, 0)は起こらない.

  スレッド1      スレッド2
  [A] ← 1      [B] ← 1
  mfence        mfence
  r1 ← [B]     r2 ← [A]

まとめるとlfenceはloadの順序を保証する. sfenceはstoreの順序を保証する. loadとstoreの順序を保証したければmfence. lfence + sfenceでは代用できない.

4月13日_

gccのlikely, unlikelyマクロは役に立つのか ~x86/x64最適化勉強会3の分岐予測番外編~

まず過去の話をしよう. 朧げな記憶によると386だったか486では条件分岐は分岐しなければ1clk, 分岐すれば3clkという感じで分岐するコストが高かった. そういうCPUでは分岐の条件が成立する確率が高い方を"分岐しない"ようにコードを記述するのが効率がよい.

そうすると事前にその分岐が起こりやすいかそうでないかをコンパイラに教えるとよいだろうという発想になる. それがgccの__builtin_expectだ. たとえばLinux カーネルのなかに入り込む GCCの分岐予測のヒント.

しかし最近のx86/x64 CPUは分岐予測が当たりさえすれば分岐しようがしまいが関係ないとされる. じゃあ__builtin_expectは無意味なんじゃなかろうか. 確認してみよう. まず「分岐しようがしまいが関係ない」を調べてみる.

  // eax : 0 or 1
  // ecx : counter
L(".lp");
    test(eax, eax);
    jz(".jmp");
L(".jmp");
    sub(ecx, 1);
    jnz(".lp");

というコードの実行時間をeax = 0と1とで測って比較する. 試したCPUはPentium D, Core Duo, Xeon X5650, i7 2600K(コードはjmp.cpp).

結果, どのCPUでも同一の時間であった. つまり上記jzでジャンプする場合としない場合とで実行時間に差はなかった. 古いCPUとは前提条件が違うことが分かる.

次に__builtin_expectを調べよう. 以下のコードをgcc 4.6.1コンパイルしてみた.

int g1(int a, int b)
{
    /* a > bを期待する */
    if (__builtin_expect(a > b, 1)) {
        return a + 1;
    }
    return a + 2;
}

int g2(int a, int b)
{
    /* a <= bを期待する */
    if (__builtin_expect(a > b, 0)) {
        return a + 1;
    }
    return a + 2;
}

生成されたコードは次の通り

g1:
    cmp     edi, esi
    jle     .L2          ; if (a <= b) then goto L2
    lea     eax, [rdi+1]
    ret
.L2:
    lea     eax, [rdi+2]
    ret

g2:
    cmp     edi, esi
    jg      .L8          ; if (a > b) then goto L8
    lea     eax, [rdi+2]
    ret
.L8:
    lea     eax, [rdi+1]
    ret

おお, 確かにg1()ではa <= bのとき, g2()ではa > bのときジャンプするようにコードが生成されている.

ではこれに(a, b) = (1, 0)と(0, 1)とを与えたときの時間を測ってみよう(先程のjmp.cppのExpectCodeの部分).

jmp timing [clk]
Pen D CoreDuo Xeon Sandy
g1(1,0) 12.235 8.047 6.096 5.391
g1(0,1) 12.352 9.099 7.833 7.247
g2(1,0) 12.589 9.084 7.850 7.238
g2(0,1) 12.352 8.084 6.091 5.384

ありゃ, 結果はやや予想外. 一つ目の実験と違ってPentium Dを除いてg1(1, 0)とg2(0, 1)のジャンプしないコードの方がやや速いやんか(1clk程度の誤差が出るのであくまで目安).

ということはこのケースでは__builtin_expectは意味があることになる.

「なんだ, 今でも意味があるのか(ちょっとがっかり)」と思ったのだが, ちょっと待った. こういう場合って普通はcmov命令を使わへんのか. 試しに__builtin_expectをどけてみた.

int g3_C(int a, int b)
{
    if (a > b) {
        return a + 1;
    }
    return a + 2;
}

これは次のコードを生成した.

    lea     eax, [rdi+1]
    cmp     edi, esi
    lea     edx, [rdi+2]
    cmovle  eax, edx
    ret

ちゃんとcmov命令が使われている. ベンチマークを取る.

jmp with cmov timing [clk]
Pen D CoreDuo Xeon Sandy
g3_C(1,0) 11.705 8.097 6.096 5.403
g3_C(0,1) 11.934 8.088 6.091 5.426

なんと, __builtin_expectをつけない方が速い(か同じ). ちなみに上のコードについては私ならこう書くかも. 命令数も少ないしね.

    cmp(p2, p1);
    sbb(a, a); // a = p2 < p1 ? -1 : 0
    lea(a, ptr [p1 + 2 + a]);
    ret();

Sandy Bridgeではこちらのほうが気持ち速いようだ.

さて, 予め分岐を予想できそうなときのjmpとcmovと言えば, 以前条件分岐を減らした方がよいのかという話をした.

ざっくり言うと与えられた配列の最大値を求めるような関数では, 入力が一様乱数と仮定すると最大値の更新が起きない確率が高いのでcmovよりもjmpを使えという話. つまり通常の最適化ではcmovが使われてしまう

int max1(const int *x, size_t n)
{
    int ret = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] > ret) ret = x[i];
    }
    return ret;
}

int max2(const int *x, size_t n)
{
    int ret = x[0];
    for (int i = 1; i < n; i++) {
        if (__builtin_expect(x[i] > ret, 0)) ret = x[i];
    }
    return ret;
}

と書くとjmpが使われて速くなる…と思いきや, max1とmax2で生成されたコードは同じ. なぜだろう.

__builtin_expectは単に古いCPUのためにどちらをjmpするかを切り替えるだけで, 最近のCPUの「予測が当たれば速い」ことは考慮されていないということか(憶測). 結局, max2が期待通りになってくれるならともかくx86/x64にとっては__builtin_expectはいらないんじゃないかと.

4月12日_

str_util.hppにmie::strcasestr(text, key)とmie::findCaseStr(begin, end, key, keySize)を追加.

これらは大文字小文字を無視してtextまたは[begin, end)からkeyを探す. ここで大文字小文字と言ってるのはASCIIコードの[A-Z]と[a-z]のこと. 他の文字は関知しない. またkeyは予め小文字にしておくこと.

mie::strcasestrはgcc拡張のstrcasestr相当のやつ. VCには無いのかな. mie::findCaseStrは'\0'文字が入ってもよいバージョン.

mie::strcasestrはgccのSSE4.2を使うstrcasestrに比べて3倍ぐらい速い. findCaseStrは比較しやすい関数が思いつかなかったけどCで普通に書いたやつに比べたら10倍は速いだろう.

以下少しだけfindStrとfindCaseStrの差分についてコード解説.

/*
    Am1 : 'A' - 1
    Zp1 : 'Z' + 1
    amA : 'a' - 'A'
    t : temporary register
*/
void setLowerReg(const Xbyak::Xmm& Am1, const Xbyak::Xmm& Zp1
    , const Xbyak::Xmm& amA, const Xbyak::Reg32& t)
{
    mov(t, 0x40404040);
    movd(Am1, t);
    pshufd(Am1, Am1, 0); // 'A' - 1
    mov(t, 0x5b5b5b5b);
    movd(Zp1, t);
    pshufd(Zp1, Zp1, 0); // 'Z' + 1
    mov(t, 0x20202020);
    movd(amA, t);
    pshufd(amA, amA, 0); // 'a' - 'A'
}

関数の最初にXMMMレジスタAm1, Zp1, amAをそれぞれbyte単位で'A' - 1, 'Z' + 1, 'a' - 'A'という数値で初期化する. 下位32bitに値を入れてからpshufdで128bitに拡散.

/*
    toLower in x
    Am1 : 'A' - 1
    Zp1 : 'Z' + 1
    amA : 'a' - 'A'
    t0, t1 : temporary register
*/
void toLower(const Xbyak::Xmm& x, const Xbyak::Xmm& Am1
    , const Xbyak::Xmm& Zp1, const Xbyak::Xmm& amA
    , const Xbyak::Xmm& t0, const Xbyak::Xmm& t1)
{
    movdqa(t0, x);
    pcmpgtb(t0, Am1); // -1 if c > 'A' - 1
    movdqa(t1, Zp1);
    pcmpgtb(t1, x); // -1 if 'Z' + 1 > c
    pand(t0, t1); // -1 if [A-Z]
    pand(t0, amA); // 0x20 if c in [A-Z]
    paddb(x, t0); // [A-Z] -> [a-z]
}

textから16byte読み込んだ値がxに入っている. それに対してbyte単位で 'A' - 1 < x && x < 'Z' + 1に入っているときのみ'a' - 'A'を足す. pcmpgtb X, Yはbyte単位での数値の比較を行いX > YならX = 0xff, そうでなければX = 0にする命令.

この命令により16byte単位で高速に大文字を小文字に変換できる.

if (caseInsensitive) {
    movdqu(xm1, ptr [p]);
    toLower(xm1, Am1, Zp1, amA, t0, t1);
    pcmpestri(xm0, xm1, 12);
} else {
    pcmpestri(xm0, ptr [p], 12);
}

caseInsensitiveがtrueのときはtextの現在のポインタpからxm1に16byte読み込んでからtoLowerで小文字に変換して pcmpestriを実行する. falseの場合は従来通り直接pcmpestriを実行する.

そんな感じ. keyを小文字化しておく仮定にしたのはkeyの小文字かは一度だけやっておけばよいからユーザに任せた.

あと64bit VCでは関数の中でxmm6は変更してはいけないので関数の先頭と最後で退避と復元をしている. 64bit VCで関数が呼ばれた直後のrspはmod 16で + 8なのでrsp + 8は16byte境界にある.

#elif defined(XBYAK64_WIN)
    movdqa(xm6, ptr [rsp + 8]);
#endif
4月11日_

先月末にあったx86/x64最適化勉強会3の@takehiro_tさんの条件分岐の講演の中で

int c_old(unsigned int k)
{
  if (k < 2) return 3;
  if (k == 2) return 6;
  return 100;
}

int c_new(unsigned int k)
{
  if (k == 2) return 6;
  if (k == 3) return 100;
  return 3;
}

のc_oldとc_newのどちらが速いかという話があった(kは0, 1, 2, 3のから一様ランダムに選ばれる).

c_oldが速いCPUがなかなか見つからないとのことだったので実家から持ってきていたFM-TOWNS HC改(CPU:K6-III)で試してみた(t.c, f.asm). 最初電源が入らなくて焦ったのだけど(ちょっと前は動いてた), しばらく叩いてると動くようになったw

ただNICがどうも認識しない. ネットワークにつなげないとWindows側と共有できるメディアが無いのでファイルのコピーができない. 仕方がないので別のモニタにコードを表示して手でコピー.

さて, Cはいいけど386asmの擬似命令を忘れていてしばし四苦八苦. 昔のソースを見ながらなんとか無事buildできて動かすとc_oldがc_newよりも速いことが確認できた. めでたしめでたし.

ちなみにasm版は後者が速かったのだけどなんでかな. K6-IIIってjmpが続くとだめなんだっけ.

まあ, そんなことはおいといて, 急に昔にひたりたくなって『雷電』を出してきて遊んだ. しかしどうも3面のボスを倒せない. しばらくトライしていたが親指が痛くなったので諦める.

しかしCD-ROMドライブが正常なTOWNSって貴重なんだろうな. いつまで動いてるのだろう.

4月10日_
スーパーでめかじきのあらを200円で買って適当に塩と胡椒とバターで焼いて食べたらめっちゃおいしかった. コストパフォーマンスがいい.
4月9日_
昨日見た他人のコード
Fp P[n][2];
for (int i = 0; i < n; i++) P[n][2] = P[n][1];
一つのバグに取られてもう一つを見逃して30分以上無駄にした. まだまだコードレビュー力が足りない.
4月4日_

x86/x64最適化勉強会3に青木和麻呂さんの資料へのリンクを追加. これで全員の分が揃いました. みなさんご提供ありがとうございました.

ところで資料を見た海外の人から「私のblogに書いてあるstrstrの実装と比較してくれ」というメールが来た. 試してみるとtypoなどがあって修正しないとコンパイルできないし, コンパイルできてもバグがあったりと品質が?なんだが, 積極的だな.

日本ではtwitterでのその場のリアルタイムな反応(つまりは殆ど感情表現)はあっても, そういう議論につながるレスポンスはなかなか見られない. 残念.

4月3日_
『飛べ!「はやぶさ」小惑星探査機60億キロ奇跡の大冒険』(松浦晋也)
小学生向けの本でとても分かりやすい. 最初の章のコンパスを使って円を書いて太陽系の大きさをを実感するところは実感がわきやすい.
クライマックスのトラブル続きの中なんとか戻ってこれたところは改めて感心する.
4月2日_
Japanist 2003 アップデート 本体
>Windows 7(64ビット) に対応しました。
富士通すげー. 64bit版の体験版が3/31に切れたのでどうしようかと思ってたらなんと3/30にupdateされていた(1カ月ぐらい前に見たときは何も書いてなかったのに). 9年以上も前の製品がちゃんとメンテナンスされるところに感動する.

御意見は光成滋生<herumi@nifty.com>までお願いします