ハクソク

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

現代プロセッサアーキテクチャのためのアルゴリズム

291日前原文(lemire.github.io)

概要

  • Daniel Lemire教授による 現代プロセッサ の性能と最適化手法の解説
  • 命令数削減 や 並列処理 による高速化技術の紹介
  • SIMD や SWAR などのデータ並列性活用事例
  • 分岐予測 や パイプライン の効率化ポイント
  • 実測値や ベンチマーク の注意点と結論

現代プロセッサの進化と性能指標

  • Xeon Max プロセッサは 64 GB HBM を搭載し、 800 GB/s の帯域幅を実現

  • プロセッサの クロック周波数 は4 GHz以上、1サイクルは0.25ナノ秒

  • 1バイト/サイクル で4 GB/sの処理速度

  • CPUボトルネック 発生の容易性

  • トランジスタ数の増加 とその用途（コア数増加、スーパースカラ実行、投機的実行、キャッシュ拡大、SIMD強化）

    • 例: Apple M4は 4.5 GHz/28億トランジスタ、AMD Zen 5は 5.7 GHz/500億トランジスタ

命令数削減とバッチ処理

  • 命令数最小化 がバッチ処理での最適性能に直結
  • バッチ処理単位の拡大 による命令節約
  • 分岐・メモリアクセス・I/O が性能制約要因

数値パースの最適化

  • fast_float::from_chars による高速数値パース
  • 主要ブラウザやGCC, C#, Rust で採用
  • 従来手法(strtod等)より大幅に命令数削減
  • SWAR （SIMD within a register）による並列化
    • 64bitレジスタを8バイトとして扱い、ASCII判定を効率化

バッチ処理とループアンローリング

  • forループのアンローリング で1回の繰り返しあたりの命令数削減
  • 例: 乗算処理で 6-7命令→3-5命令 へ短縮

ランダムシャッフルの高速化

  • Knuthのアルゴリズム をバッチ化し、乱数生成・分岐数を削減
  • Apple M4 で大規模配列（8MB）に対して高速化実績

分岐予測とUnicode検証

  • UTF-16検証 で分岐が多いと性能低下
  • 有限状態機械（FSM） を活用し、分岐レスで高速検証
  • Apple M4 で1文字/サイクルの検証速度（4GB/s）
  • 分岐の学習限界 ：Apple M4で1万ランダム分岐まで対応可能

パイプラインとメモリレベル並列性

  • パイプライン によるレイテンシ隠蔽
  • メモリレベル並列性 ：大規模配列やSattoloのアルゴリズムでランダムアクセスパス生成
  • Littleの法則 ：レイテンシはスループットに悪影響、並列性で解消

Bloomフィルタとデータレベル並列性

  • Bloomフィルタ ：キャッシュミス半減、8ハッシュ関数利用
  • SIMD （Single Instruction, Multiple Data）：1命令で16バイト以上を同時処理
    • ASCII小文字化 や デルタ計算 などで実用
    • Apple M4 はSIMD自動ベクトル化対応

UTF-16のSIMD補正関数

  • v8（Google Chrome, Microsoft Edge） で実際に導入

  • SIMD補正関数 は非SIMD検証より高速

    • AVX2/AVX-512/NEON/SVE/SVE2/RISC-V vector など各アーキテクチャでSIMDサポート

関連プロジェクト

  • simdjson ：世界最速のJSONパーサー https://simdjson.org
  • simdutf ：Unicode処理＆Base64 https://github.com/simdutf/simdutf

ベンチマークと実測値の注意点

  • 測定値は正規分布とは限らない
  • 現実の測定値 ：最小値が信頼できる指標となる場合が多い
  • 平均値と最小値の差（マージン） を重視

結論とルール

  • プロセッサは進化し続け、幅広い並列処理が可能
  • ホットスポット最適化よりも全体の命令数削減が重要
  • 分岐が多いコードは合成ベンチマークで良く見えるが、実際には注意が必要

