Linuxパイプの速度はどれほど速いのか？ (2022)
(mazzo.li)- Linuxパイプのスループットを
perfとカーネル経路解析で追跡し、単純なwrite/readベースの3.7GiB/s実装を最終的に62.5GiB/sまで引き上げた - ボトルネックの出発点は、パイプが4KiBページ参照を保持するリングバッファとして動作し、コピー、ページ割り当て、ロック、待機・起床のコストを同時に負担している点にある
vmspliceとspliceは、ユーザーメモリとカーネルバッファの間のコピーを減らし、スループットをそれぞれ12.7GiB/s、32.8GiB/s程度まで高める- その後は、仮想アドレス範囲を
struct pageに変換するコストが目立ち、2MiB huge pageを使うとページテーブル探索の負担が減って51.0GiB/sまで向上する - 最後の最適化である
SPLICE_F_NONBLOCKとbusy loopはスループットをさらに高めるが、準備完了を待つ間もCPUコアを占有し続ける
実験の目標と基準性能
- 目標は、LinuxでUnix パイプがどのように実装されているかを調べ、パイプにデータを書き込み読み出すテストプログラムを段階的に最適化すること
- 実験環境はIntel Skylake i7-8550U CPUとLinux 5.17であり、Linuxの内部実装は継続的に変化するため、数値は環境によって変わりうる
- 出発点は、
writeとreadシステムコールで256KiBバッファを繰り返しパイプへ流すプログラムwriteは同じ256KiBバッファを繰り返し書き込むreadは合計10GiBを読み取り、スループットを表示する- コードは
pipes-speed-testにある
- 比較対象にした高度に最適化されたFizzBuzzプログラムは、
pv計測で約36.2GiB/sを出力する- FizzBuzzはL2キャッシュサイズと同じ256KiBブロックを使う
- この実験でも同じ256KiBブロックを使うが、出力内容の計算は行わず、パイプI/Oの上限に近い値を見ようとしている
- 最初の実装結果は次のとおり
./write | ./read- 3.7GiB/s、256KiBバッファ、40960回反復、合計10GiB転送
writeとreadが遅い理由
perf record -gとperf reportで確認すると、write側の時間の約**47%**がpipe_writeで消費されているpipe_write内部ではcopy_page_from_iterと__alloc_pagesが大きな比重を占める- データコピー
- ページ割り当て
- スケジューリング
- 待機・起床
- ロック取得・解放
- Linuxパイプはページ参照を保持するリングバッファである
pipe_inode_infoはhead、tail、pipe_buffer配列を持つpipe_bufferはstruct page *page、offset、lenを持つ- x86-64の通常ページサイズは4KiB
- デフォルトのリングバッファスロット数は16で、例の8スロットパイプは最大32KiBを保持できる
headは書き込み端を、tailは読み出し端を表す- パイプが満杯なら
writeはブロックされる - パイプが空なら
readはブロックされる
- パイプが満杯なら
pipe_writeは概ね次の順序で進む- パイプがすでに満杯なら、空きができるまで待つ
- 現在
headが指すバッファに空きがあれば、まずそこを埋める - 空きスロットと未処理データがあれば、新しいページを割り当てて埋め、
headを更新する
pipe_readは逆にページを消費し、完全に読み終えたページを解放してtailを更新する- この経路では各ページが2回コピーされる
- ユーザーメモリからカーネルへ1回
- カーネルからユーザーメモリへ再度1回
- コピーは4KiBページ単位で行われ、その途中に同期とページ割り当て・解放が混ざる
- 同じマシンでの単一スレッド順次RAM読み出しは約16GiB/sであり、パイプ経路の複雑さを考えれば、
write/readが約4倍遅いのも不思議ではない
vmspliceとspliceでコピーを減らす
- 高速I/Oでは、ユーザーメモリとカーネルバッファの間のコピーコストがボトルネックになりうる
- Linuxはパイプ関連でコピーなしの移動を行うためのシステムコールを提供している
vmspliceはstruct iovec配列で、パイプに入れるバッファを指定する- 戻り値は実際にパイプへ入ったバイト数
- パイプリングバッファのサイズ制限のため、要求した全サイズが一度に入らないことがある
vmspliceはユーザーメモリをコピーせずにパイプへ接続するため、読み手がそのデータを消費する前にバッファを再利用しないよう注意が必要- FizzBuzzプログラムはこれに対処するためdouble bufferingを使う
- 256KiBバッファを2つの128KiB半分に分ける
- パイプサイズを128KiBに設定し、4KiBページ基準で32スロットを作る
- 2つの半分バッファを交互に埋めて
vmspliceでパイプへ入れる
- テストプログラムは実際にはバッファ内容を書き換え直さないが、実際の出力生成プログラムに必要な構造に近い形でdouble bufferingを維持している
writeをvmspliceに置き換えると、スループットは12.7GiB/sへ増加する- コピー量が半分に減る
write/read比で3倍超の改善
- 読み出し側も
spliceに置き換えると、コピーを完全に除去して32.8GiB/sまで向上する - ただし、
vmspliceの安全性には注意が必要- ページが再びspliceされると寿命が延びる可能性がある
SPLICE_F_GIFTなしでも安全でないのかは明確ではない- コピーなしの(zero-copy)パイプを安全に使うには特別な注意が必要
iov_iter_get_pagesとページ変換コスト
vmspliceとsplice適用後、perfではvmsplice経路の時間が大きく見えるiov_iter_get_pages__mutex_lock.constprop.0add_to_pipe
iov_iter_get_pagesは、vmspliceへ渡されたstruct iovecの仮想メモリ範囲を、パイプが保持できるstruct pageの一覧へ変換する- プロセスは物理メモリアドレスではなく仮想アドレスを使う
- CPUはページテーブルを通じて仮想アドレスを物理アドレスへ変換する
- x86-64の通常ページサイズは4KiB
- x86-64のページテーブルは4段、各段512分岐の木構造として説明される
- パイプの
pipe_bufferはstruct pageを参照するstruct pageは、カーネルが物理ページと関連メタデータを扱う中核構造- そのため
vmspliceは入力仮想メモリ範囲を物理ページ参照へ変換する必要がある
iov_iter_get_pages内部の時間の大半はget_user_pages_fastで消費される- 128KiBバッファと4KiBページ基準で合計32ページを取得する必要がある
- パイプコードは実装上、一度に
nr_pages = 16で呼び出し、必要なら繰り返すが、splicedされたページ総数は32ページ
get_user_pages_fastは、CPUが行うのと似た形でソフトウェア的にページテーブルをたどり、struct pageを集める- 呼び出し側がページを書き込んでいる間に物理ページが再利用されないよう、
struct pageの参照カウントを増やす必要がある- その後
put_pageで参照カウントを減らさなければならない
- その後
- 開始時に
memsetでバッファを埋めるとページテーブルエントリが事前に作られ、get_user_pages_fastの遅い経路を避けられるmemsetをしないと、例ではスループットが25.0GiB/sまで低下する- huge page使用時にはこの現象は同じようには現れない
huge pageでページ処理コストを下げる
- x86-64は4KiB通常ページのほかに2MiBと1GiBのhuge pageをサポートする
- 以降の実験では2MiB huge pageのみを扱う
- 1GiBページは比較的まれで、この用途には大きすぎると考えられる
- huge pageは同じメモリ範囲をより少ないページで表現し、管理コストを下げる
- 仮想アドレスを物理アドレスへ変換する際のページテーブル段数も1つ減る
- CPUのTLB負荷を減らすのにも役立つ可能性がある
- この実験での直接のボトルネックは、ハードウェアのページテーブルウォークではなく、カーネルのソフトウェア経路である
get_user_pages_fast - Linuxでは、2MiB境界に揃えたメモリを割り当て、
madvise(..., MADV_HUGEPAGE)を呼ぶことでhuge page利用を要求できる - huge pageを適用すると、スループットは51.0GiB/sまで増加する
- 性能改善の理由は、
struct pageが2MiBページ1つをそのまま指すからではない- カーネルコードは概ね、
struct pageが現在のアーキテクチャの標準ページサイズを指すことを前提としている - huge pageはhead
struct pageと複数のtailstruct pageで表現される - 2MiB huge pageは4KiB基準で最大512個の
struct pageとして表現されうる
- カーネルコードは概ね、
- それでも、最初のエントリを見つけた後は、続く
struct pageを単純なループで生成できるため、ページテーブルを何度も探索するコストが減る - Linux 5.17以降のカーネルには、head pageを明示的に識別する
struct folioが含まれており、実行時のhead/tail確認の必要を減らす改善が入っている
busy loopで同期コストを減らす
- huge page適用後、
perfではwait_for_spaceと__wake_up_common_lockの時間が目立つ- 書き込み可能な空きを待つコスト
- 読み出し側を起こすコスト
- この同期コストを避けるには、
vmspliceとspliceに**SPLICE_F_NONBLOCK**を使える- パイプへ書けない場合は即座に
EAGAINを返す - 呼び出し側は準備できるまでbusy loopする
- パイプへ書けない場合は即座に
- busy loopを適用すると、スループットは62.5GiB/sまで増加する
- 代償も明確
vmspliceやspliceの準備完了を待つ間、CPUコアを完全に占有する- CPU使用量を多く使う代わりに、レイテンシやスループットを得る方式
- 最終的に、この合成ベンチマークは約3.5GiB/sから約65GiB/s水準まで改善した
残る細部と実務的な話題
- 最適化の過程は、
perfの出力とLinuxソースコードを併せて見ながら進められた - 扱った話題は、パイプとsplicingそのものより広い高性能プログラミングの主題につながっている
-
コピーなし演算
- リングバッファ
- ページングと仮想メモリ
- 同期オーバーヘッド
- 実際のコードでは、2つのバッファを別々に割り当ててページテーブル競合を減らす
get_user_pagesがページテーブルエントリの参照カウントを増やし、put_pageが減らす- 2つのバッファが異なるページテーブルエントリを使えば、参照カウント更新の競合が減る
- テストは
tasksetで./writeと./readプロセスを2つのコアに固定して実行した - リポジトリには
get_user_pages_fast向けの合成ベンチマークも含まれる - huge page使用有無による速度差を測定できる
- splicingは依然として曖昧で危険な概念として残っており、関連する問題はカーネル開発者にとって引き続き負担になっている
-
1件のコメント
Hacker News の意見
正しく理解できているなら、
vmspliceは読み手側と書き手側の両端で同時に使うと、2つのプロセス間の小さな共有メモリ機構に近いものに見えるつまり、両方のプロセスがバッファをいつ読み書きするか、使用後にどう返却するかについて、極めて慎重でなければならない。高速ではあるが同時に恐ろしい方式で、誰もが書きそうな素朴な実装が、可能な性能より20倍遅いという点も残念
vmspliceが2つのプロセス間の小さな共有メモリ機構だとは思えない。ユーザーメモリからパイプへのゼロコピーだけをサポートしており、逆方向ではコピーが発生する詳細は https://mazzo.li/posts/fast-pipes.html#fn10 を参照
パイプ、ソケット、ファイル、メモリを抽象化しつつ、このような最適化まで行ってくれるデータ処理ライブラリがあるのか気になる
C、C++、Rust、あるいは他のシステム言語にそうしたライブラリがあるのか知りたい。記事に出てくる
splice()やvmsplice()のような API に詳しくないので、低レベルアプリケーションを作るとき、可能な場合にこうした最適化を自動的に活用してくれるライブラリがあるのではないかと思った。libuv、tokio、Nettyが Linux でこれを自動処理しているのかも気になるが、少し調べた限りでは、おそらくそうかもしれないように見える上位レベルのコードがこうした機能を使うことはまれで、かなり特殊用途であり、Linux 向けに特化する必要があるためだ。データの中身を見ずに Linux 上で移すだけなら
spliceは有用。TCP/UDP プロキシのようなアプリケーションには確実に必要だが、普通の HTTP サーバーにはあまり向いていない。こうしたアプリを作っているなら、zero copy のようなキーワードをよく目にするようになり、spliceは最初に目にする結果の一つになるtokio用のクレートがある。自動ではないが興味深いかもしれない: https://lib.rs/crates/tokio-splice研究環境の外ではあまり知られていないようで、効率的な Cosh 実装を書くにはかなり時間がかかる可能性が高い。要約すると、転送モードは move、share、copy の3種類。たとえば move 転送では、送信者が読み書き権限を持つデータを受信者に完全に引き渡し、ページテーブルの仮想メモリ再マッピングで実装できる。また、送信者と受信者が協力すると信頼できるのか、それとも仮想メモリ権限の再マッピングで厳密に隔離すべきなのかを示す strong/weak 属性もある。正直なところ、超高度に最適化されたパイプのようなものと安定して肩を並べられるほど十分に最適化できるかは分からず、「十分に賢いコンパイラ」問題になるかもしれない。それでも試してみる価値はあると思う
[1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf
2022年以前の議論: https://news.ycombinator.com/item?id=31592934
4年前に偶然知った驚くべき事実は、Linux のパイプを使うと非決定的な動作が起こり得るということ
https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...
echoしたデータを実際には何も渡していない(echo red; echo green 1>&2) | echo blueは、|記号を挟んで2つのサブシェルを作る。サブシェルは現在のシェルの子プロセスなので、開いているファイル記述子テーブルのような重要な属性を継承する。2つのサブシェルは同時に実行され、親シェルはすべての子プロセスが終わるのをwait()するだけ。どちらの子が先に実行されるかは概ね予測できず、マルチコアシステムでは文字どおり同時に実行されることもある。左側のサブシェルの標準出力はパイプの書き込み側に、右側のサブシェルの標準入力は読み取り側に接続される。だがecho blueは入力を読まずに出力するだけなので、パイプからは何も読み取られない。echo green >&2は標準出力をパイプではなく、標準エラーが指している先へ送る。結局echo greenとecho blueが同じファイル、おそらく端末へ直接書き込むことで競合状態が生じ、どちらが先にスケジュールされるかで順序が分かれるそうでなければパイプラインは役に立たない。例えば
curlで tar ファイルをダウンロードしてそのまま展開するパイプラインで、curlが終わるまで待ってからtarを実行すると、大きな中間 tar ファイルをどこに保存するかといった問題が生じる。tarはcurlの実行中に一緒に動いてこそ、バッファを小さく保ち、高速に実行できる。パイプラインプログラム間の唯一の制御フローは、標準入力と標準出力で構成される。この例では標準エラーに書き込んでいるので、当然ながら決定的な制御フローには含まれないついでに言うと、混同を避けるなら “Indeterministic” は哲学用語で、計算機科学の用語は “nondeterministic” である
0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
このコマンドはおそらく意図的に変わった形をしていて、コードレビュー担当者なら間違いなく首をかしげただろう。
echo redはあるが、どこにも渡されない。“red herring” のジョークかもしれない。echo greenは標準エラーへ行くので、echo blueより先に終わったときだけ見える。正確な順序は出力バッファリングに依存し、それはどのタイムスライスが先に割り当てられるかで変わり、CPU 数や負荷によっても変化する。だから非決定的ではあるが、topが非決定的であるのと同じようなものだ要約すると、2つのプログラムが可能な限り最適に書かれていると仮定した場合、パイプの最大速度はシステムの1コアが読み書きできる速度に近い
本質的には、カーネルがあるプログラムの標準出力から別のプログラムの標準入力へ同じ物理メモリページをマッピングするため、処理はゼロコピー、またはより最適でない状況では高速な単一コピーに近くなる。この事実を知ると、パイプで2つ以上のツールをつなぐシェルスクリプトで非常に高性能な処理をするのは、やりがいがあり、少し面白くもある。道具箱の中で最も有用なツールの1つだ
spliceやvmspliceを使う場合だけ。この Linux 専用システムコールは扱いが難しく、特にvmspliceはそうだ大多数のプログラムやシェルフィルタは、
pvのような目立つ例外を除けばこれを使わないため、カーネルメモリへコピーしてまた取り出すコストを払う作っているアプリケーションは、負荷特性によってはパイプ+プロセスやグリーン/ユーザー空間スレッドでよりすっきり実装できる可能性がある。多少不便なことはあっても、メッセージパッシングはたいていデッドロック地獄よりましだ
この記事は Linux パイプをより速くする方法を扱っているが、共有メモリやメッセージキューのような別の方法のほうが依然として速い場合もある
大量のデータを高速に移動する必要があるシステムでは、パイプの追加ステップが速度を落とすことがある。複数のスレッドがデータを共有する場合も、パイプが他の方式より多くの問題を生む可能性がある。なので、この記事の改善は、速度が重要な実際の状況では大きな助けにならないかもしれない
io_uringのようなものを選ぶ利点があるしかし双方向通信では、どちら側でもデータの準備ができたという通知が必要になる。CPU を消費しながらポーリングしたくないかもしれないし、そうした選択肢がその同期をパイプよりどう高速に処理するのかはよく分からない
ページテーブルのようなものは知っていたが、それを
perfによる性能分析と結びつけてみると、スループットにおいてどれほど中心的なのかが明確になるパイプは素晴らしい。別のプロセスが別の CPU にあろうと別のマシンにあろうと、正直あまり関係ない
https://github.com/nathants/s4/blob/master/examples/nyc_taxi...
パイプは
cat、sed、awk、cut、grep、uniq、jqなどを繰り返し組み合わせるのに十分速い