1. Qiita
  2. 投稿
  3. C

標準ライブラリ関数のstrchrは何故速いのか

  • 23
    いいね
  • 2
    コメント

下記のような自前実装の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;
}

昨今はライブラリ関数内でSIMD命令が使われているという話も聞くので、それが原因かもしれないと考えて調べてみました。

作業環境は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命令が使われていたもの
    • bzero
    • memccpy
    • memchr
    • memcmp
    • memcpy
    • memmove
    • memset
    • strchr
  • 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);
}