AIが書けなかったIPv4パーサー

本記事では、SIMD命令に頼らず、SWAR（レジスタ内SIMD）とビット操作のテクニックを用いた高速なIPv4アドレス解析アルゴリズムについて詳述しています。著者はDaniel Lemireのブログ記事に触発されつつも、AIに高性能コードを任せるべきではないと主張し、手動での最適化の重要性を強調しています。

アルゴリズムはまず、IPv4アドレス文字列（長さ7～15文字）を2つの64ビットレジスタに読み込みます。headは最初の8バイト、tailは最後の8バイトを含みます。長さ7の文字列に対しては、条件に応じて読み取り開始位置を調整し、バッファオーバーフローを防ぎます。コアとなるparseTwoTriplets関数は、2つのオクテット（6文字）を一度に処理し、ASCIIオフセット（0x30）を減算して数値を取得し、位置の重み（100、10、1）を乗算してpext命令で結果を抽出します。検証部分では、特別な加算（+0x76）を使用して不正な文字を検出し、動的マスクにより桁間の範囲制約（例えば百の位が2の場合、十の位は5以下）を処理します。

ドット区切りの処理では、XOR（0x2E）でドットの位置を特定し、乗算ハッシュを使って32エントリのルックアップテーブルにインデックスします。このテーブルから対応するpdepマスクとシフト量を取得し、有効なバイトを正しく配置します。最終版では、乗算ハッシュの代わりにpextを使用することでさらに高速化しています。

ベンチマークはi7-7700K上で150万のランダムIPアドレスを64回解析し、平均レイテンシ5.11ナノ秒/IP、スループット2.60 GB/sを記録しました。Robert Grahamのベンチマークと比較しても、非SIMD実装の中で上位の性能を示しています。著者は、優れたアイデアであっても、境界ケース（例：255.255.255を誤って受け入れる）を見つけるための厳格なテストスイートと、アセンブリコードの徹底的なチェックが不可欠であると述べています。

アルゴリズムは少なくとも6回の最適化サイクルを経ており、各段階でCompiler Explorerを用いてアセンブリ出力を確認し、llvm-mcaでボトルネックを分析しました。最終版はAI生成の線形スキャン関数よりもはるかに高速であり、巧妙なビット演算によって分岐予測の失敗を回避し、スループットとレイテンシの両方で印象的な結果を達成しています。