55 GiB/sのFizzBuzz（2021）
(codegolf.stackexchange.com)- Code Golf Stack ExchangeのHigh throughput Fizz Buzzは、FizzBuzzの出力をどれだけ高速に生成してpipeへ流し込めるかを競う性能実験で、
<program> | pv > /dev/nullのスループットでスコアを付ける - 有効な出力には、単純なASCII、
\n改行、正確なFizz/Buzz/FizzBuzz、少なくとも2^58以上または実質的に無限の出力が必要で、pvにだけ検出されるヌルバイトのトリックは禁止 - 上位の実装は
% 3、% 5、printfループを捨て、15行パターンのアンロール、固定幅の数値処理、大きなバッファ、並列化、ゼロコピー出力でボトルネックを減らしている - 紹介されているx86-64+AVX2 assemblyの回答は、LinuxとAVX2を前提に
vmsplice、L2 cache、huge page、FizzBuzzバイトコードインタプリタを組み合わせ、約61GiB/sを記録 - 結果はCPU、pipe buffer、
pvのバージョン、CPU affinity、mitigation設定に大きく左右され、質問者のマシン基準での最高スコアはDavid FrankのC++実装の約1.7Tb/sとしてまとめられている
FizzBuzzで押し切ったスループットの限界
- 核心はFizzBuzz問題そのものではなく、非常に単純なテキスト生成において、CPU計算、メモリコピー、pipe I/O、カーネル境界のどこが最初にボトルネックになるかを確認することにある
- 基準となる素朴なC実装は
% 3、% 5、printfを使い、平均的なマシンで約170MiB/s程度を出す - 質問者は同じマシンで3GiB/s以上の実装を見たことがあり、コミュニティにさらに高いスループットの限界を探ってほしいと考えた
- スコアは質問者のデスクトップで測定された
- AMD 5950x、16C/32T
- 64GB 3200MHz RAM
- CPU mitigations無効化
- 言語別の表には、asm 60.8GiB/s、C 20.9GiB/s、Julia 15.5GiB/s、Go 6.8GiB/s、Java 5.8GiB/s、Rust 3.4GiB/s、Ruby 1.7GiB/s、Python 0.5GiB/sなどが含まれる
- ais523のx86-64+AVX2 assembly回答は単一スレッドでの最大性能を狙ったもので、作者のマシンで約31GiB/s、質問者の集計で約61GiB/sを記録
- David FrankのC++実装は質問本文基準で現在の最高スコアとして約1.7 Terrabit/sを記録しており、別のC++20実装はAMD Ryzen 9 7700Xで283GB/sを出したとしている
出力ルールとベンチマーク条件
- 有効な出力条件は厳しい
- 出力は正確なFizzBuzzでなければならない
- ASCII文字1文字あたり1バイトでなければならない
- 改行は
\nのみ許可される \r\nは許可されない- 出力は少なくとも
2^58以上の非常に大きな数まで続かなければならない
- ベンチマーク方法そのものもスループットに影響する
pvとLinux pipe bufferは、基本的に64Kバッファを使うものとして議論されている- CPU sibling coreの配置によって、生成プログラムと消費プログラムの間のL2 cache経路が変わる可能性がある
tasksetでCPU配置を強制して比較できる
assembly実装の最適化手法
- assembly実装の核心は、計算よりも出力コピーのコストを減らすことにある
writeを使うと、ユーザー空間からカーネル空間へコピーするコストが大きくなる- 作者は、
writeベースに変更すると性能が5分の1に落ちると書いている vmspliceにより、pipeがプログラムのバッファを参照するようにしてコピーを減らす
- FizzBuzz計算は3段階に分かれる
- 第1段階は初期文字列をハードコードする
- 第2段階は2〜5桁の数字を比較的直接的なAVX2ルーチンで処理する
- 第3段階は6〜18桁の区間をFizzBuzzバイトコードインタプリタで処理する
- 第3段階のメインループは、4クロックサイクルあたり64バイトの出力を目標にする
- バイトコード1バイトが出力1バイトを生成する
- 32バイトのバイトコードをロードし、
vpshufb、vpsubbなどで32バイトの出力を作る - 行番号は近似値とバイトコード補正で処理し、各行ごとに一般的な数値変換を行わない
- この実装はプラットフォーム依存性が大きい
- 比較的新しいLinuxが必要
- AVX2をサポートするx86-64プロセッサが必要
- 標準出力がpipeでない場合は起動時にエラーを出す
spliceが絡むパイプ構成では、誤った出力を出す場合があるとしている
他の言語実装が採った共通戦略
- C、Go、Java、Rust、Python、Julia、Ruby、C#の実装も似た最適化方針を繰り返している
- 15行のFizzBuzzパターンをアンロールする
- 数値文字列変換の回数を減らす
- 大きなバッファにまとめて書く
- スレッドやgoroutineで生成処理を並列化する
- 出力順を維持するためにbarrier、channel、queue、mutexを使う
- この結果は単純な「言語性能」の比較とは見なしにくい
pvのバージョン、pipeサイズ、vmspliceの利用可否、CPU affinity、huge page、compiler最適化、memcpyのインライン化有無がスループットを大きく変える- 一部の回答は特定のマシンでは速いが、別の環境では同じ数値を再現できなかったというコメントがある
扱っていない範囲
- 入力ノートに一部のsource chunkが長さ・コスト制限により省略されたと示されているため、全46件の回答とすべてのコード・コメントを漏れなく扱っているわけではない
- 省略された範囲には、一部の言語別投稿、長いコード本文、詳細なチューニングログ、コメントでの議論が含まれる可能性がある
1件のコメント
Hacker Newsのコメント
Linuxが、あるプログラムから別のプログラムへパイプされたデータをL2キャッシュ内にだけ留め、主記憶に触れずに済ませられるという点が最も印象的だった
普通のLinuxカーネルの複数の部分がかみ合って、こうした高速経路を実現しているのは、驚くべきシステムアーキテクチャ設計だと思う
Mac OSXのMachポートやWindowsのNamed Pipesでも、こうしたことが可能なのか気になる
「ais523 - high effort answers」というユーザー名にふさわしく、プログラムを実行できなかった人にもかなり手の込んだコメントを残しており、結論はこうだった
「おそらくプログラムが何らかの拍子にASLR有効の状態でコンパイルされてしまったのだと思います。この場合、動的リンカがBSSセグメントの4MiBアラインメントを尊重せず、私の
.alignを事実上無視してしまい、それがバグの原因になっているようです」この記事が再掲されるたびに、このコメントを見て笑ってしまう
「@chx: 私にはすでに修士論文があります。こっちのほうが難しかったです。– ais523 - high effort answers Oct 29, 2021 at 1:17」
Rust、Python3、Cで最適化なしの単純実装を試してみた。単純なif/else/whileと標準出力への出力だけを使っている
Rust -> 23.2MiB/s
Python3 -> 28.6MiB/s
C -> 238MiB/s
Rustの性能がなぜPython3と同じような範囲なのか、分かる人はいるだろうか。Cにもっと近いと思っていた
Cに近い性能を出すには、このロックを自分で扱う必要がある可能性が高い
let mut lock = stdout().lock();write!(lock, "hello world").unwrap();そして標準出力のバッファサイズもCに合わせる必要がある
https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
1msの遅延を入れて数字を数えるCプログラムで、2列目は前回の
read()からの経過時間を示している$ ./out | rtss4.7ms 4.7ms | 14.7ms | 24.7ms | 34.7ms | 44.8ms exit status: 0すべて一度に書き込まれているのが分かる。ターミナルを割り当てると各行ごとに出力される
$ rtss --pty ./out0.8ms 0.8ms | 11.9ms 1.1ms | 23.0ms 1.1ms | 34.1ms 1.1ms | 44.3ms exit status: 0Rustにはこのような適応的動作がないため、ターミナルかどうかに関係なく常に後者のように振る舞う
技術的には標準出力を常にLineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html)でラップしており、改行を含む書き込みを見ると毎回フラッシュする。スループットを最大化したいなら、BufWriterでラップするなどして複数行をまとめて書く必要がある
--release、Cは-O3でコンパイルすべきすべてがアセンブリで書かれていたらどれほど速かったのか、気になってくる
オーディオ開発では、DSPコードをアセンブリで書くことは非常によくある
極端なアルゴリズム研究、Linuxのシステムコールに関する深い知識、プラットフォームごとの最適化が組み合わさって初めて可能になる。作者のAlex Smith本人の言葉を借りれば:
「@chx: 私にはすでに修士論文があります。こっちのほうが難しかったです。」
単に「アセンブリでやればいい」で済むような話とはまったく次元が違う
「そうですね。私はUniversity of Washingtonに通っていたのですが、中退してGeoworksという会社に就職し、5年間アセンブリ言語プログラミングをしていました。私たちGeoworkerは、オペレーティングシステム全体、ライブラリ、ドライバ、アプリ、つまりデスクトップOSを丸ごとアセンブリで書いていました。8086アセンブリでした！ しかも良いアセンブリですらありませんでした！ レジスタが4つしかなかったんです！ 386まで含めるならsiレジスタもありましたが。ひどいものでした。
実のところ、私たちはかなり気に入っていました。オブジェクト指向アセンブリだったからです。人間が自分を納得させて何かを好きになれるというのは驚くべきことで、これこそがこの話全体の本当の皮肉です。私たちにとってC++はローマ的退廃の極みでした。もっと食べるために吐きに行くようなものだったのです。彼らにはIFがありました！ 私たちにはjump CX zeroがありました！ 彼らには『オブジェクト』がありました。私たちにもありましたが、彼らにはそのための構文がありました。実に軟弱に見えたものです。そして当時、私たちはどんなコンパイラよりも速いコードを書けると分かっていましたし、実際そうでした！
では何が起きたのでしょう？ 会社は倒産しました。なぜか？ たぶん私はGeoworkerの全員と意見が違うでしょう。実際、こう信じているのは私だけだとも分かっています。でも理由は、私たちが1,500万行の8086アセンブリ言語を書いたからです。本当に優れたツール、世界最高レベルのツールがありましたし、信じてもらって構いません。そういうものは絶対に必要です。でも、ある時点が来ると……
問題は、アリがガレージの床を横切ってまっすぐ歩こうとするところを想像してみてほしい、ということです。アリは直線では進めません。私たちは視野が広いので、それが分かります。アリがあちこち回って、あの石に合わせて局所最適化し、今度はあっちへ向かう様子が見えるでしょう。
私たちが巨大なアセンブリ言語システムを書いていたとき、まさにそうでした。最終的にMicrosoftは、私たちのものよりはるかに速いモバイル機器向けプラットフォームを出しました。私はデバッガを持って入っていって、『何だこれは？ なぜこうなる？ レンダリングが本当に遅いし、引っかかっているぞ』と思いました。中を見てみると、画面を再描画するたびに、あるタイトルバーが140回もレンダリングされていたのです。タイトルバーだけではありませんでした。あらゆるものが何度も呼び出されていました。
私たちはもう、システムがどう動いているのか見えなくなっていたからです！
小さなシステムは最適化しやすいだけでなく、実際に最適化できるのです。つまり、グローバル最適化が可能だということです。」
http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
今日のWebサイトやソフトウェアの99%くらいは、アプリケーション性能に少し気を配るだけで、基本的な変更だけでも少なくとも50%の高速化を達成できそうに思える。適切なキャッシュ、アセット最適化、肥大化したサードパーティライブラリを同じことをする基本的なネイティブ呼び出しに置き換えること、サーバーやデータベースの適切な設定といったものだ。
数年以内にAIがリポジトリにワンクリック最適化を提供し、ベストプラクティスを適用したり、元のコードを高速なアセンブリへ書き直したりするようになるかもしれない
資源制約は、焦点の明確さをもたらしうる
この実験は面白くて有益ではあるものの、少し欠陥があるように見える。複雑な問題をどれだけ速く解けるかを評価するというより、1つのプロセスからメモリを取り出して別のプロセスに渡す効率という周辺的な問題を主にテストしている
なので2つ目のプロセスがコンソールやファイルに書き込み続けているように見えるが、技術的にはそうではない。
pv >/dev/nullの実行は本質的にはほとんど何もしておらず、write システムコールはほぼ即座に返るvmspliceは、あるプロセスのバッファ/メモリに別のプロセスがアクセスできるようにする、共有メモリに相当する機能だ。当初のコンテスト要件が曖昧だった可能性が高く、ルール上これが許されるのかは不明に思える「FizzBuzz プログラムを書いてください。実行してください。出力を
| pv > /dev/nullにパイプしてください。スループットが高いほど優秀です。」「プログラムの出力は正確に有効な fizzbuzz でなければなりません。有効な出力の間に null バイトを差し込むようなごまかしは不可です。たとえば、コンソールには見えないが pv のスループットには計上される null バイトなどです。」
そして
vmsplice(2)は実際に標準出力パイプ上にバイトストリームを作り、pv(1)はそれを/dev/nullに splice できるし、cat(1)は端末にコピーできるvmsplice(2)を使ったのはこの投稿だけではない。他の投稿者たちも、これが決して魔法の解決策ではないことを突き止めている。入出力の壁を越えた後でも、出力ページをできるだけ速く生成する作業はまだ多く残っているほとんどのコードは メモリと入出力 でボトルネックになる。複雑な問題であっても、たいていはデータをある場所から別の場所へ移す速度に阻まれ、データの計算自体に阻まれることはまれだ。GPU アセンブリの最適化に日々を費やしている身としても、まれに計算がボトルネックになる場合でさえ、それを最適化すると次はメモリがボトルネックになる
たとえば、10進数の桁上がりが自然に起こるようにする巧妙なビット表現がある
当初のコンテスト要件も、この点に関しては特に曖昧ではない。
| pv > /dev/nullでスループットを測れと明記しており、さらにこうも言っている:「アーキテクチャごとの最適化 / アセンブリも許可します。これは本当の競技ではありません。特殊な環境やプラットフォームでしか動かなくても、人々が fizz buzz を限界まで押し進めるのを見たいだけです。」
メモリ入出力 とファイル入出力を高性能に扱う方法を理解することは、すべてのプログラムとプログラマに関係するスキルだ
fizzbuzz.Sとして保存しろとあるが、拡張子 .S と .s の違いが何なのか気になるman ページによると:
file.sアセンブラコード
file.Sfile.sxプリプロセスが必要なアセンブラコード
.S）、通さないか（.s）の違いだった現代のツールチェーンでも違いがあるのかはよく分からない
.Sは人間が手で書いたアセンブリファイル、たいてい git で追跡されるファイルに使い、.sは必要なら上書きしてよい機械生成アセンブリに使う.Sを上書きしないが、アセンブリを生成するよう求めると（例:gcc -S xyz.c）、.sは上書きする以前の記事:
https://news.ycombinator.com/item?id=29031488
https://news.ycombinator.com/item?id=29413656
最初は 55 GiB/s FritzBox と読んでしまった。FritzBox はヨーロッパのドイツ語圏で人気のあるルーターだ
私の ISP も先週、まもなく提供予定の 60 GiB/s 対応 OPNSense ボックス[1] をツイートしていた
[1] https://twitter.com/init7/status/1674920410889043973
USB WiFi アダプタも挿してあり、ケーブルが切れると特定の VLAN がフェイルオーバーし、携帯電話を使って業務上重要な接続性を維持している
安くはないが、OPNSense プロジェクトを金銭的に支援しつつ、きちんとした機材が欲しいなら Deciso の機材はなかなか否定しがたい。電力効率が高く、耐久性重視の部品を使っており、単純によく動く
商用製品ラインがさらに強力になっていくのを見るのはうれしい