ハクソク

世界を動かす技術を、日本語で。

NvidiaのH100より109倍速い文字列処理

248日前原文(ashvardanian.com)

概要

  • StringZilla v4 は初のCUDA対応で、CPUだけでなくGPUでも高速動作を実現
  • Levenshtein距離などの動的計画法アルゴリズム のGPU高速化を達成
  • 新しいハッシュ関数 やバイオインフォマティクス向けの指紋生成機能を搭載
  • Apache 2.0ライセンス で商用利用も無料
  • 大規模な情報検索、DB、データレイク、バイオインフォマティクス用途をターゲット

StringZilla v4: CUDA対応SIMDファースト文字列処理ライブラリ

  • StringZilla v4 はSIMD最適化文字列処理ライブラリの最新バージョン
  • CUDAによるGPUアクセラレーション に初対応、CPUとGPU両方で高速化
  • pipでインストール可能なパッケージとして500+ GigaCUPSの編集距離計算性能
  • 情報検索、データベース、データレイク、バイオインフォマティクス 向け機能強化
  • Apache 2.0 のオープンソースライセンスで商用利用も制限なし

v4新機能一覧

  • 非暗号化ハッシュ関数、AESベースの文字列PRNG追加
  • DBMSのJOINやORDER BY向けの新しい 交差・ソートアルゴリズム
  • Levenshtein距離、Needleman-Wunsch、Smith-Waterman などの文字列類似度計算をGPU/CPUで高速化
  • MinHash による大規模情報検索・重複排除のための指紋生成
  • Python、Rust、JavaScript、Swift向けの薄いバインディング実装

動的計画法アルゴリズムのGPU並列化

  • Levenshtein距離 は$N+1$×$M+1$のマトリクスを逐次的に埋める従来手法が主流
  • 行単位ではなく 対角線（アンチダイアゴナル）単位で並列化 することでSIMD/GPUに最適化
  • 3本の対角線を管理し、各セルを独立して並列計算
  • Cell Updates Per Second（CUPS） で性能評価
    • rapidfuzz::levenshtein（CPU）: 14,316 MCUPS
    • stringzillas::LevenshteinDistances（CPU）: 13,084 MCUPS
    • stringzillas::LevenshteinDistances（GPU）: 624,730 MCUPS
    • NLTK（CPU）: 2 MCUPS
  • Pythonバインディングも極めて薄く、バインディング層での性能劣化が最小限

他ライブラリとの比較

  • CuDF は短い入力で高性能だが長い文字列ではGPUコアの活用が不十分
  • StringZillaは 1,000バイト文字列で46倍、10,000バイトで109倍 の性能向上
  • Nvidia Clara Parabricksなどの商用製品と比較しても優位性あり

バイオインフォマティクス向け拡張

  • Levenshtein距離 はDNA配列比較で利用
  • ギャップ導入・延長のコストを区別する アフィンギャップペナルティ に対応
  • Needleman-Wunsch は可変置換コストを扱い、20種アミノ酸の置換行列を利用
  • DP4A/DPX命令 による小整数のSIMD処理で高速化
  • 現状では置換行列の格納法に改善余地あり
  • 1,000配列長での性能比較
    • biopython: 303 MCUPS
    • stringzillas-cpus: 276 MCUPS
    • stringzillas-cuda: 10,098 MCUPS

新ハッシュ関数設計

  • XXH3、MurMurHash、aHash など既存の高速ハッシュ関数を参考
  • 設計目標
    • 短・長文字列どちらでも 高速
    • インクリメンタルハッシュ 対応
    • シード値の全ビット反映
    • アーキテクチャごとに 動的ディスパッチ
    • AVX2、NEON、AVX-512、SVE2 対応
    • 64/128ビット出力、SMHasher --extraテスト合格
  • AES命令 を活用し、信号混合・並列化
    • VAESENC/VAESDECで高速化
    • VPSHUFB_Z、VPADDQと組み合わせて演算ポートを分散
    • 64バイト超の入力には広いレジスタを活用
    • シードは64ビット、Pi定数を多用して均一性向上
    • インクリメンタル構築 を考慮し長さ情報の混入タイミングを調整
    • バイトごとの重みを均等に保つため、AVX-512のマスクロードやSVE2のプレディケート命令を活用
  • x86とArmでAES命令の挙動差異 ありだが、補正により高性能維持
  • StringWa.rsベンチマークで他ライブラリと比較
    • stringzilla::hash64: 短文1.84 GiB/s、長文11.23 GiB/s
    • xxh3::xxh3_64: 短文1.08 GiB/s、長文9.48 GiB/s
    • aHash::hash_one: 短文1.23 GiB/s、長文8.61 GiB/s

今後の展望・まとめ

  • ROCm（AMD GPU）対応や並列多パターン検索アルゴリズム は今後の課題
  • 2024年12月公開予定 だったが遅延、しかし機能面で大きな進化
  • 大規模データ処理の 信頼できる高速ベースライン を提供
  • 学術・商用・OSSプロジェクト での活用を推奨

