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

下記のような自前実装の`strchr()`を書いてライブラリ関数と速度比較をしたところ、ライブラリ関数の方が劇的に速いという結果になりました（`s`の文字列長が長いと自前実装の方が~~約20倍~~約6倍遅かった）。

実験に使ったコードはシンプルなもので、そこまで品質が悪いとは思えません。なぜそんなに劇的な差がついたのでしょうか。

```c
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命令が使われていたもの
  - `bzero`
  - `memccpy`
  - `memchr`
  - `memcmp`
  - `memcpy`
  - `memmove`
  - `memset`
  - `strchr`
- SSE2命令が使われていたもの
  - `strcmp`
  - [`strcpy`](https://opensource.apple.com/source/Libc/Libc-1158.20.4/x86_64/string/strcpy.s.auto.html)
  - [`strlen`](https://opensource.apple.com/source/Libc/Libc-1158.20.4/x86_64/string/strlen.s.auto.html)
  - `strncmp`
  - [`strncpy`](https://opensource.apple.com/source/Libc/Libc-1158.20.4/x86_64/string/strncpy.s.auto.html)
  - [`strnlen`](https://opensource.apple.com/source/Libc/Libc-1158.20.4/x86_64/string/strnlen.s.auto.html)

他の環境では違った結果になるかもしれませんが、この辺の関数でSIMD命令が使われてる可能性があるんだな、という目安にはなると思います。

# 追試用コード

筆者は`-O0`で実験しました。

```c
#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倍程度の差になる