最速のMutexたち
(justine.lol)- 高い競合 状況では Mutex 実装の差が大きく現れ、Cosmopolitan Libc の
pthread_mutex_tは Windows と Linux の主要実装よりも短い実行時間と低い CPU 使用量を示した - Windows の 24-core Threadripper 29070WX テストでは、Cosmopolitan は Microsoft SRWLOCK より 2.75 倍高速で、CPU リソースの使用量は 18 倍少なかった
- Linux の 96-core Threadripper Pro 7995WX では、glibc より 3 倍、musl libc より 11 倍高速で、CPU 時間の差はさらに大きく広がった
- MacOS M2 Ultra では Apple Libc がわずかに上回り、Cosmopolitan は ARM 環境で XNU の ulock システムコール に依存する単純なアルゴリズムを使っている
- 性能の基盤は Google の nsync 統合であり、CAS の高速パス、待機キュー、futex/ulock/
WaitOnAddress()、飢餓防止と designated waker 設計が中核となっている
競合 Mutex ベンチマークの方法
- テストでは 30 個のスレッド を作成し、各スレッドが同じグローバル整数
g_choresを 100,000 回 増加させる - 各インクリメント処理は
pthread_mutex_lock()とpthread_mutex_unlock()の間にある非常に小さなクリティカルセクションで実行される - 測定値はマイクロ秒単位で、3 種類の時間を区別している
- wall time: プログラム実行にかかった実時間で、スレッド生成と join のオーバーヘッドを含む
- user time: ユーザー空間で消費した CPU 時間
- system time: カーネルで消費した CPU 時間
- 複数スレッドが並列実行されるため、user time と system time の合計は wall time より大きくなることがある
- 非競合の状況では実装間の性能差は概して小さいが、競合状況 では Mutex 設計の差が大きく現れる
Windows: SRWLOCK より高速な Cosmopolitan
- Windows テストは 24-core Threadripper 29070WX で実施された
- Mark Waterman の MutexShootout は、高競合シナリオにおいて Windows の SRWLOCK を最も強力な実装と評価していた
- 同じ条件で Cosmopolitan
pthread_mutex_tは、SRWLOCK より短い wall time と低い CPU 使用量を記録した
| 実装 | wall time | user time | system time |
|---|---|---|---|
Cosmopolitan pthread_mutex_t |
148,940µs | 328,125µs | 62,500µs |
| Microsoft SRWLOCK | 410,416µs | 5,515,625µs | 1,640,625µs |
Microsoft CRITICAL_SECTION |
949,187µs | 7,937,500µs | 5,078,125µs |
MSVC 2022 std::mutex |
991,750µs | 12,156,250µs | 4,031,250µs |
| spin lock | 1,165,435µs | 24,515,000µs | 15,000µs |
Cygwin pthread_mutex_t |
9,780,803µs | 1,937,000µs | 6,156,000µs |
- Cosmopolitan Mutex は Microsoft SRWLOCK より 2.75 倍高速 で、CPU リソースの使用量は 18 倍少ない
- POSIX 実装を Windows に提供する Cygwin Mutex と比べると 65 倍高速
- Cygwin Mutex はこのユースケースでは spin lock よりも遅い結果になった
Linux: wall time よりさらに大きい CPU 時間の差
- Linux テストは 96-core Threadripper Pro 7995WX で実施された
| 実装 | wall time | user time | system time |
|---|---|---|---|
Cosmopolitan pthread_mutex_t |
36,905µs | 44,511µs | 23,492µs |
glibc pthread_mutex_t |
101,353µs | 150,706µs | 2,724,851µs |
| spin lock | 202,423µs | 4,694,749µs | 2,000µs |
Musl libc pthread_mutex_t |
411,013µs | 2,167,898µs | 9,926,850µs |
- Cosmopolitan Mutex は glibc より 3 倍、musl libc より 11 倍 高速
- CPU 時間ベースでは glibc より 42 倍、musl libc より 178 倍 少なく使う
- すべてのスレッドが直列化された処理を行う必要があるワークロードでは、Cosmopolitan は
htop上で 1 コアしか動いていないように見えることがある - 同じ状況で glibc や musl libc は CPU 使用量を大きく埋めることがあり、同じサーバー上で複数の処理を走らせる際の負担が大きくなる
MacOS: Apple Libc がわずかに優勢
- MacOS テストは M2 Ultra で実施された
| 実装 | wall time | user time | system time |
|---|---|---|---|
| Apple Libc | 52,263µs | 43,202µs | 911,009µs |
Cosmopolitan pthread_mutex_t |
54,700µs | 63,055µs | 1,003,674µs |
- MacOS M2 ARM64 では Apple Libc が Cosmopolitan Mutex よりわずかに高速
- Cosmopolitan の一般的な Mutex 実装はこのプラットフォームではうまく動作しない
- MacOS ARM では、Cosmopolitan は Ulrich Drepper の Futexes Are Tricky に基づく、より単純なアルゴリズムを使用している
- この方式では重い処理の大半を XNU の ulock システムコール に任せており、その結果 Apple 実装とほぼ同等の性能を出している
性能の基盤: nsync 統合
- Cosmopolitan Mutex の性能の鍵は、Google の nsync ライブラリ統合にある
- nsync は GitHub スター 371 件のライブラリで、Google の Mike Burrows によって書かれた
- Cosmopolitan への統合過程では、次の作業が行われた
- nsync の Mutex unlock 関数で長らく見つかっていなかったバグを発見して修正した
- AARCH64 で C11 アトミック演算へ移植し、競合時の nsync Mutex を upstream nsync より 30% 高速 にした
- futex のようなシステム統合を新たに書き直し、ランタイム移植性を実現した
- POSIX スレッドキャンセルと滑らかに動作するようにした
nsync の動作方式
- nsync はロックを素早く取得するため、最初に 楽観的 CAS(compare and swap) を即座に試みる
- ロックを取得できなければ、呼び出しスレッドを待機者の 双方向リンクリスト に追加する
- 各待機者は、独立した別キャッシュライン上に自分専用のセマフォを持つ
- 待機状態に入ったスレッドは、もはや主ロックに触れない
- これは複数コアが同じキャッシュラインに触れることで生じる通信オーバーヘッドを減らすうえで重要である
- 関連する背景として Ulrich Drepper の What Every Programmer Should Know About Memory が挙げられている
- nsync は OS の futex を使ってスレッドをスリープさせる
- MacOS では futex は ulock と呼ばれる
- Windows では
WaitOnAddress()が futex の役割を果たす - Cosmo がサポートする OS の中で NetBSD だけは futex がなく、POSIX セマフォをカーネル空間で実装しており、各セマフォごとに新しいファイルディスクリプタが必要になる
- nsync は “long wait” の概念で 飢餓(starvation) を避ける
- 待機者が 30 回起こされたにもかかわらず毎回内部的にロック取得に失敗した場合、まだ待っていないスレッドがロックを取得できないよう、ロックにビットを追加する
- このビットがあると、待機キューがある程度空くまで新規に入ってきたスレッドの初回 CAS は失敗する
- 小さなクリティカルセクションで競合するユースケースは、designated waker の概念によって高速化される
- あるスレッドが起床してロックを取得しようとする時、主ロックにビットがセットされる
- nsync では unlock 関数が次の待機スレッドを起こす責任を持つ
- このビットのおかげで、unlock 中のスレッドはすでに起きているスレッドがいる場合に 2 番目の待機者を起こす必要がない
- 関連するソースコードは
cosmopolitan/third_party/nsync/mu.cとcosmopolitan/libc/intrin/pthread_mutex_lock.cにある
実サービスと検証コード
- Cosmo Mutex を使ったライブデモとして http://ipv4.games/ サーバーを見ることができる
- このサービスは 2 コア GCE VM で動作しており、これまで最大 49,131,669 IP 規模のボットネット DDoS に耐えてきた
- nsync によって SQL クエリをバックグラウンドスレッドへ移し、スレッド同士がメッセージを送り合う構造を使えるようになった
- 状態指標は /statusz で確認できる
- ベンチマークコードは
gettimeofday()で wall time を測り、getrusage()で user time と system time を測定する - 最後に
g_chores == THREADS * ITERATIONSを確認して、すべてのインクリメント処理が実行されたことを検証する
Spin lock を見るときの注意点
- 非競合の状況では Mutex 実装間の差は小さく、数行の spin lock のほうが良い場合もある
- しかし spin lock は、本当に他に選択肢がない時だけ使うべきである
- カーネルのように極端に低レベルの制約があり、より複雑な方式を使いにくい場所では有用である
- nsync lock の内部実装詳細として spin lock が使われることもある
- lock 性能を wall time だけで見ると spin lock が良く見えることがあるため、
getrusage()で CPU 時間 まであわせて確認する必要がある
1件のコメント
Hacker News のコメント
新しいミューテックス実装との比較はいつも興味深いが、このベンチマーク手法は気に入らない。ほとんどマイクロベンチマークのように見える。
高速なロックを実際にデプロイしている人たちは、たいてい非常に大きなマルチスレッドプログラムを主な性能テスト手段にしている。クリティカルセクションの長さ、競合するスレッド数、競合の度合いがさまざまに変わる複雑なワークロードでは、ミューテックスを速くしたり遅くしたりする要因が変わるようだ。
参考までに、私は WebKit の高速ロックを書き、ロック実装用の ParkingLot 抽象化を発明し（Rust と Unreal Engine でも使われている）、以前には Java 用の高速ロックに関する研究と論文も行った。
リアルタイムオーディオのプログラマーとしては、まだロックされていないミューテックスを取得するコストのほうが重要だ。私たちのアプリではこの状況が圧倒的に多い。同様に、N 個のスレッドが競合するときではなく、失敗する
try-lock操作のコストも知りたい。Cosmopolitan はオープンソースなので自分で測定することもできるが、それでも物足りない。
ハッシュマップと同じで、単一のハッシュマップがあり得るすべてのワークロードで優れていることはまれだ。
ロック取得失敗時に固定時間（例: 100µs）スリープするミューテックスは、ほぼ常に処理をひとかたまりにし、この挙動に近づけてベンチマークで「勝つ」ことができる。しかし実際のアプリケーションで少しでも競合があると、そのようなミューテックスはひどいものになる。
このミューテックスが悪いとか pthread ミューテックスが良いという意味ではなく、そのマイクロベンチマークが実際のアプリケーション性能を予測できるようなものを測っていないという意味だ。
「Cosmopolitan Mutex が優れている理由は nsync というライブラリを使っているから」という部分について、nsync は初めて聞いたが、Mike Burrows は Google の本番用ミューテックス実装も書いている: https://github.com/abseil/abseil-cpp/blob/master/absl/synchr...
なので、なぜこのミューテックス実装がベンチマークから外れているのか気になる。そして macOS で
__ulockに委譲するなら、libc++ の atomic ライブラリにあるwait()、notify_one()メンバー関数だけを使って、もっと単純に実現できそうだ。以前、Rust のミューテックス実装改善に関する大きなスレッドもあった: https://github.com/rust-lang/rust/issues/93740#issuecomment-... 興味深いのは、人気のあるほぼすべてのミューテックス実装の内部動作が詳しく議論されていることだ。
本当かもしれないが、直接確認することはできない。効率を重視する、極めて頭の切れるエンジニアだった。ただし、私たちは 1 台のサーバーを長く運用していたわけではない。
現在の Rust のミューテックス実装は今年初めに入ったもので、Linux では大きく違わないかもしれないが、Windows と Mac では新しい作業だと理解している。
それでも Mara が他の実装の内部を説明した内容は依然として興味深いが、自分の状況では古い情報ではないか確認したほうがよい。
https://awards.acm.org/award-recipients/burrows_9434147
「まだ新しいCライブラリなので粗い部分はあるが、あまりにも急速に良くなっているため、プロダクションで使わないことが職業上の責任放棄のように見え始めた」という文はかなり変だ。Cosmopolitanプロジェクトは高く評価しているが、こうした大げさな優越性の主張は、たいていかなり悪い危険信号だ
一部の人にはきつく見えるかもしれないのも理解できる。以前にもllamacppでそういう形の騒動が起きたことがある
プロダクションで最優先されるのは「ものすごい速さで良くなっていること」ではなく、安定性、予測可能性、信頼性だ。もちろん性能も重要だ。より速いコードはインフラを減らし、コストや環境面で良い可能性がある。しかし速さは最後の優先事項だ
例えばAPEは非常に印象的なハックだと感じるが、「今や1つのプラットフォームだけで不安定なのではなく、複数のプラットフォームで同時に不安定になれるということか？」という批判も可能だ
技術分野に長くいるほど、完全な相互利益は極めてまれで、ほとんどは得るものと失うものが同時にあるトレードオフなのだと気づく
完全に横道だが、ゲーム開発者としては、すべての開発者ビルドでデバッグ作業をたくさんする遅いミューテックスが好きになった。デバッグ名/IDを持ち、所有者を追跡し、競合に費やした時間をプロファイラに報告し、所有権の変更もプロファイラに報告する、といったものだ
ゲームは並行性を別の形で構成する傾向があり、ロックを避けるパターンも発展してきた。しかしそうしたパターンは使うのが難しく、プログラマが構造を変える必要がある。ほとんどのコードは「とりあえずここにロックを付けて、マイルストーンを越えよう」から始まる
高速なロックも予測不能に遅くなることがあり、リアルタイム保証があったならそれを壊してしまう。平均的には速いかもしれないが、テールレイテンシは消えない。「うちのゲームがカクつく」を追跡するために戻ってくる人間にはなりたくないが、たいてい自分がその人間になる
だから遅いロックを使う方がいい。プロファイラで大きく赤く見えるロックのことだ。問題になっているのが見えたら、リファクタリングして取り除けばいい
難しい要求だというのは分かっている。AAAプロダクションでプロファイラを使える人は、指で数えられる程度だ。複数のプロダクションを見ても、いつもそうだった
愚痴で申し訳ないが、高速な並行性プリミティブとアルゴリズムの研究は続いてほしい
ゲームでは、可能ならロック競合は絶対に避けたいし、多くの場合、ロックを取る必要がないことを証明できる。例えば各フレームは段階に分かれており、ある共有リソースへの可変アクセスは特定の段階でだけ必要になる。
render()前のupdate()や、アセットのホットリロードのような場合だスコープ付きスレッドとRustの借用規則を使えば、そもそもミューテックスが不要になるように構造化でき、後でコードが変わって必要になった瞬間にコンパイラが厳格にエラーを出してくれると確信できる
可能なら、プロファイラのスパイクよりもコンパイルエラーを受け取る方が常に良い
一方で Cosmo/APE/redbean 系は本当にすごそうに見えるし、関連記事のコメントもおおむね好意的で、概念そのものに反論する内容もあまりありません。ところが別の面では、他の人がこれを使っているという話をほとんど聞きません
誰もが自分の作業を大きく共有するわけではありませんが、何年も経っているならプロジェクトの振り返り記事をいくつか見かけていてもよさそうです。私が見た Cosmo/APE/redbean への言及は、すべて Justine のサイト由来のものでした
なので気になります。隠れた落とし穴があるのでしょうか？成果を得るために何か悪いことをしているツールなのでしょうか？コンパイラやランタイムに詳しくないせいで私が理解できない、tom7 風のジョークやトローリングなのでしょうか？それとも本当に、まだ広く普及していない独創的なツール群なのでしょうか？
クロスプラットフォームソフトウェアを作る多くの人が欲しいのは、すべてのプラットフォームで動く単一の実行ファイルではなく、サポートする各プラットフォームで正しく動作する単一のコードベースです
その観点では、Go のように CGO を避ければすべてのターゲットへクロスコンパイルできる言語は快適です。しかし、APE の「3通りに実行可能」という魔法は本当に賢いとはいえ、永遠に動き続けるという信頼感はなく、多くの場合は実質的な利点もあまりありません
各プラットフォームにはそれぞれのパッケージングや署名の要件があるので、プラットフォーム別のターゲットとして個別にコンパイルするほうがよいです
たとえば、すでにプロジェクトを別の OS やプラットフォーム向けにクロスコンパイルできている、あるいはそのためのビルドインフラがあるなら、どこでも動く単一バイナリを作る解決策を探す理由はありません
また APE は複数の OS で実行するために巧妙なハックを使っています。実行ファイル形式が進化して、そのハックがいつか壊れたら？その変更に合わせて APE を直す時間が誰にもなかったら？
一方で gcc、clang、go、rust のような退屈なツールは、更新され進化し続ける OS 上でも動き続けるでしょう。だから結局、退屈なほうに留まることになります。賢いものを気にしない理由は、退屈なものが私には普通にうまく動くからです
統合された重みなしで実行し、ファイルシステムから重みを読み込ませることもできます。ローカル LLM を最も簡単に「入手してすぐ実行」できる方式かもしれません
しかし
libcのような基盤技術として使うには、主に面白いおもちゃや小さな個人プロジェクトに役立つものに見えますその文脈で
glibc、musl、msvcrtのようなものの真面目な代替として提示されると、少し奇妙に感じます。とてもかわいいハックですが、自分が本気で依存しているものの中で見つけたら、かなり戸惑うと思いますHugging Face にも、その形式で再パッケージした人気モデルを定期的にアップロードしています: https://huggingface.co/models?search=llamafile
ただし、それが小さなモデルを素早く試すこと以上の実用性を持つかどうかは別問題です
それほど良いなら、なぜすべての C ライブラリが同じトリックを採用していないのか気になる
私の推測では、そのトリックは特定のアーキテクチャ、特定の CPU モデル、特定のワークロードやアクセスパターンでだけ常に速い可能性が高い。サポートするすべてのハードウェアでさまざまなワークロードをきちんとベンチマークすると、同じ利点は出ないかもしれない
あるいは、Cosmopolitan が実装しようとしている pthread API のセマンティクスが微妙に異なり、この実装が仕様に厳密には準拠していない可能性もある
複数の libc 作者たちが、OS の基本要素に関する最新研究についていけていないとは想像しにくい
glibc の malloc はそれなりに使えるが、全体的な速度とスケーラビリティでは、より現代的な代替に簡単に負ける。断片化がひどく、時間とともに悪化し、実ワークロードに大きな影響を与える
MALLOC_ARENA_MAXのような調整値も多い。musl malloc は性能面ではあらゆるレベルでひどい。マルチスレッドプログラムで musl のアロケータを使うと性能をひどく台無しにし、ほとんど過失と言ってよいほどだったmusl には SIMD 最適化された文字列比較ルーチンのようなものもない。非自明なプログラムでこの種の処理にどれほど多くの CPU サイクルが使われているかを知れば驚くだろうし、実際のプロファイルにもはっきり表れ、これを改善するとほぼすべてのプログラムが普遍的に良くなる。glibc の最適化ルーチンは良いが、それでもまだ速くできそうに見える
こうしたものは「一つのアーキテクチャにだけ特化して一般化できない最適化」ではない。特にこの二つの領域は、ほぼすべてのワークロードで実時間を 2〜5 倍短縮し、長時間のワーキングセット利用率も大きく改善する、よく研究され理解された領域だ。ではなぜ採用されなかったのか。いつものように、他にやることがあったか、musl のように最高性能より単純さを優先する相反する優先事項があったからである可能性が高い
こうしたプロジェクトを責めているわけではない。誰も「私のプログラムはひどく遅く、何もまともにできないように設計しており、私はそれを誇りに思っている」とは言わない。ただ、そのプロジェクトの作業者たちが完璧なパレート境界だけを選んで設計したという考えはまったく現実的ではなく、多くのプロジェクトが実際に動いている姿を捉えていない
glibc や C++ 側の同等物で何かを変えるには永遠に時間がかかる
同期プリミティブにはいくつもの種類があるが、pthreads はその一部しかサポートしていない。それに自分を縛ると、たいてい性能を手放す代わりに移植性を得ることになる
libc のメンテナについては知らないが、いくつかを保守している立場としては、最新研究を実装しようとは思わない。安定性を保ち、性能が許容範囲かを確認しようとする。研究実装は私の「保守」予算の外にある
ある男と統計学者が道を歩いていて、50ユーロ札を見つける。統計学者は歩き続け、男は立ち止まって「見てください、地面にお金があります」と言う。すると統計学者は「偽物でしょう。本物なら誰かがもう拾っているはずですから」と言って歩き続ける。もう一人の男がそのお金を拾っていく
スレッドとミューテックスは、計算機科学で最も複雑さを生む要素だ。新しい実装は、何年も大規模に使われるまでは常に懐疑的に見る
こうしたスレッディング機構のバグは、最も厳しいレビューすらすり抜けることが多い。90年代半ばに Java が登場したとき、Solaris のあらゆるスレッドやミューテックスのバグが露呈した
必要なのは最速のミューテックス実装ではなく、信頼できる実装だ
このコードはミューテックスロック性能ではなく、ミューテックス競合をベンチマークしている。こういう形でロックを使っているなら、コードを見直すべきだ
各スレッドは
g_choresをインクリメントするたびにミューテックスをロックして解除する。そのため、ミューテックスを頻繁に取得・解放するオーバーヘッドが生じ、スレッドごとに 100,000 回繰り返されるこのオーバーヘッドが、ロック機構間の実際の性能差を覆い隠す。ベンチマークが実作業ではなくロック競合に支配されているからだ。こういうベンチマークは役に立たない
Justine とその仕事のファンだが、これはおそらくミューテックスのベンチマークテストケースとしては最も面白くない部類だ。複数のスレッドが同じミューテックスを叩き続ける状況は、そもそも避けるべきだ
なので、どのミューテックス実装がこのケースを最もうまく処理するかは、あまり面白くないと思う
重要な点を一つ見落としていたが、競合状況で性能の悪いロックは、メモリネットワークにホットスポットを作るなど、非常に悪いシステム的影響を及ぼし得るし、それもここで現れるはずだ
同じミューテックスに複数のスレッドが集中するケースはいくつか思い浮かぶ。簡単な例として、リストや辞書のようなデータ構造を同時に埋める作業がある
メッセージパッシングでもできるが、メモリをより多く使い、共有位置に書き込むために待つより遅くなることもある
本番環境は、速度、効率、あるいは明らかに「賢いハック」に関するものではない
日曜の午前3時に壊れたシステムを直すために呼び出されない保証のために効率の 50% を犠牲にする必要があるなら、毎回その選択をする
本番環境は信頼性に関するものであり、信頼できるコードを書くことは「速い」コードを書くことより 10 倍難しい