あらまし
strlen() という関数がある。御存知の通り、文字列の長さを算出する標準 C ライブラリの関数だ。
やってることは単純で、例えば以下のように実装できる。
size_t strlen_simple(const char* str)
{
const char* p = str;
while (*p) ++p;
return size_t(p - str);
}
'\0' が見つかるまでポインタを進め、初期位置との差分を返すだけだ。これで機能的には std::strlen() と同等である。
では、速度的にはどうだろう？適当にベンチマークを書いて MSVC 2022 でコンパイル＆実行するとこうなった。
std::strlen(): 390.91ms
strlen_simple(): 1640.53ms
std::strlen() の圧勝である。しかし、こんな単純な関数のどこでこんな差が出るのだろう？
packed 比較
上記の strlen_simple() は 1 byte 毎に '\0' かの判別を行っている。しかし、1 byte 毎の処理は遅い。
今どきの CPU は 64 bit なのだから、8 byte 単位でまとめて処理できたら大きな高速化を見込めそうだ。この場合、8 byte の型 (uint64_t) の中に 0 の byte が含まれるかをどう判別するかが問題となる。これは以下のようなビット演算でできる。
bool contains_zero_byte(uint64_t v)
{
constexpr uint64_t hi = 0x8080808080808080;
constexpr uint64_t lo = 0x0101010101010101;
return ((v - lo) & ~v & hi) != 0;
}
(v - lo) & ~v & hi の結果、元が 0 の byte は 0x80、非 0 の byte は 0x00 になる。0 の byte が含まれなければ 0 になるので、8 byte まとめて判別できる。
また、今回のケースでは 0 が含まれているかに加え、最初の 0 のインデックスが欲しい。これは C++20 であれば std::countr_zero() でできる。右からの連続した 0 の bit の数が得られるので、それを 8 で割れば最初の 0 のインデックスになるわけだ。
int index_of_first_zero_byte(uint64_t v)
{
constexpr uint64_t hi = 0x8080808080808080;
constexpr uint64_t lo = 0x0101010101010101;
uint64_t mask = (v - lo) & ~v & hi;
return std::countr_zero(mask) / 8;
}
C++20 が使えない場合、x86 における contr_zero() は以下のようになる。
int countr_zero(uint64_t v)
{
#ifdef _MSC_VER
return _tzcnt_u64(v);
#else
return __builtin_ia32_tzcnt_u64(v);
#endif
}
tzcnt (Trailing Zero Count) は CPU の命令レベルで実装されており、高速に動作する。
(比較的新しい命令であり、gcc や clang では -mbmi などのオプションで明示的に有効化する必要がある。有効化しなかった場合、コンパイルエラーにはならないが、エミュレーション実装に差し替わり、若干遅くなるようだ)
これらのテクニックを用いて 8 byte 単位で処理する strlen が以下になる。
size_t strlen_u64(const char* str)
{
// 8 byte align ではない先頭部分を処理
const char* aligned = (const char*)((size_t(str) + 0x7) & ~0x7);
for (const char* p = str; p != aligned; ++p) {
if (*p == 0) {
return size_t(p) - size_t(str);
}
}
// 8 byte 単位でまとめて処理
constexpr uint64_t hi = 0x8080808080808080;
constexpr uint64_t lo = 0x0101010101010101;
for (const uint64_t* qp = (const uint64_t*)aligned; ; ++qp) {
uint64_t packed = *qp;
uint64_t mask = (packed - lo) & ~packed & hi;
if (mask != 0) {
int idx = countr_zero(mask) >> 3;
return size_t(qp) - size_t(str) + idx;
}
}
}
最初に 8 byte align ではない先頭部分を 1 byte 単位で処理している。x86 では 8 byte align ではない uint64_t* や 4 byte align ではない float* でも問題なく読めるのだが、align 不揃いだと '\0' の位置によってはページの境界を跨いで access violation を起こす危険性があるため、このような処置が必要になる。
8 byte align になっているため、*qp はクラッシュしないという意味では安全なのだが、malloc() などで確保した範囲を超えてアクセスする可能性はあり、その場合 Address Sanitizer が有効だと律儀にエラーを出してくる。Address Sanitizer を使う場合、この関数は審査しないようにしておく必要があるだろう。(clang なら __attribute__((no_sanitize_address))、MSVC なら __declspec(no_sanitize_address))
この方式はポータブルかつ strlen_simple() よりずっと早く動作し、多くの C 標準ライブラリの実装で採用されているようだ。
std::strlen(): 390.91ms
strlen_simple(): 1640.53ms
strlen_u64(): 364.14ms
MSVC 2022 でのベンチマーク結果はこうなった。strlen_simple() と比べると圧倒的である。
また、MSVC の std::strlen() は strlen_u64() と大体同じ内容なのだが、std::strlen() は inline 展開されておらず、strlen_u64() されているため、若干差が出ているとみられる。
SSE による比較
8 byte 単位の処理が実現できたが、もう一歩踏み込んでみよう。
SSE を使えば 16 byte 単位の処理ができる。しかも SSE 4.2 には文字列比較用の命令があり、16 byte の中から特定のパターンを探してそのインデックスを得る、といったことが高速に可能だ。
SSE を使って書くと以下のようになる。
size_t strlen_sse(const char* str)
{
const __m128i zero = _mm_set1_epi8(0);
const __m128i* sxp = (const __m128i*)(size_t(str) & ~0xf);
// 16 byte align ではない先頭部分を処理
size_t mod = size_t(str) & 0xf;
if (mod) {
__m128i sx = _mm_load_si128(sxp);
__m128i mask = _mm_cmpeq_epi8(zero, sx);
if (!_mm_test_all_zeros(mask, mask)) {
size_t remain = 16 - mod;
for (size_t i = 0; i < remain; ++i) {
if (str[i] == 0)
return i;
}
}
++sxp;
}
// 16 byte 単位で処理
for (;;) {
__m128i sx = _mm_load_si128(sxp);
__m128i mask = _mm_cmpeq_epi8(zero, sx);
if (!_mm_test_all_zeros(mask, mask)) {
int idx = _mm_cmpistri(sx, sx, _SIDD_CMP_EQUAL_EACH | _SIDD_MASKED_NEGATIVE_POLARITY);
return size_t(sxp) + idx - size_t(str);
}
++sxp;
}
}
SSE の load も必ずしも 16 byte align を要求しないが、strlen_u64() と同じ理由で 16 byte align ではない部分を先に処理している。Address Sanitizer 抑止が要るのも同じだ。
メイン部分は以下のような手順になっている。
- _mm_load_si128() で 16 byte 読み込んで SSE のレジスタに格納する
- _mm_cmpeq_epi8() で文字列と 0 を比較 ('\0' がある場合、対応する mask の byte が 0xff になる)
- _mm_test_all_zeros() で mask に 0xff が含まれるか判別 ('\0' があるなら true)
- _mm_cmpistri() で '\0' のインデックスを得て文字列の長さを決定
_mm_cmpistri() が SSE 4.2 の命令で、_SIDD_CMP_EQUAL_EACH | _SIDD_MASKED_NEGATIVE_POLARITY フラグを与えると、__m128i を 16 byte の文字列と見立てて 2 つの文字列の一致する長さを返す。途中に '\0' がある場合はそこまでの長さになる。この場合、sx 同士を _mm_cmpistri() で比較しているため、'\0' のインデックスが返る。
なお、_mm_cmpistri() とその一族の動作はものすごく複雑で、フラグによって全く異なる挙動になる。ぐぐってもほとんど情報がなくて、詳細は ChatGPT に聞いてみるといいだろう。
この実装を手持ちのいくつかの環境でテストしたところ、その全てで strlen_u64() よりも有意に早い結果になった。一部の clang 系の環境の std::strlen() はこの方式を採用しているようで、これが私が知る最も早い実装になる。
std::strlen(): 390.91ms
strlen_simple(): 1640.53ms
strlen_u64(): 364.14ms
strlen_sse(): 201.10ms
std::strlen() の inline 展開問題
std::strlen() には特殊な事情があって、その点にも触れておきたい。端的には、最適化を有効にすると逆に遅くなることがある。
現象としては、inline 展開されたときとされなかったときで全く別の実装が用いられることがあり、展開されたときの実装が遅いというものだ。以下のベンチマーク結果は、本記事を書いている時点で最新の MSVC 2022 での結果になる。
std::strlen() (inlined): 1666.68ms
std::strlen(): 390.91ms
strlen_simple(): 1640.53ms
strlen_u64(): 364.14ms
strlen_sse(): 201.10ms
inline 展開されると strlen_simple() と同等処理、つまり 1 byte 単位の超遅い実装に差し替わるようだ。std::strlen() は std::string や std::string_view の内部でも使われていることが多く、結構な広範囲に影響が出ていると思われる。
この現象は gcc でも起きることが確認されている。(godbolt.org で試したところ、gcc 9 系と -O1 の組み合わせで起きるのが確認できた。10 以降のバージョンでは確認できなかったが、対策されたのか条件が変わっただけなのかは不明)
コンパイラのバグと言っていいレベルのおかしな挙動だが、今現役のコンパイラで起きている以上、そういうものと認識して付き合わなければならない。strlen() の遅さが問題になるようなケースはそうそうないとは思われるが、気に留めておく価値はあるだろう。
おわりに
検証に用いたコードは以下になる。(godbolt.org 上のベンチマーク結果は信用ならないので注意)
std::strlen() の inline 展開にまつわる問題は よっふぃ～ さんに教えていただいた。感謝。
そんなわけで、一見単純な strlen() が実は必要以上に奥が深いことがわかった。