intrinsic version of strlenSSE42を加筆.
pcmpestriなどは戻り値がecxとフラグの両方なのでintrinsicだと無駄が出るんだろうなと思ってたらちゃんと作られていたという話.
ところで_mm_cmpestrcがCFで*stroがOF, *strsがSFで*strzがZFなら*straはAFと思うだろう. 普通.
SSE4.2文字列処理命令のページを書いた.
もうSSE4.2が使えるCPUは大分旧世代で本当に今更なのだけど, きちんとマニュアルを読んだこと無かったので今回理解しようとした. 想像していた以上に複雑で驚いた.
よくもまあ, こんな複雑な命令を高速に処理させることができるものだ. 流石CISCの権化である.
簡単なベンチマークを取ってみた(strlen_sse42.cpp). 対象はXeron X5560とcore i7-2600. プログラムはWindows/Linux両対応(Macでも動くかな).
strlenLIBCはコンパイラ標準のstrlen, strlenCはナイーブなCによる実装.
size_t strlenC(const char *p)
{
const char *top = p;
while (*p) {
p++;
}
return p - top;
}
strlenSSE2は昔作ったやつ(fast strlen and memchr by SSE2).
| ave | 1.98 | 4.96 | 6.76 | 9.75 | 11.60 | 15.23 | 18.86 | 28.65 | 51.63 | 84.67 | 127.23 | 175.75 | 197.63 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| strlenLIBC | 11.78 | 5.00 | 4.06 | 3.22 | 2.92 | 2.42 | 2.12 | 1.58 | 1.02 | 0.71 | 0.51 | 0.38 | 0.34 |
| strlenC | 14.06 | 8.40 | 6.96 | 5.59 | 4.95 | 4.26 | 3.83 | 3.27 | 2.71 | 2.46 | 2.31 | 2.19 | 2.19 |
| strlenSSE2 | 12.77 | 6.40 | 5.11 | 3.92 | 3.42 | 2.77 | 2.35 | 1.73 | 1.15 | 0.79 | 0.52 | 0.33 | 0.28 |
| strlenSSE42 | 9.26 | 3.98 | 3.23 | 2.70 | 2.50 | 2.24 | 2.03 | 1.59 | 1.01 | 0.69 | 0.51 | 0.35 | 0.31 |
| ave | 1.98 | 4.96 | 6.76 | 9.75 | 11.60 | 15.23 | 18.86 | 28.65 | 51.63 | 84.67 | 127.23 | 175.75 | 197.63 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| strlenLIBC | 11.68 | 5.67 | 4.60 | 3.61 | 3.11 | 2.54 | 2.14 | 1.43 | 0.72 | 0.46 | 0.36 | 0.30 | 0.30 |
| strlenC | 14.47 | 6.95 | 5.55 | 4.37 | 3.94 | 3.42 | 3.07 | 2.56 | 2.07 | 1.76 | 1.60 | 1.51 | 1.46 |
| strlenSSE2 | 12.30 | 5.74 | 4.58 | 3.42 | 2.97 | 2.35 | 1.92 | 1.26 | 0.71 | 0.40 | 0.30 | 0.24 | 0.23 |
| strlenSSE42 | 12.56 | 5.26 | 4.12 | 3.29 | 2.95 | 2.59 | 2.31 | 1.56 | 0.83 | 0.52 | 0.39 | 0.32 | 0.29 |
aveは平均の文字列長. 徐々に長くしている. 数値はbyteあたりに掛かったクロック数. 小さい方が速い.
条件が違うので直接比較はできないのだけど, 昔SSE2版を作った頃のgccのstrlenLIBCは大分遅かったが最近はかなりよくなってるようだ.
ただstrlenLIBCとstrlenCを比べるとstrlenLIBCは明らかに専用の最適化コードが入ってるので汎用的ではない.
文字列が長いときは, 今でもstrlenSSE2が速い. これはループアンロールして32byte単位でデータを取り込んでるからだろう.
strlenSSE42はXeon上では好成績. こんな単純なコードでこれほど速いなら使い勝手がよいかも. i7だとXeonほどでも無いけど悪くはない. ループアンロールも不要, アライメントを気にしなくてもよい, 昔のrep stringみたいに初期コストが高いわけでもなさそうだ.
というわけで, あの複雑怪奇な仕様さえクリアできれば大分よさそう.
コードサイズと実行速度の関係に関する話(perfでL1命令キャッシュミスをみてみよう)
先日, 「やみくもにコード生成してもコードが肥大化してキャッシュから外れると遅くなるよ」とsinya8282さんに言ったけどどの程度だろうと思って実測してみた. 測定コードはicache.cpp(Windows/Linux, 32bit/64bit対応)
./a.out 0で実行すると次のようなシーケンシャルにaddを実行するコードを生成する.
.lp:
add eax, 1
add eax, 1
...
同じものをたくさん生成
...
add eax, 1
sub ecx, 1
jnz .lp
Xeon X5650で走らせるとシーケンシャル版はコードサイズが32KBを超えても意外と速度低下は無かった.
| コードサイズ(KB) | <1 | 1.5 | 3 | 6 | 12 | 24 | 49 | 98 | 196 |
|---|---|---|---|---|---|---|---|---|---|
| clk/unit | 0.9 | 0.908 | 0.906 | 0.923 | 0.898 | 0.907 | 0.910 | 0.920 | 0.917 |
これは単純な命令のシーケンシャル実行なのでdecoderの先読みが十分速くて実行ユニットへの命令供給が問題ないということだろう.
次にオプションを変えて./a.out 1で実行すると次のようなjmpを含むコードを生成する.
./a.out 2では更にジャンプがシーケンシャルでなくなるコードを生成する.
.lp:
add eax, 1
jmp L1
L1:
add eax, 1
jmp L2
L2:
add eax, 1
jmp L3
L3:
...
同じものをたくさん生成
...
add eax, 1
jmp Ln
Ln:
sub ecx, 1
jnz .lp
このコードでベンチマークをとると次のようになった.
| コードサイズ(KB) | <1 | 1 | 2 | 4 | 8 | 16 | 32 | 65 | 131 |
|---|---|---|---|---|---|---|---|---|---|
| clk/unit | 1～2 | 2.099 | 2.060 | 2.059 | 2.085 | 2.029 | 9.138 | 12.138 | 12.039 |
これらのjmpがからむコードでは, コードサイズが16KBを超えるあたりでガクンと実行速度が落ちた. i7-2600でもほぼ同じ傾向.
L1命令cache自体は32KBあるのにそれよりも前に速度劣化が発生している. これはjmp命令が複雑でμopへのdecodeが追いつかず, decoded icacheも足りなくなって底をついたせいじゃないかと想像. decoded icacheはSandy Bridgeで最大1536エントリ. もちろん命令の種類によっても変動はあるだろう. いろいろ試すと面白いかも.
せっかくなので先日の最適化手法の勉強方法で少し触れたLinuxプロファイラツールperfでicacheミスがどのぐらいあるかを見てみよう. perfはバージョンや環境によってによって結構オプションが違うみたいなので注意が必要.
>perf --version
perf version 0.0.2.PERF
>perf stat -e L1-icache-load-misses ./a.out 0
24166341 L1-icache-load-misses # 0.000 M/sec
>perf stat -e L1-icache-load-misses ./a.out 1
239641246 L1-icache-load-misses # 0.000 M/sec
>perf stat -e L1-icache-load-misses ./a.out 2
342195755 L1-icache-load-misses # 0.000 M/sec
-eオプションで指定できるパラメータは
perf list
で取得できる. L1-icache-loadl-missesの値がシーケンシャル版に比べて ジャンプ版は1桁icahceミスが増えている(もちろんjmp命令が増えてるので同一条件ではないのだけど).
ちなみにdecoded icacheについては先日書き始めてみた「Intelプロセッサ最適化マニュアルを読もう」で少し書いた(一次情報はもちろんIntelのマニュアルを参照してね).
最適化手法の勉強方法
人数が少なかったので多分顔合わせ的なものだろうと参加してみた. 管理者のsyuu1228さんは何故か不在.
Intelの最適化マニュアルを読むのはある程度のスキルがついてからでよいと思う. 初心者にはあまりお薦めしない. 理由は資料が膨大なのでどれが重要なのか分からない, 読んでて退屈(個人的にはおもろいけど)なので途中で挫折しやすい, かつそうなると後半の大事な部分が抜け落ちるから.
こういうのは人によって勉強方法が異なるので「これが絶対正しい」というわけじゃない. だから自分の経験(主にx86/x64)を書いてみよう. なお, ここでは「そもそも最適化が必要なの?」という問い対しては触れない.
#include <stdio.h>
void f()
{
int id = 0;
unsigned int n = 64;
unsigned int a = (id - 1) % n;
printf("f=%u\n", a);
}
void g()
{
int id = 0;
const unsigned int n = 64;
unsigned int a = (id - 1) % n;
printf("g=%u\n", a);
}
int main()
{
f();
g();
return 0;
}
このコードをgcc/g++(4.6.0)で動かすとどちらでも
f=63 g=63mpicc(for 1.2.7 (release) of : 2005/11/08 03:56:31)でも同じ結果. でもmpicxxだと
f=63 g=4294967295ん, 処理依存を踏んだ? でもconstのありなしで整数演算の挙動が変わるって聞いたことないからmpicxxのバグなのかなあ.
const uint32_t NPROCS = 64; const uint32_t to = (myid - 1) % NPROCS;でuint32_tを使うことでwrap aroundしても大丈夫なようにしてたつもりが, 課題サンプルの元からあったプロセッサ番号を示す変数myidがintのままだったのでmyid = 0のときに0xffffffffになってたからだった. うわっちゃ. こないだ定数クイズなんて出してたくせに.
C/C++における定数クイズ(規格改定による仕様変更の差異について)
int x = -1; int y = x == 4294967295; int z = x == 0xffffffff;
としたときy, zの値は何か. もとネタはC/C++の定数の型の話 C90/C99の差分のびみょーな話. そこでも触れられているが接尾語(ULとかLLとかのこと)無しの10進数, 16進数リテラルの扱いは規格改定の際に意外と変わっている. まとめてみよう(以下long intをlongと略す).
| 10進数 | 16進数 | |
|---|---|---|
| C90(yupo5656さんの記事から孫引き) | int, long, unsigned long | int, unsigned int, long, unsigned long |
| ISO/IEC14882:1998(C++98) ISO/IEC14882:2003(C++03) | int, long, それ以外は未定義 | |
| ISO/IEC9899:1999(C99) N3242.pdf(C++0xドラフト) | int, long, long long | int, unsigned int, long, unsigned long, long long, unsigned long long |
C++0xではC99で入ったlong long型がようやく正式に入る. ポイントは二つ. 10進数と16進数とで整数定数を決める型の順番が異なること, 昔のCとC++とでは仕様に違いがあり, C99とC++0xとで統一されたということ. yupo5656さんのところではC++03はC90と同じとあったけど違うと思う.
では問題を考えてみよう. sizeof(long long) = 8とする. まずsizeof(int) = sizeof(long) = 4の環境とする. すると0xffffffffはいずれの場合もunsigned intになるのでz = 1.
それに対して4294967295はC90ではunsigned longになるのでx = -1がunsigned longに整数拡張(integer promotion)されて4294967295になり, y = 1となる. C++98, C++03なら4294967295はlongで表せないのでなんと未定義. C99/C++0xではlong longになるのでxの値-1と比較してy = 0となる.
sizeof(int) = 4, sizeof(long) = 8の環境とする. すると0xffffffffは上記の環境と同じでz = 1. 4294967295はlongになるのでy = 0となる. まとめると
| sizeof(int) = sizeof(long) = 4 | sizeof(int) = 4, sizeof(long) > 4 | |||
|---|---|---|---|---|
| y | z | y | z | |
| C90 | 1 | 1 | 0 | 1 |
| ISO/IEC14882:1998(C++98) ISO/IEC14882:2003(C++03) | 未定義 | 1 | 0 | 1 |
| ISO/IEC9899:1999(C99) N3242(C++0xドラフト) | 0 | 1 | 0 | 1 |
試してみる... ありゃ, gcc 4.6.0だと32bitでは-std=c++0xでもy = 1になるなあ. -std=c99だと正しくy = 0になるので多分gccが間違ってるんだろうなあ.