AVX-512を使った`tolower()`関数

 (dotat.at)
1 ポイント 投稿者 GN⁺ 2024-07-30 | 1件のコメント | WhatsAppで共有

  • 数年前、SWARトリックを使ってtolower()を高速化する方法について書いた。数日前、Olivier Giniauxの記事で、SIMD命令を使って短い文字列を処理する最適化手法に興味を持った。この手法はRustで書かれた高速なハッシュ関数で使われている。

  • SIMD命令は短い文字列を簡単に処理できるが、メモリとベクタレジスタ間の転送が難しい点が常に悩みだった。Olivierの記事は、この問題を解決するおもしろい方法を示していた。

希望の兆し

  • 一部のSIMD命令セットは、文字列処理に役立つマスク付きロードおよびストア機能を提供している。これはバイト単位で動作する。

    • ARM SVE: 最近の大型ARM Neoverseコアで利用可能。たとえばAmazon Graviton。ただしApple Siliconでは利用できない。
    • AVX-512-BW: 最近のAMD Zenプロセッサで利用可能。AVX-512は複雑な拡張セットで、Intelでのサポートはまちまちである。

  • AMD Zen 4のマシンを持っているので、AVX-512-BWを試してみることにした。

tolower64()

  • Intel intrinsicsガイドを使って、一度に64バイトを処理できる基本的なtolower()関数を書いた。
    • *をワイルドカードとして使い、mm512*epi8を検索してバイト単位のAVX-512関数を探す。
    • いくつかのレジスタを64個の有用なバイトで埋める。
    • 大文字を小文字に変換するために必要な数値を設定する。
    • 入力文字をAとZと比較して大文字かどうかを確認する。
    • マスクを使い、大文字の場合は小文字に変換する。

一括ロードとストア

  • tolower64()カーネルを、より使いやすい関数でラップする必要がある。たとえば、文字列をコピーしながら小文字化する関数など。
    • 長い文字列については、アラインされていないベクタロードおよびストア命令を使う。

マスク付きロードとストア

  • 短い文字列と長い文字列の末尾部分では、マスク付きのアラインされていないロードおよびストアを使う。
    • マスクは先頭lenビットがセットされる。
    • ロードとストアは、マスクが追加された全幅版に似ている。

ベンチマーク

  • 複数の類似関数の性能をベンチマークした。

    • Clang 16でコンパイルし、AMD Ryzen 9 7950Xで実行した。
    • 各関数はインライン化やコード移動の干渉を避けるため、個別にコンパイルした。

  • 結果:

    • tolower64は、テストしたすべての関数の中で最も高速だった。
    • copybytes64はtolower64と同様の方法でAVX-512を使うが、それほど大きくは速くならない。
    • copybytes1はバイト単位でmemcpyを行い、Clang 11の自動ベクトル化が比較的よくないことを示している。
    • 標準のtolower()は最も遅い。
    • tolower1はClang 16でコンパイルしたバイト単位のtolower()で、自動ベクトル化は改善されているが、依然として遅い。
    • tolower8は以前のブログ記事で紹介したSWAR版tolower()で、Clangは自動ベクトル化を試みるが結果はよくない。
    • memcpyは当初は速いが、copybytes64の半分の速度まで落ちる。

結論

  • AVX-512-BWは、特に短い文字列を処理するときに非常に有用である。

  • Zen 4では非常に高速で、組み込み関数も使いやすい。

  • AVX-512-BWの性能は非常になめらかである。

  • ARM SVEをサポートするマシンを持っていないため詳しく調べられなかったが、SVEが短い文字列でどれほどうまく動作するのか気になる。

  • こうした命令セット拡張がもっと広く使われるようになってほしい。文字列処理性能を大きく向上させるはずだ。

  • このブログ記事のコードは自分のWebサイトで確認できる。

GN⁺のまとめ

  • この記事は、SIMD命令を使って短い文字列を効率的に処理する方法を説明している。
  • AVX-512-BWとARM SVE命令セットが文字列処理に有用であることを示している。
  • ベンチマークの結果、AVX-512-BWは特に短い文字列で優れた性能を発揮した。
  • この記事は、性能最適化に関心のある開発者にとって有用だろう。

関連記事

1件のコメント

 
GN⁺ 2024-07-30
Hacker News のコメント

  • Rust と LLVM のメモリモデルでは、「unsafe read beyond of death」トリックは未定義動作と見なされる

    • コンパイラは最適化のため、そのような動作は発生しないと仮定できる
    • これを避けるにはインラインアセンブリを使う必要がある

  • AMD の AVX512 実装と Intel の AVX10 競争への興味が湧く

    • AVX10 は Intel の P コア対 E コア問題を解決するためのもの
    • AMD は状況に応じて、Zen5 のフル幅、または Zen4 と Zen5 モバイルの 256 ビット・ダブルポンプを使用する
    • 大きな性能向上は Zen4 コアで起きる

  • SWAR 最適化は 8 バイト境界にアラインされた文字列にしか有用ではない

    • 非アライン文字列に適用すると元のアルゴリズムより遅い
    • アルゴリズムを 3 つの部分に分けると、より多くの命令が必要になる

  • マスクの追加がきれいに見える

    • .NET の組み込み機能で AVX512 のマスクレジスタを直接操作する方法があればよいのにと思う

  • Clang を使うと、よりよい結果が得られる

    • よりよい命令選択と、うまく展開された結果を提供する

  • 短い文字列長に対するコアループでは命令が 1 つ少ない

    • 短い文字列を高速に処理することが重要

  • ASCII を UTF-8 で大文字・小文字変換する類似の実装を C# で書いた

    • ほとんどのコードベースでは短い文字列が支配的なので、高速に処理することが重要

  • AVX512 を使ってテキストを uwu に変換する SIMD 利用例がある

  • Unicode の文字変換まで考慮すると、さらに印象的になるだろう

    • ほとんどのプログラマは ASCII にしか関心を持たないが、標準文字集合の外にも広い世界がある

  • 昔、画像の周囲に黒い縁を追加して、バッファに関する SIMD 問題を回避したことがある

    • 入力を完全に制御できないこともある