ハクソク

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

I/Oはもはやボトルネックではないのか？ (2022)

101日前原文(stoppels.ch)

概要

  • Ben Hoytのブログ記事を受けて、I/Oがボトルネックではないとする主張の検証
  • CPU最適化やベクトル化によるパフォーマンス向上の試み
  • wc -wなどの既存ツールや手動ベクトル化との速度比較
  • AVX2による手動最適化の実践と結果
  • ディスク速度とCPU速度の関係についての考察

I/Oは本当にボトルネックか？ベンチマークと最適化の実践

  • Ben Hoytのブログで「I/Oはボトルネックではない」と主張
  • 順次読み込み速度は近年大幅に向上、CPU速度は頭打ち傾向
  • cold cacheで1.6GB/s、warm cacheで12.8GB/sの読込速度を計測
  • 単一スレッドで1.6GB/sのワード頻度カウントは可能かという疑問
  • GitHubにコードを公開

Cによる最適化実装の検証

  • Ben Hoytの高速C実装をGCC 12で-O3 -march=native付きでコンパイル
  • 425MBのテキスト（聖書100冊分）を入力として実行
  • 結果は278MB/s（warm cache）と期待外れの速度
  • ホットループに分岐や早期脱出が多く、ベクトル化困難であることが判明

ベクトル化による改善

  • 小文字変換部分をループ外に出すことで330MB/sに改善（clang使用）
  • しかし、依然としてcold cacheの順次読込速度の5分の1程度
  • ハッシュマップのキャッシュミスやパーフェクトハッシュ導入などの余地もあるが、劇的な改善は難しいと判断

問題を単純化して計測

  • 頻度カウントをやめて単純なワード数カウント（wc -w）を実行
  • 結果は245.2MB/sとさらに低速
  • wc -wは多様なホワイトスペースやロケール対応で処理が重い点を指摘

AVX2による手動ベクトル化とビットトリック

  • AVX2などの新しいCPU命令セットでのベクトル化を試行
  • コンパイラの自動ベクトル化は困難、分岐の多いスカラプログラムの限界
  • VPCMPEQBでホワイトスペース位置をマスク化し、PMOVMSKBでビットマスクをintへ
  • ffs（Find First Set）命令でワード開始位置を効率的に特定

実装と検証

  • immintrin.hを使った手動AVX2実装
  • データを32バイトアラインし、ループを4回アンローリングして128バイトずつ処理
  • 実装上のバグ修正に苦戦しつつも動作確認
  • wc-avx2とwc -wで同一結果を確認

パフォーマンス結果

  • warm cacheで1.45GB/s（順次読込速度の11%程度）
  • cold cacheでもユーザーモード処理の割合が高い
  • ディスク速度の向上に対し、CPU側の処理が追いついていない現状

まとめと展望

  • ディスクI/O速度の向上は著しいが、CPU側の処理最適化がボトルネック
  • 自動ベクトル化の限界、手動最適化の必要性
  • GitHubでコード公開、さらなるビットトリックや最適化案の募集
  • 今後もCPUアーキテクチャやコンパイラ技術の進化に期待

Hackerたちの意見

