最速のミューテックス

10月2日^nd、2024 @ ジャスティンのウェブページ

コスモポリタンLibc でよく知られています ポリグロットファットバイナリ AMD64 / ARM64 の 6 つの OS で実行可能ファイルを実行できるようにするハック。驚かれるかもしれませんが、これは実稼働ワークロードにも最適な C ライブラリである可能性があります。この点を実証するために、Cosmo のミューテックス ライブラリを他のプラットフォームと比較してみましょう。

これを行うには、次のような単純なテストを作成します。 30 スレッド 同じ整数をインクリメントします 10万回。これは、競合の激しいユースケースでミューテックスの実装がどの程度うまく機能するかをテストします。本質的に、これは次のことを意味します (完全なソース コードについては、ページの下部にあるセグメントを参照してください)。

int g_chores;
pthread_mutex_t g_locker = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
  for (int i = 0; i return 0;
}

それでは、興味深い部分から始めましょう。これが私のベンチマーク結果です。

ベンチマーク

時間はマイクロ秒単位で測定されます。経過時間は、テスト プログラムの実行にかかる時間です。これには、スレッドの生成と結合のオーバーヘッドが含まれます。ユーザー時間はユーザー空間で費やされた CPU 時間であり、システム時間はカーネルで費やされた CPU 時間です。複数のスレッドが並行して実行されているため、システム時間とユーザー時間は実際の所要時間を超える可能性があります。

Mark Waterman が素晴らしい成果を上げたため、最初に示す結果は Windows に関するものです。 ミューテックス銃撃戦 3 か月前、同氏は「激しい競争のシナリオでは、Windows が SRWLOCK で勝利を収めた」と述べました。競合は、ミューテックスの実装が不平等を示す場所です。 Mark は Microsoft の SRWLOCK に非常に感銘を受け、Linux と FreeBSD のユーザーに対して、ミューテックスの競合が問題になる場合は Windows をターゲットにすることを検討するよう勧めました。

ご覧のとおり、Cosmopolitan Libc ミューテックスは、Microsoft の SRWLOCK (以前は最高のものだと考えられていました) よりも 2.75 倍高速でありながら、消費する CPU リソースは 18 分の 1 です。 Cosmopolitan のミューテックスも、Cygwin より 65 倍高速でした。Cygwin は、Cosmopolitan と同様に Windows 上で POSIX 実装を提供します。 Cygwin のミューテックスは非常に悪いので、このユースケースではスピン ロックのみを使用した方が良かったでしょう。

次に、すべてのオペレーティング システムの王である Linux について説明します。

ここでは、Cosmopolitan ミューテックスが次のとおりであることがわかります。

• glibc よりも 3 倍高速
• musl libc より 11 倍高速
• glibc よりも 42 倍少ない CPU 時間
• musl libc よりも 178 倍少ない CPU 時間

実際に物事がどのように機能するかを次に示します。すべてのスレッドがシリアル化された操作を実行する必要があるワークロードがあると想像してください。 Cosmo では、htop を見ると 1 つのコアだけがアクティブであるように見えますが、glibc と musl libc は CPU メーター全体を埋め尽くします。同じサーバー上で多数のジョブを実行している場合、これは悪い知らせです。サーバーの 1 つだけでミューテックスが発生した場合、cosmo を使用していない限り、すべてのリソースが失われます。これはまだ新しい C ライブラリであり、少々荒削りな部分があります。でも、とても良くなって、とても早くなっているので、見え始めています ない それを本番環境で使用することは、専門的な責任を放棄することになります。 C ライブラリはソフトウェア サプライ チェーンに深く組み込まれており、非常に依存しているため、地球を破壊するものにはなりたくないでしょう。必須の疑いのないツールがこれほど無駄であるなら、Amazon Cloud がこれほどの富を生み出すのも不思議ではありません。

最後になりましたが、MacOS があります。