参考：プロセッサの分岐学習能力（Apple M4）

| size | ns/value | GHz | cycles/value | instr/value | i/c | |--------|---------:|-----:|-------------:|------------:|-----:| | 1048576| 1.59 | 4.51 | 7.20 | 8.01 | 1.11 | | 524288 | 1.50 | 4.51 | 6.76 | 8.01 | 1.19 | | 262144 | 1.31 | 4.51 | 5.90 | 8.01 | 1.36 | | 131072 | 0.76 | 4.52 | 3.43 | 8.01 | 2.34 | | 65536 | 0.49 | 4.52 | 2.20 | 8.01 | 3.64 | | 32768 | 0.49 | 4.52 | 2.19 | 8.02 | 3.66 |

Hackerたちの意見

今日、SEA 2025でこれが配信されたみたいだね。早く動画が見られるといいな！ https://x.com/lemire/status/1947615932702200138

└

残念ながら、講演は録音されてないと思うよ。

失礼なこと言いたくないけど、LLVMが同じ組織の手にあるってのは、プラットフォームへのアクセスをコントロールしているのが狂ってる理由そのものだよね。編集 - #64 E！それに、いつも言ってるけど、人間の体は人間が持ってる中で一番エラーが出やすい測定器だよ。

└

ちょっと物議を醸すかもしれないけど、Red Hatがx86_64_v1とx86_64v2を非推奨にした時、みんな泣いてたよね…。

└

もう少し具体的に教えてくれない？特定のプラットフォームに最適化しすぎて、他のコンパイラやアーキテクチャに一般化できないから？具体的に何が不満なの？

└

LLVMは具体的に誰の手にあるの？

└

LLVMとGCCはプロセッサーメーカーから直接サポートされてるよ。アップルとインテルはそれぞれ独自のLLVMバージョンを持ってるけど、GCCとの互換性を壊さず、明示的にポーティングを妨げなければ問題ないと思う。個人的にはGCCスイートしか使ってないけど、LLVMはあまり好きなコンパイラじゃないな。GCCチームが頑張るきっかけを与えてくれたことには感謝してるよ。

AppleはまだUTF-16を使ってるの？

└

これってアップルの話？それはさておき、まだ多くのプログラミング言語のランタイムがUTF-16を使ってるよ（例えば、Java、Qt、Haskellとか）。Windowsも確実にUTF-16を使ってるしね。

└

JavaScriptはそうだから、ウェブもそうだし、だからアップルもUTF-16に気を使ってるんじゃないかな。

└

NSStringは内部的にはUTF-16だよね。https://developer.apple.com/documentation/foundation/nsstrin... でも、NSStringにUTF-8の文字列を入れたり出したりするのは簡単だから、内部の表現はあんまり重要じゃないんだ。もっと重要なのは、macOSのユーザー向けの部分は全部UTF-8だってこと。例えば、UTF-8でエンコードされたUNICODE文字列リテラルをCのソースファイルにそのままコピー＆ペーストして、printf()すれば、テキストエディタやロケール設定をいじらなくてもターミナルに正しく表示されるよ。

Pentium 4は3.8GHzには達してなかったよ。1.4GHzくらいで溶けちゃった。

└

2005年に発売されたPentium 4 HT 670は、工場出荷時に3.8GHzでクロック設定されてたよ（https://www.techpowerup.com/cpu-specs/pentium-4-ht-670.c20）。Netburstは長い間続いたけど、インテルが迷走してたからね。Core Duoが2006年に出るまで。

└

ペンティアム3は最終的に1.4GHzに達したんだ。2001年に登場した130nmのトゥアラティン版ね。ペンティアム4は2000年に登場した180nmのウィラメット版で1.4GHzと1.5GHzからスタートしたけど、最終的には2.0GHzまで出たよ。130nmのペンティアム4ノースウッドは2004年に3.4GHzに達して、90nmのペンティアム4プレスコットはその後の2004年に3.8GHzに到達したんだ。