Hackerたちの意見

これを数日前に公開した後、2つのことが起こった。まず、StringZillaはNvidia H100で1000バイトの入力に対して900 GigaCUPS以上にスケールすることが分かった。しかも、同じパフォーマンスが低スペックのハードウェアでも得られるのは明らかで、メモリに依存しないからHBMも必要ない。次に、ついに192の物理コアと384のスレッドを持つXeon 6 Granite Rapidsノードに移行した。そこで、Ice Lake+カーネルは現在、3 TeraCUPS以上を出していて、これは今のHopperカーネルの3倍だ。最新の数字はすでにリポジトリに入ってるよ: https://github.com/ashvardanian/StringWa.rs

RipGrepがStringZillaを使ったらもっと速くなるのか、めっちゃ気になる。RipGrep自体もすごく速いしね。

└

自分はRipGrepのヘビーユーザーじゃないから、全ての使い方については言えないけど、推測するに、普通の部分文字列検索ではあまり違いは見られないと思う。StringZillaが役立つのは、文字セット検索のところかもしれないね。

└

いや、ripgrepは部分文字列検索にmemchrクレートを使っていて、俺のベンチマークでは一般的にstringzillaより速いよ。$ rebar cmp results.csv --intersection -f huge benchmark rust/memchr/memmem/prebuilt stringzilla/memmem/oneshot --------- --------------------------- -------------------------- memmem/pathological/md5-huge-no-hash 47.4 GB/s (1.00x) 38.1 GB/s (1.25x) memmem/pathological/md5-huge-last-hash 40.3 GB/s (1.00x) 23.4 GB/s (1.72x) memmem/pathological/rare-repeated-huge-tricky 40.4 GB/s (1.04x) 42.0 GB/s (1.00x) memmem/pathological/rare-repeated-huge-match 1977.7 MB/s (1.00x) 563.3 MB/s (3.51x) memmem/subtitles/common/huge-en-that 35.9 GB/s (1.00x) 25.3 GB/s (1.42x) memmem/subtitles/common/huge-en-you 15.9 GB/s (1.00x) 9.5 GB/s (1.67x) memmem/subtitles/common/huge-en-one-space 1376.4 MB/s (1.00x) 1364.0 MB/s (1.01x) memmem/subtitles/common/huge-ru-that 29.0 GB/s (1.00x) 15.5 GB/s (1.87x) memmem/subtitles/common/huge-ru-not 16.0 GB/s (1.00x) 3.5 GB/s (4.53x) memmem/subtitles/common/huge-ru-one-space 2.6 GB/s (1.00x) 2.4 GB/s (1.08x) memmem/subtitles/common/huge-zh-that 31.2 GB/s (1.00x) 23.8 GB/s (1.31x) memmem/subtitles/common/huge-zh-do-not 19.4 GB/s (1.00x) 12.1 GB/s (1.59x) memmem/subtitles/common/huge-zh-one-space 5.3 GB/s (1.05x) 5.6 GB/s (1.00x) memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x) memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x) memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x) memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x) memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x) memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x) でも、全体的にはかなり競争力があると思うよ。自分でベンチマークを試したいなら、できるよ。まず、rebarを入手して[1]、次にmemchrリポジトリのルートから: $ rebar build -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' stringzilla/memmem/oneshot: 実行中: cd "benchmarks/./engines/stringzilla" && "cargo" "build" "--release" stringzilla/memmem/oneshot: バージョン3.12.3のビルドが完了 rust/memchr/memmem/prebuilt: 実行中: cd "benchmarks/./engines/rust-memchr" && "cargo" "build" "--release" rust/memchr/memmem/prebuilt: バージョン2.7.4のビルドが完了 $ rebar measure -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' | tee results.csv $ rebar rank results.csv エンジン バージョン 速度比の幾何平均 ベンチマーク数 ------ ------- ------------------------------ --------------- rust/memchr/memmem/prebuilt 2.7.4 1.14 57 stringzilla/memmem/oneshot 3.12.3 1.43 54 $ rebar cmp results.csv --intersection -f never/huge benchmark rust/memchr/memmem/prebuilt stringzilla/memmem/oneshot --------- --------------------------- -------------------------- memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x) memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x) memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x) memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x) memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x) memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x) 参考: https://github.com/BurntSushi/memchr/discussions/159 [1]: https://github.com/BurntSushi/rebar [2]: https://github.com/BurntSushi/memchr

これは面白いね、ちょっとアップボート押しちゃう。ハイパー最適化って最高だもん。でも、現実的にはこれを使う場面ってあるのかな？どんなニッチや業界、ニーズがこれで恩恵を受けるんだろう。依存関係やセットアップコストがそれに見合うのか疑問だな。文字列の問題なんてもう長い間解決済みのように思えるし。