M2 ARM64 マイクロプロセッサを搭載した MacOS では、Apple の Libc は Cosmopolitan のミューテックスよりわずかに優れています。理由はまだ完全には理解できませんが、Cosmopolitan の通常のミューテックス実装はこのプラットフォームではうまく機能しません。おそらく、M2 と XNU がリーグに参加しているためです。そのため、MacOS ARM では、Cosmopolitan は Ulrich Drepper の「」に基づいたより単純なアルゴリズムを使用します。フューテックスは難しい「基本的に、XNU の ulock システム コールに対するすべての重労働を省くだけの論文です。そのため、パフォーマンスは Apple のパフォーマンスとほぼ同じです。」

要約すると、これらのベンチマーク結果は、競合 + 小さなクリティカル セクションのユースケースでは、最良の場合、Cosmopolitan ミューテックスが代替より圧倒的に優れており、最悪の場合、Cosmopolitan がほぼ同等であることを示しています。

どうやってやったか

Cosmopolitan Mutex が優れている理由は、 というライブラリを使用したからです。 nsync。 GitHub には 371 個のスターしかありませんが、これを書いたのは Mike Burrows という Google の著名なエンジニアです。彼が誰なのか知らない人のために説明すると、彼は Google の最も強力な競合相手である Altavista をコーディングした人物です。 Altavista を覚えているほど年齢が高くない方のために説明すると、Altavista は最初の優れた検索エンジンであり、1 台のコンピューター上で動作しました。

nsync を Cosmopolitan に統合するのはとても楽しかったです。上流に貢献する機会もありました。たとえば、私は何年も発見されなかったミューテックスのロック解除機能のバグを見つけて修正しました。また、C11 アトミックを使用するように移植することで、競合する nsync ミューテックスを AARCH64 上の nsync アップストリームより 30% 高速化することにも成功しました。私は、実行時の移植性を可能にする futex などの新しいシステム統合を作成しました。最後に、POSIX スレッドのキャンセルでシームレスに動作するようにしました。

では、nsync はどのように行うのでしょうか?どのようなトリックが使われているのでしょうか？以下に私の見解と分析をいくつか示します。

• nsync はオプティミスティック CAS (比較とスワップ) をすぐに使用するため、競合がない場合はロックがすぐに行われます。

• ロックを取得できない場合、nsync は呼び出しスレッドをウェイターの二重リンク リストに追加します。各ウェイターは、別個の独立したキャッシュライン上で独自のセマフォを取得します。これは重要な目的を果たします。スレッドが待機状態に入ると、メイン ロックに触れなくなります。それがなぜ重要なのかを理解するには、ウルリッヒ・ドレッパーの論文「」を読んでください。すべてのプログラマーがメモリについて知っておくべきこと彼は、最新のマイクロプロセッサで使用されるコヒーレンシ プロトコルについて深く掘り下げています。このプロトコルでは、コアは基本的に、どのキャッシュラインを使用しているかについて内部で互いに通信します。複数のコアが同じコアにアクセスすると、内部で大量の通信オーバーヘッドが発生します。プロセッサー。

• nsync は、futexes を使用してオペレーティング システムの助けを借ります。これは数年前に Linux によって発明された優れた抽象化であり、すぐに他の OS に導入されました。 MacOS では、futex は ulock と呼ばれます。 Windows では、futex は次のように呼ばれます。 WaitOnAddress()。 Cosmo がサポートする futex を持たない唯一の OS は NetBSD です。NetBSD はカーネル空間に POSIX セマフォを実装しており、残念ながら各セマフォには新しいファイル記述子を作成する必要があります。しかし、futex とセマフォについて重要なことは、これらによって OS がスレッドをスリープ状態にできるということです。これにより、何もすることがないときに nsync が CPU 時間を消費することを回避できます。

• nsync は、この「長い待機」の概念により飢餓を回避します。ウェイターが 30 回ウェイクアップされ、毎回内部でロックの取得に失敗した場合、nsync はロックにビットを追加して、まだ待機していないスレッドが取得できないようにします。これは、キューがクリアされるまで時間がかかるまで、最初の最初の CAS は他の全員に対して失敗することを意味します。

