glibcのstrlenが2023年刷新、文字列外アクセスでループを完全排除した極限ハック

• 事実と背景：glibcのstrlen汎用C実装が2023年に刷新され、端数処理のループを完全に排除したO(1)アルゴリズムへ移行した。
• 技術的変革：PTR_ALIGN_DOWNによる文字列手前からのワード読み込みと、繰り下がりを排除したfind_zero_allビット演算を導入。
• 現場への影響：通常のCプログラムでは即死する「範囲外アクセス」を、OSのページ境界仕様を逆手に取って安全に実行している。

プログラミングを学び始めた初日に書くような、文字列の長さを測るstrlen関数。愚直に実装すれば、ポインタを1バイトずつ進めて（終端文字）を探すだけの単純なループになる。しかし、我々シニアエンジニアが直面する現代のプロダクション環境において、この「1バイトずつの走査」は非効率の極みであり、CPUの実行パイプラインをドブに捨てるようなものだ。現代のプロセッサは、メモリからデータを読み出す際にキャッシュラインやワード（64bit環境なら8バイト）単位で処理を行う。ならば、メモリを8バイトまとめて読み込み、一撃で終端文字を判定できれば、ループ回数は8分の1に激減する。これがglibcが挑む高速化のスタートラインである。

しかし、ここには「ページ境界」というOSレイヤーのデッドロック級の罠が待ち受けている。通常のプロセスが扱う仮想メモリは、通常4KBなどの「ページ」単位で管理されており、ページごとに読み書きのアクセス権限が設定されている。もし、探索対象の文字列がページの末尾ギリギリ（例えば境界の手前3バイト）に配置されており、その先が未割り当て、あるいはアクセス禁止の領域だった場合、どうなるか。何も考えずにそこから8バイトをまとめて読み込もうとすれば、文字列の終端を超えて読めないページにアクセスしてしまい、セグメンテーションフォールト（SIGSEGV）を引き起こしてプロセスは即死する。深夜の障害対応で呼び出されたエンジニアが、ログに刻まれたこのエラーを見て頭を抱える姿が目に浮かぶようだ。

この致命的な問題を回避するために、glibcは「アラインメント（整列）」という概念を利用する。OSのページ境界は必ずページの大きさ（通常は4096の倍数、すなわち8の倍数）のアドレスに存在する。したがって、読み込み開始アドレスを8の倍数にアライン（調整）してやれば、1回の8バイト読み込みがページ境界をまたぐことは絶対にない。2023年の変更前のglibc実装では、このアラインメントに達するまでは「1バイトずつ愚直に読む」という泥臭い妥協を挟むことで、安全性を担保していた。しかし、この妥協こそが、極限のパフォーマンスを追い求める開発者にとっての「最後のボトルネック」だったのである。

2023年のアップデート以前、glibcは以下の3段階で終端文字を探索していた。まずワード境界（8の倍数アドレス）に達するまで1バイトずつ読み、境界に達したら8バイト（1ワード）単位で一気に読み込み、最後に終端文字を含むワードの中を1バイトずつ走査して正確な位置を特定する。この第2段階である「ワード内に0（終端文字）が含まれるか」を判定する処理こそが、低レイヤーにおける伝説的なビット魔術である。具体的には、以下の数式が使われていた。

(longword - 0x0101010101010101UL) & ~longword & 0x8080808080808080UL

この式がなぜ機能するのか、1バイト（8ビット）の値 b に対する挙動を以下の表で整理してみよう。この演算は、値が 0x00 のときだけ最上位ビット（MSB）である 0x80 が残るという性質を持っている。

この演算を8バイト（64ビット）に拡張したのが上記の数式である。ただし、複数バイトをまとめて引き算すると、バイト境界を越えて「繰り下がり（ボロー）」が発生する。例えば、ワード内に 0x0100 という並びがあった場合、下位の 0x00 から1を引くことで繰り下がりが発生し、上位の 0x01 からも1が引かれてしまう。その結果、本来は0ではない 0x01 の位置にも 0x80 の印（マスク）が立ってしまうのだ。しかし、これは「ワード内に0が含まれているか否か」を判定するだけであれば、偽陰性（0があるのに検出できない）が発生しないため、ワード単位のスキップ判定としては完璧に機能する。だが、このアルゴリズムには、最初と最後の端数処理でどうしてもループが発生するという、美しさに欠ける弱点があった。

