ARM64 での gearhash の高速化

← 作成中 ARM64 での gearhash の高速化 (2倍高速) 2026年9月6日 要約: バージョン0.1.4以降、gearhash クレートはNEONバックエンドを獲得し、ARM64で典型的なチャンクサイズにおいて約2倍高速になりました。aarch64 では自動的に選択され、後方互換性があるため、クレートの利用者は更新するだけで済みます。この実現方法の詳細に興味がある場合は、以下をお読みください。最終結果に直接スキップしても構いません。 すべてはどのように始まったか 2019年末、私は個人的なバックアップシステムを構築しており、その一部としてコンテンツ定義チャンク分割という技術に興味を持ちました。その主なアイデアは、ファイルを固定のチャンク境界で分割するのではなく、スライディングウィンドウハッシュ関数をファイル全体に実行し、ハッシュが特定の値を持つときにチャンク境界をトリガーすることです。欠点は、これにより分布上の可変長チャンクが得られることですが、利点は、チャンク分割がファイルのバイトシーケンスの挿入や削除に対してはるかに回復力があることです。 anyway、その一部として FastCDC の論文に出会いました。そのビルディングブロックは GEAR ローリングハッシュです。私は速いものが好きなので、論文で公開されている逐次アルゴリズムをSIMDアルゴリズムに変換する方法を理解するのにかなりの時間を費やしました。その結果を gearhash として公開しました。これは、SSE4.2 および AVX2 の最適化を備えた小さなRustクレートです。私がこのクレートを書いたとき、ARM64 は最適化する価値のあるターゲットではありませんでした。AWS は1年間ARM64インスタンスを提供していましたが、Cortex-A72コアをベースにした最初の世代のGraviton A1ファミリのみで、汎用コンピューティングよりもスケールアウトワークロード向けにマーケティングされていました。Graviton2、競争力のあるコアを持つ最初の世代は、私の最初のコミットと同じ月に re:Invent で発表され、2020年5月まで一般提供されませんでした。Apple は2020年11月にM1を発表しました。 今日まで、多くのことが変わりました。Apple はARM64を一般消費者向けハードウェアに普及させました。AWS はさらに数世代のGravitonを出荷しており、3年間連続で追加した新しいCPU容量の半分以上がGravitonであると述べています。GitHub Actions は2025年に公開リポジトリ向けの無料ARM64ランナーを追加しました。 これらのマシンのすべてで、gearhash クレートはスカラーループにフォールバックしていました。それに加えて、gearhash は当初私自身以外にほとんど本番ユーザーがいませんでしたが、それ以来、Xetクライアントのコア部分となり、Hugging Face の大規模ファイル用ストレージプロトコルであり、Git LFS をデフォルトとして置き換えました。gearhash にとっては、これは1日あたり10,000から20,000回のダウンロードが行われていることを意味します。このクレートへの新たな関心は、さらにどこまでプッシュできるかを見つけるモチベーションを与えてくれました。 並列化の鍵となった洞察 ギアハッシュカーネルは、64ビット符号なし整数に対する逐次関数として定義されています。 hash = (hash << 1).wrapping_add(table[byte as usize]); この2つのプロパティがベクトル化を困難にしています。 それは逐次的な依存関係チェーンです。各バイトのハッシュは前のバイトに依存します。単一ストリームから抽出できるデータ並列性はありません。 テーブルルックアップはギャザーです。256 × 8バイトは2KBであり、レジスタ内パーミュートには大きすぎます。各バイトは実際のロードを必要とします。 この問題にしばらく頭を悩ませた後、最初のプロパティに関する観察をしました。ハッシュは64ビット幅で、バイトごとに1ビット左シフトされるため、64バイト後には開始値は完全にシフトアウトされます。これは、バッファの任意のオフセットからハッシュを hash = 0 で開始し、64バイトでウォームアップすれば、それ以降のハッシュは最初からのパスとビット同一になることを意味します。 これにより、チャンクをストリップに分割できます。レーン0を実際の入力ハッシュでシードし、他のすべてのレーンをそのストリップの前の64バイトをハッシュすることでシードし、すべてのストリップをロックステップで実行します。レーンが一致を報告した場合、最も早い一致がどれかを特定する必要があります。実装の複雑さのほとんどはここにあります。 NEONへのポート開始 SSE4.2実装から直接ポートすることから始めました。aarch64::uint64x2_t は2つの64ビットレーンであり、x86_64::__m128i と同じなので、SSE4.2構造はほぼ機械的にマッピングされます。マッピングされなかった唯一のことはマスク抽出です。NEONには pmovmskb のような同等のものがないため、レーン比較結果をスカラーレジスタに入れるには、ナローイングシフトとムーブが必要になります。これを小さな movemask ヘルパーにラップしました。 結果は残念なものでした。0.92倍、スカラーコードよりも遅くなりました。その理由を理解するには、ARM64でのループ伝播遅延を見てみる必要があります。 イテレーションごとに、NEONバージョンは次のことを行います。 add.2d v1, v1, v1 ; h << 1, LLVM は自身への加算として発行します add.2d v1, v1, v_g Appleコアでは、これらのそれぞれが約2サイクルかかります（Dougall Johnson のM1テーブルによると）、したがってイテレーションあたり約4サイクルです。イテレーションは2バイト（レーンあたり1バイト）をカバーするため、バイトあたり約2サイクルになります。 スカラーバージョン hash = (hash << 1) + table[b] は、単一のシフトレジスタ加算にコンパイルされます。 add x0, x1, x0, lsl #1, 約2サイクルの遅延があります。これもバイトあたり約2サイクルです。 これは、ベクトルバージョンがクリティカルパスの単位あたりでスカラーバージョンと同じ量の作業を行いますが、それに加えてロードとマスク抽出のコストを支払う必要があることを意味します。これでは先に進めません。 NEONで勝つには、依存関係チェーン自体を短くする必要があります。 チェーンを短くする チェーンが2バイトあたり2オペレーションの場合、なぜそれを4バイトあたり2オペレーションにしないのでしょうか？バイトごとの更新を2ステップ書き出し、それを乗算します。 h₁ = (h << 1) + g₀ h₂ = (h << 2) + (g₀ << 1) + g₁ これにより、h₂ は単一のシフトと単一の加算によって h に依存します。ただし、G = (g₀ << 1) + g₁ を事前に計算する必要があります。G はテーブルルックアップのみに依存し、h には依存しないため、クリティカルパスから外れます。 結果: 0.92倍 → 1.13倍、改善しましたが、まだ期待の2倍にはほど遠いです。 アセンブリに隠された理由 add.2d v2, v1, v1 ; h << 1 add.2d v2, v3, v2 ; h₁ = (h<<1) + g₀ shl.2d v1, v1, #2 ; h << 2 add.2d v3, v3, v3 ; g₀ << 1 add.2d v1, v1, v4 ; (h<<2) + g₁ <-- h チェーン上 add.2d v1, v3, v1 ; ... + (g₀<<1) <-- h チェーン上でも LLVM が単に再結合したことが判明しました！私は (h << 2) + (G₀ + G₁) と書きましたが、それは ((h << 2) + G₁) + G₀ を発行しました。これはもちろん合法的な変換ですが、依存関係チェーンに2番目の加算を戻します。 やや不正な修正 コンパイラが合計を再結合するのを止めることはできませんが、1つを（止めようと）することができます。結合された項は2つのテーブルルックアップから構築され、それらは anyway 一般的なレジスタに到着するため、結合はそこで発生させることができます。 let (t00, t01) = (table[b00 as usize], table[b01 as usize]); let (t10, t11) = (table[b10 as usize], table[b11 as usize]); // スカラーレジスタで2つのテーブルエントリを結合すると、ベクトルオペランドが // 不透明になり、加算がループ伝播する `h` チェーン上の2つの依存ベクトル加算に // 再結合されるのを防ぎます。 let g1 = vcombine_u64( vcreate_u64((t00 << 1).wrapping_add(t01)), vcreate_u64((t10 << 1).wrapping_add(t11)), ); let h2 = vaddq_u64(vshlq_n_u64::<2>(h), g1); アセンブリを確認すると、チェーン上には shl.2d → add.2d のみが表示されました。 結果: 1.13倍 → 1.46倍、ようやく meaningfully に高速になり始めましたが、まだ十分ではありません！ 遅延バウンドからスループットバウンドへ 一度に2ステップまでアンロールした結果に励まされ、4つの中間状態でも同じことを試みました。それぞれが still h から直接計算されます。 let h1 = vaddq_u64(vshlq_n_u64::<1>(h), g[0]); // hk == (h << k) + g[k-1] // ... let h4 = vaddq_u64(vshlq_n_u64::<4>(h), g[3]); これにより、バイトあたりの依存関係チェーンの長さが再び半分になるため、さらに大きなステップを期待していました。しかし、測定すると、まったく違いはありませんでした。この時点で、限界はもはやイテレーション間の遅延ではなく、単にCPUのスループットである可能性が高いと疑いました。その仮説に従って、私の焦点は命令数を減らすことに移りました。ループは1バイトあたり2回のロードを行うようになりました。1つはバイト用です。