下記のような自前実装のstrchr()を書いてライブラリ関数と速度比較をしたところ、ライブラリ関数の方が劇的に速いという結果になりました（sの文字列長が長いと自前実装の方が約20倍約6倍遅かった）。
実験に使ったコードはシンプルなもので、そこまで品質が悪いとは思えません。なぜそんなに劇的な差がついたのでしょうか。
char *my_strchr(const char *s, char c)
{
char *p = (char *)s;
do {
if (*p == c) {
return p;
}
} while (*p++ != '\0');
return NULL;
}
調べてみたところ、ライブラリ関数はC言語ではなくマシン語で実装されており、SIMD命令であるAVX2命令が使われていることがわかりました。SIMD命令はベクトル演算を行うマシン語命令で、1命令で複数の演算（今回なら比較演算）を行えるため、今回のように劇的な速度差ができるのです。
以下、作業環境はOS X 10.11、CPUはIntel Core m5です。
strchrの実体を探す
dtrussを使って読んでいるライブラリを確認してみたところ、/usr/lib/system/libsystem_c.dylib内にstrchrの実装がありそうでした。
$ nm -gU /usr/lib/system/libsystem_c.dylib | grep strchr
0000000000003028 I _strchr
しかし、otoolで逆アセンブルしてみると_strchrシンボルが見当たりません。
$ otool -Vt /usr/lib/system/libsystem_c.dylib | less
代わりと言っては何ですが、下記のような行がチラホラ見つかります。
000000000000ac53 callq 0x85402 ## symbol stub for: _strchr
また、確かに何やらそれっぽいシンボルテーブルも見つかります。
$ otool -Iv /usr/lib/system/libsystem_c.dylib | grep strchr
0x0000000000085402 1741 _strchr
0x000000000008e6f8 1741 _strchr
どうやら、実体は更に別ファイルにあるということのような気がしますね…
ここからどう読まれるのか不明ですが（弱）、もう一つ怪しげなライブラリ/usr/lib/system/libsystem_platform.dylibが存在します。この中には次のようなシンボルが見つかります。
$ otool -Vt /usr/lib/system/libsystem_platform.dylib | egrep 'strchr.*:'
__platform_strchr$VARIANT$Generic:
__platform_strchr$VARIANT$Haswell:
__platform_strchr:
上記の中でも__platform_strchr$VARIANT$Haswellが気になるところです。名前的にHaswell以降に最適化されたstrchrなのではないか？と期待できるので、これを少し眺めてみましょう。
するとvpcmpeqbという命令が見つかります。これはHaswellから入ったSIMD命令のAVX2命令ですね！なるほど、256bit＝32バイトを1命令で比較するのか…。そりゃ速くもなりますわな…。
__platform_strchr$VARIANT$Genericの方ではpcmpeqb命令を使っています。これもSSE2命令ということで128bit=16バイトを1命令で比較しているわけです。昨今ではgenericといっても相当リッチな環境ですねー。
デバッガで追う
$ lldb ./a.out
(lldb) target create "./a.out"
Current executable set to './a.out' (x86_64).
(lldb) b strchr
Breakpoint 1: re-exported target = libsystem_platform.dylib`_platform_strchr, address = 0x000000000000146f
(lldb) run foo x
Process 14393 launched: './a.out' (x86_64)
Process 14393 stopped
* thread #1: tid = 0x205f4f, 0x00007fff94e87400 libsystem_platform.dylib`_platform_strchr$VARIANT$Haswell, stop reason = breakpoint 1.1
frame #0: 0x00007fff94e87400 libsystem_platform.dylib`_platform_strchr$VARIANT$Haswell
libsystem_platform.dylib`_platform_strchr$VARIANT$Haswell:
-> 0x7fff94e87400 <+0>: pushq %rbp
0x7fff94e87401 <+1>: movq %rsp, %rbp
0x7fff94e87404 <+4>: vmovq %rsi, %xmm0
0x7fff94e87409 <+9>: vpbroadcastb %xmm0, %ymm0
(lldb)
先ほど実験に使ったプログラムでstrchrにブレークポイントを置くと、予想通り_platform_strchr$VARIANT$Haswellで停止しました。
というわけで、最近の文字列処理関数ではSIMD命令が使われているという話を自分で確認できました。
なるほど、自前でcharをチマチマ比較するコード書いちゃいけない時代なんですなー。
SIMD命令が使われていることが確認できたライブラリ関数一覧
私の手元の環境にて、デバッガでステップ実行して確認しました。
- AVX2命令が使われていたもの
bzeromemccpymemchrmemcmpmemcpymemmovememsetstrchr
- SSE2命令が使われていたもの
他の環境では違った結果になるかもしれませんが、この辺の関数でSIMD命令が使われてる可能性があるんだな、という目安にはなると思います。
追試用コード
筆者は-O0で実験しました。
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#ifdef USE_MY_STRCHR
char *my_strchr(const char *s, char c)
{
char *p = (char *)s;
do {
if (*p == c) {
return p;
}
} while (*p++ != '\0');
return NULL;
}
#endif
int main(int argc, const char **argv) {
struct timeval tv1, tv2;
long usec;
char *p;
if (argc < 3) return 0;
gettimeofday(&tv1, NULL);
for (int i = 0; i < 100000000; i++) {
#ifdef USE_MY_STRCHR
p = my_strchr(argv[1], argv[2][0]);
#else
p = strchr(argv[1], argv[2][0]);
#endif
}
gettimeofday(&tv2, NULL);
usec = (tv2.tv_sec-tv1.tv_sec)*1000000 + (tv2.tv_usec-tv1.tv_usec);
printf("%ld\n%.06f sec\n", p ? (p - argv[1]) : -1, usec/1000000.0);
}
まとめ
- macOSの一部C標準ライブラリ関数（一部の文字列系関数）ではSIMD命令が使われている
- Cで素直に記述したソースコードより平均的に高速だと考えられる、ひどいときは6倍程度の差になる