『カブキの日』(小林恭二)
能や狂言は大学のときにそこそこ見てたけど歌舞伎は見たことが無い.
ので細かいところはどこまでほんとの話か判断つかないけど,
普通の世界から徐々に魑魅魍魎の世界に移る後半のはちゃめちゃさは森見登美彦っぽくてすがすがしい(って『カブキの日』は10年以上前の本だが).
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によるとこれで正しく順序が保たれるはず.
まあいい加減なベンチマークなのでどれだけ当てになるのかわからないけど, いくつかの環境で試すと
| 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の方が速かった.
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個の論理プロセッサでの順序の原理:
複数プロセッサでは
思っていたよりも順序に関して強いルールだった(大昔見たときと違うような気が*). それでいくつか具体例が書いてあって(これも大昔見たときは無かった気がする…)昨日の一つ目の例
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)というのは起こり得るようだ.
最小例で理解する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では代用できない.
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の部分).
| 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命令が使われている. ベンチマークを取る.
| 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はいらないんじゃないかと.
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
先月末にあった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って貴重なんだろうな. いつまで動いてるのだろう.
Fp P[n][2]; for (int i = 0; i < n; i++) P[n][2] = P[n][1];一つのバグに取られてもう一つを見逃して30分以上無駄にした. まだまだコードレビュー力が足りない.
x86/x64最適化勉強会3に青木和麻呂さんの資料へのリンクを追加. これで全員の分が揃いました. みなさんご提供ありがとうございました.
ところで資料を見た海外の人から「私のblogに書いてあるstrstrの実装と比較してくれ」というメールが来た. 試してみるとtypoなどがあって修正しないとコンパイルできないし, コンパイルできてもバグがあったりと品質が?なんだが, 積極的だな.
日本ではtwitterでのその場のリアルタイムな反応(つまりは殆ど感情表現)はあっても, そういう議論につながるレスポンスはなかなか見られない. 残念.