• nsync は、この「指定されたウェイカー」の概念を使用して、ベンチマークしたユースケース (小さなクリティカル セクションによるロックの競合) を高速化します。メイン ロックのこのビットは、スレッドが起動していてロックを取得しようとしているときに設定されます。 nsync では、ロック解除関数は、ロックを待っている次のスレッドをウェイクアップする役割を果たします。このビットがあると、ロック解除スレッドは、2 番目のロッカーがすでに起動しているため、わざわざ 2 番目のロッカーを起動する必要がないことを認識できます。

nsync の秘密をさらに詳しく知るには、ここでソース コードを読むことができます。
cosmopolitan/third_party/nsync/mu.c。こちらも参照
cosmopolitan/libc/intrin/pthread_mutex_lock.c。

オンライン証明

Cosmo ミューテックスを使用して構築されたソフトウェアのライブ デモを見たい場合は、最悪の DDOS を実行してください。
http://ipv4.games/ ウェブサーバー。これはまさに、インターネットを支配するために競う、ハッカーのためのゲームです。あなたの IP がちょうど jart のために要求されたので、あなたはすでにこのゲームをプレイしています。このサービスは 2 コアの GCE VM 上で実行されており、これまでのところ、49,131,669 個の IP もの規模のボットネットによる DDOS 攻撃に耐えることができています。その多くは nsync のおかげで、SQL クエリをバックグラウンド スレッドに移動してメッセージを相互に送信できるようになりました。まだまだ改良の余地はありますが、全体的には良くまとまっています。監視することもできます /状態 健康指標。

ソースコード

#define ITERATIONS 100000
#define THREADS    30

int g_chores;
pthread_mutex_t g_locker = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
  for (int i = 0; i return 0;
}

struct timeval tub(struct timeval a, struct timeval b) {
  a.tv_sec -= b.tv_sec;
  if (a.tv_usec return a;
}

long tomicros(struct timeval x) {
  return x.tv_sec * 1000000ul + x.tv_usec;
}

int main() {
  struct timeval start;
  gettimeofday(&start, 0);

  pthread_t th[THREADS];
  for (int i = 0; i struct rusage ru;
  struct timeval end;
  gettimeofday(&end, 0);
  getrusage(RUSAGE_SELF, &ru);
  printf("%16ld us realn"
         "%16ld us usern"
         "%16ld us sysn",
         tomicros(tub(end, start)),
         tomicros(ru.ru_utime),
         tomicros(ru.ru_stime));
}

私たちが論争のケースに注目する理由は、それがミューテックスの実装が不平等を示す場所だからです。競合していないミューテックスは通常、どの実装でも同じように実行されますが、その場合でも、数行しかかからないスピン ロックを使用した方がよい場合があります。

void spin_lock(atomic_int *lock) {
  if (atomic_exchange_explicit(lock, 1, memory_order_acquire)) {
    for (;;) {
      for (;;)
        if (!atomic_load_explicit(lock, memory_order_relaxed))
          break;
      if (!atomic_exchange_explicit(lock, 1, memory_order_acquire))
        break;
    }
  }
}

void spin_unlock(atomic_int *lock) {
  atomic_store_explicit(lock, 0, memory_order_release);
}

スピン ロックは実際には他に選択肢がない場合にのみ使用すべきであることに注意してください。これらは、極端な低レベルの制約によって特別なことは一切許可されないカーネルで役立ちます。スピン ロックは、nsync ロックの実装の詳細にも役立ちます。しかし、全体的には悪いです。多くの開発者は自分たちが優れていると信じていると思います。もしそうなら、それはおそらく、ウォールタイムのベンチマークしか行っていないからでしょう。ロックを使用する場合は、CPU 時間を考慮することも重要です。だからこそ私たちは
getrusage()。

The Fastest Mutex の資金調達は Justine Tunney からクラウドソーシングされました。 GitHub スポンサー
そして パトレオン購読者、の裏付け
Mozilla の MIECO プログラム、そして私たちの寛大な貢献
開発者コミュニティ ディスコードで。皆さんのご支援がコスモポリタンのようなプロジェクトを可能にします。ありがとう！