SHA-1の衝突検出を高速化するため、ソルバーでSIMDコードを生成した
Solving for faster SHA-1 collision detection
gitサーバーでpack検証が遅い原因は、衝突検出付きSHA-1が通常の29%の速度しか出ないことだった。既存実装にハードウェア命令を導入して倍増させた後、StevensとShumowの論文を読み、衝突検出フィルタをSIMD向けに再設計。ソルバーが条件をベクタレーンに割り当てるコード生成器を備えたRustクレートsha1dcを開発し、通常SHA-1の68〜81%の速度を実現。gitのpack検証を最大2倍高速化できる。
衝突検出付きSHA-1が通常のSHA-1より時間を費やすのは、このフィルタの部分である。
HNでの議論
10- gleenn
これはめちゃくちゃクールに思えるけど、同時に複雑すぎるようにも聞こえるな。記事は thorough だったけど、アルゴリズムが複雑すぎて著者自身がまともなテストすら書けないってのは気がかりだ。動的に大きなバイナリ式を組み合わせて扱っているとなると、大事な何かをうっかり飛ばしてしまうんじゃないかとすごく心配になる。速くすることはできるだろうけど、それを証明できないなら、しかもセキュリティ関連なら、もっと証明を詰める必要があるんじゃないかな。SHA1がすでに破られているとしてもね。
- rurban
git本体はもうRustを受け入れてるのか？ packチェックが2倍速くなるのは、みんなに影響するから価値があるよな。2.55からもうやってるって聞いたけど。
- someonebaggy
この文章、ほとんどAIっぽく感じるけど、AIじゃないんだよな。なんでだろう？