2023年2月6日、glibcの開発コミュニティはこの端数処理のループすらも許さない、狂気的とも言えるアップデートをマージした。新実装の核心は、「文字列の先頭より手前のアドレスから読み始める」という、一見すると配列の範囲外アクセスを犯しているかのようなアプローチである。例えば、文字列が 0x1003 から始まっている場合、マクロ PTR_ALIGN_DOWN を用いてアドレスを 0x1000 に切り下げ、そこから8バイトを読み込む。前述の通り、ページ境界は8の倍数であるため、この切り下げによって前のページ（読めない領域）に侵入することは絶対にない。しかし、通常のC言語のルール（規格）に照らし合わせれば、これは未定義動作の崖の上を歩く行為だ。glibcは、対象環境のメモリ仕様やコンパイラ（GCC）の独自属性 __may_alias__ を前提とすることで、この禁忌を安全なハックへと昇華させている。

手前から読み込むことで、最初のワードには「文字列の先頭より前にある無関係なデータ」が含まれることになる。ここに偶然 0x00 が存在した場合、それを終端文字と誤認してはならない。そこで、繰り下がりの影響を完全に排除した真のゼロ検出関数 find_zero_all が導入された。

~(((x & m) + m) | x | m)  /* m = 0x7f7f7f7f7f7f7f7fUL */

この式は、各バイトの最上位ビットをマスクした上で 0x7f を足し合わせることで、バイト間の干渉（繰り下がり）を完全にシャットアウトする。これにより、各バイトが 0x00 である場所だけに正確に 0x80 が立つマスクが生成される。あとは、文字列の開始位置（例えば 0x1003）より手前の不要なバイト数分だけ、このマスクを右シフト（shift_find）して物理的に削ぎ落とせばよい。最後に、CPUのハードウェア命令に直結するコンパイラ組み込み関数 __builtin_ctzl（最下位から連続する0のビット数を数える）を呼び出し、それを8で割ることで、ループを1回も回すことなく、終端文字の正確なインデックスを弾き出す。最初から最後まで、一切の分岐ループを排除した、完全なO(1)処理の完成である。

このglibcの極限ハックは、我々現代のソフトウェアエンジニアに強烈な教訓と問いを突きつけている。現代の開発は、フレームワーク、仮想マシン、コンテナ、そしてクラウドといった厚い抽象化レイヤーの上で行われており、メモリのアラインメントやキャッシュライン、OSのページ境界といった物理的な制約を意識する機会は激減した。しかし、我々が毎日何気なく動かしているWebサーバーやデータベース、AIの推論エンジンの最深部では、このような「ハードウェアの物理限界に肉薄する狂気的な最適化」が世界を支えているという事実を忘れてはならない。

もちろん、このglibcのコードを通常のアプリケーション開発で真似してはならない。AddressSanitizerを有効にした瞬間にビルドパイプラインは真っ赤に染まり、コードレビューでは「未定義動作の温床」として即座に却下されるべきスパゲッティコードの極みである。しかし、我々が目指すべきは、このコードを模倣することではなく、このレベルの「低レイヤーへの深い洞察」を自らのアーキテクチャ設計に宿すことだ。例えば、データベースのインデックス設計、キャッシュのヒット率向上、シリアライズ処理の高速化など、物理レイヤーの挙動を理解しているか否かで、システムの限界性能は桁違いに変わってくる。

ここで、読者諸氏に痛烈な問いを投げかけたい。我々は、フレームワークが提供する「動けば良い」コードに甘んじて、ハードウェアのポテンシャルをドブに捨ててはいないだろうか？ あなたが昨日書いたそのループ、本当にこれ以上高速化できないと言い切れるだろうか？ 抽象化の温室から一歩踏み出し、CPUとメモリが織りなす物理的な現実に目を向けること。それこそが、単なる「コードの書き手」から「真のシステムアーキテクト」へと至る、唯一無二の処方箋なのである。