└

この最後の作業の波は、実際にはここ2年の業界の動きによって引き起こされたんだ。生物学的な配列データの量が急速に増えていて、もっと多くのバイオテクノロジーや製薬会社が計算パイプラインをスケールアップしようとしている。具体的には、DeepMindのAlphaFold 1と2を見てみると、計算時間の大部分がPyTorchの外で使われていて、配列アラインメントを実行している。歴史的にはBLASTを使っていたけど、最近は他の研究室でも、俺のコードの一部を使ってたりする :)

こういう最適化のブログ、めっちゃ好き。教育的で、よく書かれてる。

すごくいいね、これをPostgresで使うための拡張はもうあるのかな？

└

それについては知らないな。いくつかの商用DBMSベンダーが統合を試してるみたいだけど、Postgresのエコシステムではあんまり見かけないね。このリリースでワクワクしてるのは、新しいハッシュ関数の質だよ。これまでにいくつか作ってきたけど、今まで共有する価値があるとは思わなかった。ここに2つ含まれてるのは、個人的なマイルストーンなんだ。xxHashやaHashの良さをずっと尊敬してきたから、同じくらいのクオリティのものを作りたかったんだよね。新しいハッシュはデータベースで直接役立つはずで、例えばJOINのパフォーマンスを改善することができるよ。それに、52ビットのモジュロ数学を使ったフィンガープリンティングインターフェースは新たな道を開いてくれる。使いこなすのは簡単じゃないし、どこでも使えるわけじゃないけど、ペタバイト規模のデータ取得タスクでは本当に効果を発揮すると思う。

いい仕事だね、Ash！素晴らしいまとめだ！提案なんだけど、「AESとポート並列性レシピ」の比較表に「ストリーミングサポート」と「安定した出力」（OS/アーキテクチャ間）をカラムに追加するといいと思う。それと気をつけてほしいのは、いくつかのハッシュライブラリはHasherインターフェースを通じてストリーミングをサポートしてるって主張してるけど、実際にはストリーミングとワンショットモードで異なる結果を返すことがあるんだ（パフォーマンスプロファイルも違うし）。今はモバイルだから確認できないけど、gxhashには少なくともこれらの問題のうちの1つがあったはずで、以前は使えなかったんだよね。

└

ありがとう！たぶん君が正しいね！StringZillaのISA特有のバージョン6つ（https://github.com/ashvardanian/StringZilla/blob/main/includ...）が、ワンショットとインクリメンタル構築の両方で同じ出力を返すことを確認するのにかなり時間がかかったんだ。他のプロジェクトにとってそれが優先事項だったかどうかは分からないけどね :)

今のところこれを使う予定はないけど、プロジェクトとその機能のプレゼンテーションがすごく良かったって言いたかったんだ。編集に関するちょっとした質問なんだけど、なぜ数字がアポストロフィ（'）で千の区切りとして書かれているの？[1] スイスではこの目的で使われているのは知ってるし、多くのプログラミング言語もサポートしてるよね。でも、英語のテキストでは通常カンマ（,）が使われるから、ちょっと変に感じたんだ。[1]: https://en.wikipedia.org/wiki/Decimal_separator#Digit_groupi... [2]: https://en.wikipedia.org/wiki/Apostrophe#Miscellaneous_uses_...

└

これはC++（2014）標準の愚かな選択だね。長い数字の可読性を高めるための数字区切りは、最初にAda（1979-06）がアンダースコアを使って導入したんだ。この使い方は、PL/I（1964-12）が長い識別子の可読性を高めるためにアンダースコアを導入した理由と一致しているんだ。ハイフンを使うことで生じる曖昧さを避けるためにね。多くのLISPはCOBOLのハイフンの使い方を保持しているけど、彼らもCOBOLと同様に通常は演算子を使って算術式を書かないからね。数字区切りを追加したほとんどのプログラミング言語は、Adaに倣ってアンダースコアを使っている。35年後、C++も同じことをすべきだったし、標準を更新した人たちの中でそう考えた人が嫌いだ。そうすることで、異なる言語で書かれたプログラムテキストソース間で大きな初期化された配列をコピーする際に、完全に不必要な互換性の問題を引き起こしてしまったんだ。アンダースコアに対しては、変なレガシープログラムで解析の問題を引き起こす可能性があるという不完全な議論があったけど、それはアポストロフィのレガシー使用によって引き起こされる解析エラーを避けるのと同じくらい解決が難しいわけじゃなかったよ（つまり、数字の最初の文字として数字区切りを禁止すれば、非曖昧な解析が確保できる）。

└

優しい言葉をありがとう！この場合、特定のプログラミング言語やロケール特有のフォーマットには結びついていないんだ。長い数字ではカンマがあまり読みやすくないと思うし、特に西洋の言語ではテキストの流れの中でそう感じるんだ。アポストロフィの方がクリアに感じるから、私は通常それを使ってるよ。