└

インテルはいくつかの異なるコアのペンティアム4をリリースして、最高で3.8GHzに達したんだ。[0] トムズハードウェアは、このノースウッドのペンティアム4を液体窒素とコンプレッサーを使って5GHzにオーバークロックしたんだよ。[1] あの頃は本当に楽しかったな。[0]: https://en.wikipedia.org/wiki/Pentium_4 [1]: https://www.youtube.com/watch?v=z0jQZxH7NgM

└

3.8に達して、しばらくの間は複数のコアの性能を超えてたんだよね。ゲームはシングルコア向けに作られてるから、マルチスレッドやマルチコアでもそうなった。エミュレーターでも同じことがあったよ。

こんなに多くの分岐がそれほどコストがかからないなんて驚きだね。

└

分岐予測器によるね。正しい分岐なら、すべてがロードされて設定される。間違った分岐なら、全部フラッシュして再度ロードすることになる。分岐予測アルゴリズムを知っていれば、それに最適化できるよ。編集：27ページに載ってるよ。

└

ブランチ予測器がすごく良くなったから、今はブランチを処理するよりもそれに頼った方が合理的なことが多いよ。例えば、最近のコンパイラは条件付きムーブ（cmov）をほとんど導入しないんだ。x86では、ほとんどの場合、単にブランチする方が速いからね。直感に反するかもしれないけど、ブランチ予測は条件付きとその句の間のマイクロオペレーションの依存関係を壊すんだ。だから、cmovの条件がロードに依存してる場合、そのロードが完了するまで待たなきゃいけない。常にスケールデータでベンチマークして、測定することが大事だよ。

自動ベクトル化のために、コンパイラに必要なコンテキストを含める努力はされてるの？

└

必要なコンテキストってどういうこと？最近のコンパイラは自動ベクトル化がすごく得意だよ。普通は、プレーンなC配列を使ったシンプルなループを書くのが、ポータブルで最適なSIMDコードを書く良い方法だと思う。私が使ってる一般的なワークフローは、論文のメモにあるベクトル表記（RIP Cilk+配列構文）をプレーンなCループに翻訳すること。コンパイラの最適化レポート（icxの場合は-qopt-report、gccは-fopt-info-vecや-fopt-info-vec-missed）で、どの最適化を考慮したのか、なぜ適用しなかったのかのフィードバックがもらえるよ。もっと複雑なシナリオでは、Cのセマンティクスを上書きするために#pragma omp simdのようなプラグマを追加するのが役立つこともある。

これはいいスライドセットだね。ダンはいい人だし。ただ、いくつか気になる点があるかな。Sqrt(N)の収束は独立性から来るもので、正規性からではないんだよね。独立性に基づくと、分散の線形性が成り立つから。{ だから、任意の分布のN IIDサンプルの合計はN倍の分散を持つけど、Nで割るとsqrt(N)になる。 } もちろん、分散や「スケール^2」とその尾部との間には高次の関係があって、統計学者はそれを「形状」と呼んでる。彼は後で依存問題や、例えばhttps://github.com/c-blake/bu/blob/main/doc/tim.mdに依存している最小dt解についても言及してるから、全体的にはいい感じだね。彼はもしかしたら声でそれをカバーしたかもしれないし。彼はまた、https://github.com/c-blake/bu/blob/main/doc/memlat.mdで使われているサトロについても言及して、メモリレイテンシの測定をしてる。ちょっと変だったのは、1バイト/サイクルが4GB/sだから「簡単にCPUバウンドになる」と言ってたことかな。私は「メモリの壁と戦ってる」感じが30年は続いてる気がするけど…スーパースカラCPUからでもね。でも彼は後でベクトル化の話もしてたし。もちろん、どんな計算をしてるかにも関係あるけど、高帯域幅メモリはnVidiaが売ってるものの大きな部分だよ。

スライドに合わせたトークってあるのかな？