GNU strlen を読む
Hacker News でみかけた Glibc’s strlen implementation: Probably not what you’d guess というスレッドが面白かった。スレッドでは GNU の他に OpenBSD (べたな C, i386, x86-64) と Apple (SSE3 を使っている) にもリンクがあるんだけど、ここでは GNU strlen の実装についてだけ説明します。
実装
GNU strlen は文字列から long word 単位でおおまかに NUL っぽいものを探してから、バイト単位でこまかく探す、という方法をとっている。
strlen.c にある strlen は、トリッキーなところを丁寧にコメントで補っているせいもあってやや長い。まず、strlen の引数の str のアドレスが long word にそろっていない場合、最初の for ループにはいる。
for (char_ptr = str; ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; ++char_ptr) if (*char_ptr == '\0') return char_ptr - str;
このループはふつうに文字単位で回っていて、NUL でも抜けられる。ただ、さらに終了条件としてポインタのアドレスの下の桁も見ていることに注意してほしい。もし NUL がなくても、文字列の先頭が long word にそろった時点でこのループは終了してしまう。
次に、char* を long int* にキャストして himagic と lomagic という定数を定義している。
longword_ptr = (unsigned long int *) char_ptr; /* ... */ magic_bits = 0x7efefeffL; himagic = 0x80808080L; lomagic = 0x01010101L;
magic_bits は #if 0 の中でだけ使っている == 使っていないので無視していい。himagic は 0×80808080 で2進数だと
1000 0000 1000 0000 1000 0000 1000 0000
こう表せる。lomagic は 0×01010101 なので
0000 0001 0000 0001 0000 0001 0000 0001
こうだ。実装では long word が 32bit より長いマシンではこのパターンをもう一回くりかえし、64bit より上のマシンだと abort している。
ここから long word 単位のループにはいる。for 文直後のコメントは magic_bits 時代のものだと思う。
for (;;) { /* ... */ longword = *longword_ptr++; if ( #if 0 ... #else ((longword - lomagic) & himagic) #endif != 0) {
たとえば “hi” だと longword - lomagic は
h i NUL 0110 1000 0110 1001 0000 0000 XXXX XXXX - 0000 0001 | 0000 0001 | 0000 0001 | 0000 0001 0110 0111 0110 0111 1111 1111 XXXX XXXX
NUL から1を引いたときに上から繰り下がって、NUL の桁の全ビットが立つ。X は未定義なのでここではスルーしてほしい。
これに himagic を & すると
0110 0111 0110 0111 1111 1111 XXXX XXXX & 1000 0000 | 1000 0000 | 1000 0000 | 1000 0000 0000 0000 0000 0000 1000 0000 XXXX XXXX
ここで結果が 0 にならない場合、longword のなかの文字のどれかが NUL である可能性があるので、if のなかで文字単位で探している。
{ const char *cp = (const char *) (longword_ptr - 1); if (cp[0] == 0) return cp - str; if (cp[1] == 0) return cp - str + 1; if (cp[2] == 0) return cp - str + 2; if (cp[3] == 0) return cp - str + 3; if (sizeof (longword) > 4) { if (cp[4] == 0) return cp - str + 4; if (cp[5] == 0) return cp - str + 5; if (cp[6] == 0) return cp - str + 6; if (cp[7] == 0) return cp - str + 7; } }
日本人としては、ループから if に入る条件が char の MSB が立たないことを期待しすぎていると思った。
感想
NUL 終端文字列の長さをとる処理はどうやっても O(n) だ。Joel Spolsky は NUL 終端文字列を「文字列を格納する最悪の方法のひとつ」と評しているし、文字列の長さは番兵で表現せずに別の場所にいれておいたほうがいいと思う。
とはいえ、計算上はどうしようもない問題でも、計算機上ではまだ工夫の余地があるというのは面白かった。教科書的にはアルゴリズムで O(n) の定数を削るよりもデータ構造を検討するべきなんだけど、これ libc ですからね。