- SIMDは最高性能のソフトウェアだけのための複雑な技法ではなく、連続したデータを複数値ずつ処理して普通のループを高速化する、日常的な最適化手段である
- 一般的なSIMDコードは、定数のブロードキャスト、ベクトル単位の走査、並列演算、結果の縮約・保存、スカラーの末尾処理という5段階の構造に従う
- Ghosttyのコードポイント検索ループは、一度に4・8・16個の
u32を比較し、理論上のスループットをARM NEONでは最大4倍、AVX2では8倍、AVX-512では16倍まで高められる
- AVX2対応Intelデスクトップでのターミナル全体のスループットは約5倍高速化し、対応するベクトル幅がない場合や入力が残った場合は、従来のスカラーのループが入力全体または残りを処理する
- コンパイラの自動ベクトル化は単純なループでも機会を逃すことがあるため、まず最適化後の出力を確認しつつ、重要なホットループでは明示的なSIMDによって挙動と性能を予測可能に保てる
SIMDが行うこと
- SIMDは、CPUが1つの命令で複数の値を並列処理できるようにする
- バイトを1つずつ比較する代わりに、一度に4個、8個、またはそれ以上を比較できる
for (byte in bytes)、for (character in string)、for (value in array)のようなループをベクトル幅単位の処理に変える機会がある
- データが数百・数千・数百万バイトあるなら、並列幅に応じて局所的に4倍、8倍以上の高速化を得られる
- データが数個や数十個にすぎないなら、SIMDを適用する価値はない
- simdutfとsimdjsonは複雑なSIMD技法を使っているが、日常的なSIMDまでこの程度に複雑である必要はない
- 例ではZigを使うが、5段階構造は他の言語にも適用でき、SIMD命令のサポート方法は言語ごとに異なる
繰り返し現れる5段階構造
- 必要な定数をすべてのレーンにブロードキャストし、必要ならベクトルアキュムレータを初期化する
- 入力を一度にベクトル幅のサイズずつ走査する
- すべてのレーンで比較や算術演算を並列実行する
- アルゴリズムに合わせてベクトル結果を縮約または保存する
- 完全なベクトルに収まらない残りは、従来のループである**スカラーの末尾（scalar tail）**で処理する
- この構造に慣れると、通常のループを同じ5段階に分解できるため、SIMDを書くこともスカラーのループと同じくらい単純になる
- この構造で簡潔に表現できないなら、当面はSIMDの適用を見送るのが適切である
Ghosttyの実際の検索ループ
- Ghosttyは、デコード済みのコードポイント配列から
0xF以下の値に出会うまでデータを消費する
- ターミナルデータの大半は出力する通常文字なので、それらをまとめて処理する
- ループは次に出力可能な区間の終端をできるだけ速く見つける
- 元のスカラー実装はコードポイントを1つずつ検査する
while (end < cps.len and cps[end] > 0xF) end += 1;
- ベクトル実装はCPU専用の組み込み関数を使わず一般的なベクトルを使い、スカラー実装よりコードが12行増える
- 期待されるスループット向上はベクトルのレーン数に対応する
- ARM NEONとApple Silicon: 最大4倍
- 大半の最新x86 CPUがサポートするAVX2: 最大8倍
- 一部のIntel CPUとAMD Zen 4以降がサポートするAVX-512: 最大16倍
- AVX2対応Intelデスクトップで、ターミナルプログラムの入力から最終的なターミナル状態までを測定した全体スループットは約5倍高速化した
- SIMD周辺の処理があるため、理論上の高速化をすべて得られるわけではない
- C0制御文字は
0xF以降にも存在するが、0xFはこのGhosttyのコードパスで使う基準である
1段階目: 定数のブロードキャスト
if (simd.lanes(u32)) |lanes| {
const V = @Vector(lanes, u32);
const threshold: V = @splat(0xF);
- Ghosttyの
simd.lanes(u32)は、対象CPUが同時に処理できるu32の個数を返す
- それぞれの値は**レーン（lane）**と呼ぶ
- ARMは4、AVX2は8、AVX-512は16を返す
- 使えるベクトルサイズがない場合は
nullを返し、SIMDコードをスキップする
@Vector(lanes, u32)は、そのレーン数を持つベクトル型を生成する
lanesが8なら、1つのVに並列処理できるu32が8個入る
- ベクトル比較では両側ともベクトルである必要があるため、
@splat(0xF)が0xFをすべてのレーンに複製する
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
- このアルゴリズムにはベクトルアキュムレータは不要だが、別のアルゴリズムではこの段階でアキュムレータを初期化できる
2段階目: ベクトルを1つずつ走査
while (end + lanes <= cps.len) : (end += lanes) {
const values: V = cps[end..][0..lanes].*;
lanesが8なら、値が少なくとも8個残っている場合だけループに入り、8個をvaluesにロードする- 各反復の終わりに、
endを1ではなくレーン数だけ増やす
- 完全なベクトルをロードできる必要があるため、値が5個しか残っていないなら8レーンベクトルは読まない
- ベクトルに入らない値は、5段階目のスカラーの末尾が処理する
3段階目: すべてのレーンを並列比較
const greater_than_threshold = values > threshold;
valuesとthresholdがどちらもベクトルなので、>は対応する各レーンを1つのベクトル演算として比較する- 8レーンなら、
cps[end] > 0xFに相当する比較8個を並列に実行する
values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold: { 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
- 明示的な内部ループはなく、結果はレーンごとのブール値を含むベクトルである
- 比較だけでなく、加算、乗算、最小値、最大値など、ベクトル型がサポートする演算にも同じ構造を適用できる
- 比較そのものは1つのベクトル演算だが、ベクトルのロード、結果の縮約、失敗したレーンの検索には追加命令が必要である
4段階目: ベクトル結果の縮約
if (@reduce(.And, greater_than_threshold)) continue;
@reduce(.And, ...)は、すべてのブール値をandで結合して単一のブール値にする- すべてのレーンが
trueなら次のベクトルへ進み、1つでもfalseなら失敗した正確な位置を探す
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
@bitCastはブールベクトルを1レーンあたり1ビットの整数マスクに変換する
1は値が0xFより大きいことを意味する0は比較に失敗したことを意味する
- マスクを反転すると失敗した比較が
1になり、@ctzは最初の1より前にある0ビットの数を数える
values: { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask: { 1, 1, 1, 0, 1, 1, 1, 1 }
~mask: { 0, 0, 0, 1, 0, 0, 0, 0 }
- この例では
@ctz(~mask)は3を返し、endを最初の制御文字である0x0Aがある3番レーンへ移動させる
- 結果の縮約は、5段階の中でアルゴリズムごとの差が最も大きい部分である
- 合計はベクトルアキュムレータを単一の数値に縮約できる
- 変換はベクトル全体を出力バッファに保存できる
- この検索はビットマスクを作って特定レーンの位置を見つける
5段階目: スカラーの末尾処理
while (end < cps.len and cps[end] > 0xF) end += 1;
- 入力長がベクトル幅の正確な倍数でない場合、元のスカラーのループが残りを処理する
- 8レーンのベクトルループの後には、0個から7個の値が残る可能性がある
simd.lanes(u32)がnullであるCPUではSIMD区間をスキップし、スカラーのループが入力全体を処理する- 元の実装が残りの処理と互換性フォールバックを同時に担う
- 汎用ベクトルはCPU別の構文を取り除くだけで、CPU別のコード生成までなくすわけではない
- Zigは対象で有効化された命令セットにベクトル演算を変換する
自動ベクトル化が取りこぼすもの
- コンパイラは、複雑な制御フローのない規則的な算術ループのような単純なコードを自動ベクトル化できる
- 手動でSIMDを書く前に、スカラー版を最適化オプション付きでコンパイルし、生成されたコードを確認すべきである
- プロダクションコンパイラはベクトル化の機会を頻繁に逃しており、自動ベクトル化は数十年にわたって研究されてきたが、最近の研究もこの問題から出発している
- 5倍の高速化が重要になるほどのループなら、ベクトル化を明示的に書くことで挙動を予測可能に保てる
- 関係のないコード変更やコンパイラ更新によって、ベクトルループが静かにスカラーのループへ戻ってしまう状況を避けられる
開発者が身につけるべきSIMDの範囲
- 大量の連続データを検索・比較・計数・変換するホットループを見つけたら、ベクトル幅単位の処理を検討できるべきである
- 日常的なSIMDは、定数の準備、ベクトルのロード、並列演算、結果の縮約、スカラーの末尾という規則的な形に従う
- 言語がSIMDをうまくサポートしていれば、アセンブリやCPU別の詳細を直接知らなくても性能を改善できる
- すべての開発者に必要な水準は、複雑な
simdutf・simdjson式の技法ではなく、SIMD適用の機会を認識し、共通構造を活用できる程度である
1件のコメント
Hacker Newsの意見
良い記事だが、SIMDは理解しやすく、forループと同じくらい簡単に書けると言って始めておきながら、最初の例でいきなりスカラーコード1行を12行に増やしてしまうのは説得力に欠ける
むしろSIMDは難しいが、その見返りには価値があると率直に言ったほうがよい。初心者向けなら、第1段階から
broadcastのようなSIMD専用用語を説明なしで使うべきではないし、スカラーの端数処理を説明した第5段階は良い構成だったハードウェアが一度に処理できる項目数を把握し、そのサイズで処理を束ね、結果を再び展開し、余りの項目を別途処理し、定数も複製したベクトルにしなければならない。それぞれは難しくないが、作業量が増えて面倒になる
いちばん気に入っていた機能は、ある境界条件の下でコンパイラがforループを自動並列化する
par(; ; )だった本当に複雑なテーマなら、より小さく単純な部分に分けたうえで、急な学習曲線を登れるよう順序をうまく構成し、それだけの価値があると納得させる必要がある
よりよい助言は、みんなが配列プログラミングを知るべきだということだ。SIMD最適化にはたいていその考え方が必要で、パックドSIMDにだけ特化した手法は意外と少ない
配列プログラミングはコンパイラが自動ベクトル化しやすいため、SIMDを直接書かなくても概ね高速なコードを生成してくれる
経験は多くないが、Juliaは似たようなベクトル化能力を備えた、よりモダンで表現力の高い言語に最も近いように見える
ここ数日、生物情報学プロジェクトの行列演算をAVX-512で最適化したが、非常に満足している
ほとんどのアプリケーションでは、大規模データセットをメモリから読む過程がボトルネックなので、複数の演算のために何度も読む代わりに、AVXレジスタと融合カーネルで一度にすべて処理できる。5倍の高速化も珍しくなく、直接イントリンシクスを使ったが、
wideクレートを使えば一般的な演算はとても簡単になる: https://docs.rs/wide/latest/wide/圧倒的大多数の開発者はSIMDを学ぶ必要などまったくない。なぜ、すべての開発者がこれを知らなければ本物の開発者ではないかのような誤解を招くのか疑問だ
タイトルは「みんながSIMDが適用されない時点を知るべきだ」に変えたほうがよい
現代のコンパイラはベクトル化が非常に上手でも、仮定が1つ増えたりデータ依存の分岐が1つ入ったりするだけで、突然スカラーコードに後退する。SIMDの書き方より、コンパイラの最適化レポートの見方を知るほうが価値があるかもしれない
問題を特定できたとしても、結局は「残念だったね」で終わる
去年、オーディオシンセサイザーを作りながらx86とARMのSIMDを学び始めた: https://github.com/seclorum/SIMDSynth
マルチティンバー・ポリフォニックシンセサイザーの構造では、同じ処理を複数のデータフローに適用するため、SIMDの原則を学ぶのに非常に向いていた。ただしデバッグはかなり難しく、各処理パイプの状態を理解できるシミュレータが切実に欲しかったし、SIMDツールを調べるにもまた大きな投資が必要そうだ
記事は良く、より多くの言語がSIMDをサポートしてほしいとは思うが、最も人気のある2つの言語がSIMDをネイティブにサポートしていない状況で、「すべてのプログラマが知るべきだ」という言い方はやや奇妙だ
自分でSIMDを書かない、あるいはAIに任せるつもりでも、どんな処理がどんなハードウェアでSIMDによって速くなりうるかは知っておくべきだ。そうすれば、SIMD適用が可能になるようアルゴリズムとコード構造を設計できる
データ依存性の影響、ベクトル要素幅を広げるコストとその回避法、条件や分岐をマスクに変える方法、「除算命令はない」といった特性は、SIMDを少しでも実際に使ってみるとずっと身につきやすい
大きな連続データをまとめて検査・変換する場合にはうまく機能するが、入力の数バイトごとに判断を下す必要があるなら、スカラー方式と同等かそれ以下になることもある。SIMDは魔法の加速ボタンではない
The Witness開発チームが、実際の性能問題をSIMDで解決する過程をCasey Muratoriが説明した有用な動画: https://www.youtube.com/watch?v=Ge3aKEmZcqY
性能のための垂直統合の好例であり、一般的な抽象化がなぜ存在し、なぜ汎用的である必要があるのかを理解したうえで、特定のユースケースでは問題定義からSIMDまで垂直に統合して大きな利益を得る過程を示している
SIMD のような微細な最適化に入る前に、まず データ構造とアクセスパターン を真剣に見直すべきだ
以前の Zig コードに SIMD を適用したことがあったが、データ構造モデルが最適化とは正反対で、壊れたエンジンの付いたボロ車に高性能レーシングタイヤを履かせるようなものだった。性能も測定せず、メモリ割り当ての位置も考慮しない、典型的な早すぎる最適化だった
今ではデータを SQL テーブルのように捉え、潜在的な主キーとアクセスパターンを中心に構造を設計している。以前はヒープ上の別の構造体を指すツリーを使っていて、連結リストの欠点、多数のヒープベクタの断片化、遅い生成・解放コストをすべて抱え込み、
Dropだけでも実行時間のかなりの部分を使っていたツリーはいつでも線形化できるので、アクセス・挿入パターン、実際にツリーなのか別のグラフなのか、
Vecまたは複数のVecの構造体として保存するかを検討する。その結果、コードはより高速で単純になり、データが同種配列に集まることでコンパイラの SIMD 最適化や L1 キャッシュを活用しやすくなり、必要なときには自分で 分岐なしの SIMD コード も書けるようになる関連資料: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...
実際のボトルネック区間では、メモリ割り当て、仮想関数テーブルの参照、過剰な間接参照を避けるべきだ。C++ の
vectorも、予期しない割り当てを呼び出す可能性があるなら、常に最善とは限らない一方で、データ指向コードはほとんど常にスレッディングと SIMD を容易にサポートする
興味深いことに、CPU コードも結局は GPU スタイルで書くことになり、オブジェクト配列の代わりに Parquet 風の 配列の構造体 を使うのが一つの方法だ