I/Oがボトルネックになるのは、シーケンシャルリードのことじゃなかったよね？記事のポイントは分かるけど。
└
現代のCXL/PCIeを考えると、RAMやメモリコントローラーが徐々にI/Oになってきてるって言うのも馬鹿げてはいないと思うけど。
└
初めてデータベースの授業を受けたとき、トピックの一つが古いハードドライブのシークタイムで測定されたI/Oパフォーマンスだった。I/Oができる速度よりも早くシーケンシャルリードのためにコードを最適化することはできないから、実際にシーケンシャルでないものを最適化することに集中するのが一番なんだ。
現代のCPUのパフォーマンス限界は、シングルコアに通すことができるデータ量なんだよね。要するにmemcpy()の速度。ほとんどのx86コアではその限界は約6 GB/s、AppleのMチップだと約20 GB/sだよ。『200 GB/s』みたいな広告の数字は、全体のメモリ帯域幅、つまり全コアを合わせたものだからね。個々のコアではやっぱり6 GB/s前後が限界なんだ。だから、完璧なパーサーを書いても、それ以上は速くならない。JSONやProtobufみたいなデータの（デ）シリアライズにもこの限界が適用されるんだ。これらのフォーマットは、フィールドを読み取る前に完全にパースされる必要があるからね。でも、ゼロコピー形式を使えば、CPUは関係ないデータをスキップできるから、6 GB/sの限界を「超える」ことができるんだ。俺が作ってるLite³シリアライズ形式は、まさにこれを利用していて、いくつかのベンチマークではsimdjsonを120倍も上回る性能を出せるんだよ。https://github.com/fastserial/lite3
└
> 6 GB/s サムスンが14 GB/sのシーケンシャルリード速度を謳ったNVMe SSDを売ってるね。
└
ここでのアーキテクチャの限界って何なんだろう？個々のコアとキャッシュ、またはメモリコントローラー間のバス？
└
かっこいいね、lite3にスキーマモードを追加してメッセージサイズのトレードオフをなくすことって可能だと思う？ほとんどの人は、シリアライズとデシリアライズの両方でハードスキーマを使いたがると思うけど、スキーマなしでも動くのはいいよね。
└
あなたのシングルコアの数値は、ピークスループットとしてはかなり低いように思えます。全コアがアクティブで帯域幅を争っていると仮定しない限り、例えばデュアルチャンネルのZen 1がシングルコアで25GB/sを示しているのに対してです。https://stackoverflow.com/a/44948720 私はシングルスレッドのmemcpyのためのマイクロベンチマークをいくつか書きました。Zen 2（8チャンネルDDR4）のナイーブCでは17GB/s、非一時的AVXでは35GB/s。Xeon-D 1541（2チャンネルDDR4、私の最も弱いシステムで10年前のもの）では、ナイーブCで9GB/s、非一時的AVXで13.5GB/s。Apple Siliconのテスト（ウォーム＝新しいソースバッファを生成し、出力バッファをmemset(0)して、メモリフェンスを追加し、同じコピーを再実行）では、M3のナイーブCで冷却時17GB/s、ウォーム時41GB/s、非一時的NEONで冷却時78GB/s、ウォーム時78GB/s。M3 MaxのナイーブCでは冷却時25GB/s、ウォーム時65GB/s、非一時的NEONでは冷却時49GB/s、ウォーム時125GB/s。M4 ProのナイーブCでは冷却時13.8GB/s、ウォーム時65GB/s、非一時的NEONでは冷却時49GB/s、ウォーム時125GB/s。実際、なぜApple Siliconのウォームが冷却よりもずっと速いのかはよく分からないです。ソースバッファは各イテレーションごとに新しいランダムデータで埋められていて、メモリフェンスも使っているのに、キャッシュよりもずっと大きい16GBのソース/デスティネーションバッファでスピードアップが見られます。x86/Linuxでは冷却/ウォームのテストの違いはありませんでした。私の推測では、カーネルのページアカウンティングに関する何かで、CPUとは関係ないと思います。だから、x86で6GB/sのシングルコア制限や、Apple Siliconで20GB/sの制限を主張するのは理解できません。
└
Liteはインプレースで修正できると主張してるけど、文字列のような可変長構造体でそれがどう機能するのか気になるな。
└
> ほとんどのx86コアでは制限は約6GB/sで、Apple Mチップでは約20GB/sです。Mシリーズがx86の3倍の帯域幅を持つ理由は何ですか？
└
最近のいくつかのチップ（Apple Mシリーズも含めて）では、iGPU（統合メモリにアクセスできる）を使わないとメモリ帯域を飽和させることができないんだ。CPUコアだけでは無理だよ。だから、iGPUを使って大きなメモリ内転送やスループットが制限される計算（並列パースや圧縮/解凍のワークロードなど）を行うのが技術的に推奨される選択肢になったんだ。> ただし、ゼロコピー形式を使うと、CPUは気にしないデータをスキップできるから、6 GB/sの制限を「超える」ことができるんだ。もちろん、「スキップ」はキャッシュラインによるものだよ。キャッシュラインは、メモリスループットの観点から見て自己完結したデータのブロックだから、どんな部分を読んでも残りはタダでついてくるんだ。
└
> ただし、ゼロコピー形式を使うと、CPUは気にしないデータをスキップできるから、6GB/sの制限を「超える」ことができるよ。ただ、64バイトのキャッシュラインを一度にロードしなきゃいけないし、ほとんどのCPUはある程度のリードアヘッドを行うから、これらの利点を得るにはかなり大きな「空白」スペースが必要になるよ。典型的なprotobufよりも大きいね。
└
6GB/sをどうやって測定・計算するの？
└
実際にパース作業をしていないで、事前にパースされたデータをメモリマッピングしているだけなら、パースライブラリを上回るのはかなり簡単だよね。とはいえ、ツリーをシリアライズ可能なフラットバッファとして保存するのは確かに便利だよ。安くリリースできるからね。
NVMe SSDが最初に出たとき、俺は「今や2 TBのRAMがある！」って冗談を言ってたんだ。でも実際の冗談は俺の方で、今や一部のGPUサーバーは本当に2 TBのRAMを搭載してるんだ。すごいエンジニアリングだよね！
└
今？去年、2TBのDDR4 RAMを搭載した中古のEPYCサーバーを約5,000ドルで見つけたんだ。買っておけばよかったな。
*クラウドにいるなら、スロットリングでニッケルとダイムを稼ぐ指標になるけどね！もっと真面目な話、今のハードウェアの性能は、昔のものとは比べ物にならないくらい驚異的だよね。でも、俺が理解できないのは、いくつかのソフトウェア（特にWindowsとか、インスタントメッセージングアプリなど）が、今の方が昔よりもパフォーマンスが悪く感じることなんだよね。
└
答えは、いつもと同じだと思う：GUIスレッドでのI/O待ち。TelegramもFBメッセンジャーもサクサク動くけど、最近は他のアプリはあまり使ってないな。（特にTeamsや最近のSkypeは使ってない。）
└
CRTはデータを画面により早く届ける。いくつかのLCDは500msの遅延があるんだ。
└
今のハードウェアの性能は、ほとんどの人（SREマネージャー、開発者、CTO）がクラウドコンピュートに対して払う意欲がある金額と比べると、さらに驚異的だよね。特に、開発者の「リモートワークステーション」の文脈で考えると。AWSのインスタンスでパフォーマンスをベンチマークしたら、平均的なM1 MacBookよりも少なくとも5倍遅くて、開発者一人あたり月に数百ドルもかかるのに、MacBookはすでに支出済みのコストだし！
新しいアイデアではないけど、CPUがキャッシュする不揮発性ストレージのアーキテクチャについて考えるのは面白いね。もしmmap()でファイルをマッピングすることがmalloc()と全く同じパフォーマンス特性を持つと仮定できたらどうなる？データがアドレス空間を解放しても消えないとしたら？任意のプログラムメモリにファイル名を付けて、OSに渡して永続化できたらどうなる？基本的なソフトウェア設計の前提は、まだスピニングラスト時代の制約に基づいていることが多いよね。
└
今のLinuxならこんなのが手に入るよ。(実際、mmapはほとんどのケースでカーネルからメモリをリクエストする方法なんだ。) ただ、mmapはread/writeより遅いんだよね。カーネルがデータアクセスパターンをあまり理解してないから、キャッシュをどう埋めるかを推測しなきゃいけないんだ。
└
> 基本的なソフトウェア設計の前提は、まだスピニングラスト時代の制約に基づいていることが多い... fsync()はまだ遅いし、本当の永続性にはそれが必要なんだ。ただスピニングラストの問題だけじゃなくて、明らかに一時的なストレージに対して異なる扱いを求める理由があるんだよ。
高い同時実行性を持つOLAPデータベースを最適化した経験から言うと、ボトルネックはメモリ速度であることが多いです。
メモリやCPU、I/Oの問題ではなく、レイテンシとスループットの問題だと思う。ほとんどのソフトウェアはレイテンシを無視するから遅くなる。何かを待ちながらシリアルにプログラムすると、遅くなるよね。データをメモリのあちこちに散らばせたり、ディスクから小さなチャンクで読み込んだり、DBに対してたくさんの小さなクエリをシリアルに実行すると、ソフトウェアは99.9%の時間、何かが終わるのを待っているだけになる。それが全てだよ。データをメモリ内で線形に整理したり、一度にバッチ処理をしたり、並列化したり、I/Oをバッチ処理したりすれば、速くなるはずだよ。
俺のボトルネックは相変わらず、クラウドVMやコンテナのファイルシステムI/Oがクソだわ。
「これは[これ]じゃなくて、[あれ]だ！」みたいなコメントをたくさん見たけど、それも間違ってる。パフォーマンスのボトルネックは、実際に実行しているワークロードの中で最初に飽和するリソースだよ：CPU、メモリ帯域、キャッシュ/アロケーション、ディスクI/O、ネットワーク、ロック/調整、または下流のレイテンシ。測定して、プロファイルやトレースで証明して、一つのことを変えて、もう一度測定するんだ。
ここに作者がいます。これにはパート2があるよ： https://stoppels.ch/2022/11/30/io-is-no-longer-the-bottlenec...
└
もしこれがシングルコアであれば、「6GB/s」の主張は理論だけでなく実践でも否定されるよ。
└
こんにちは、数年前に単語の頻度をカウントしてソートされたヒストグラムを生成するコンテストに参加したことがあるよ。その参加者のトリックについて話している動画があるクールな投稿があるんだ。https://easyperf.net/blog/2022/05/28/Performance-analysis-an... 他の参加者は、pshufb+eqとeqx3+orx2の間で実行時間に0の違いを測定したと言ってたけど、君の問題はホワイトスペースのクラスがもっと多いと思うし、ヒストグラムの問題では、入力のチャンク内のすべての単語をハッシュする方法が、単語の開始位置や終了位置のビットマスクを取得する方法よりも重要になると思うよ。