WLSとwindowsで実行した時に2倍も速度に差が出る

Question

Rustでゲームの手筋を全探索して最適解を導き出すプログラムを作ったのですが、高速化の為に色々試している内に、WSLで実行すると2倍の速度で実行されることが分かりました。
私はこれの理由が何か全く検討も付かないので、あり得る理由をご教授願いたいです。いくらlinuxが早いとはいえ、倍速になるのは何らかの理由があると思うのですが…

以下、プログラムの中で関係のありそうなところを挙げます。

プログラムの内部では、並列処理を実装していて、実行されるとプレイヤーが取り得る全てのパターンに対してそれを計算するスレッドを複数生成し、そのスレッドがまたスレッドを複数生成していて...というように再帰しています。また、スレッドが増えすぎないように以下のコードを実装しています。

macro_rules! spawn_thread {
    ($counter:expr,$limit:expr, $y:expr ) => {{
        if *$counter.lock().unwrap() < $limit {
            let counter = $counter.clone();
            let closure = move || {
                let temp = $y();
                *counter.lock().unwrap() -= 1;
                temp
            };
            *$counter.lock().unwrap() += 1;
            thread::spawn(closure)
        } else {
            let temp = $y();
            thread::spawn(move || temp)
        }
    }};
}

counterはArc<Mutex<usize>>で初期値は0、limitはconstのusizeで1000となっています。

また、計算結果を再利用するため以下のようなhashmapを利用しています。

RwLock<FxHashMap<X , Y>>

FxHashMapはfxhashというクレートの物です。スレッドが生成される度にこれにアクセスし、計算結果が存在していればそれを利用し、存在しなければ計算して格納します。読み込みと書き込みは同程度起きています。

Answer 1

お使いのRwLockはstd::syncモジュールが提供しているものでしょうか？　もしそうなら、それによってOSで差がつくかもしれません。

一般的な話として、Reader-Writerロックを実装する際、Readerロックの要求とWriterロックの要求が同時にあったときに、どちらを優先するか決める必要があります。

たとえば、Readerロックを優先する場合は、以下のようになります。

• すでに1つ以上のReaderロックが有効なとき、たとえ待機中のWriterロックがあったとしても、後から来たReaderロックが優先される。
• 全てのReaderロックが解放されるまで、Writerロックは待たされる。

Rustのstd::sync::RwLockは、この優先順位ポリシーを自身では定義（実装）せず、OSの実装に依存するようになっています。

https://doc.rust-lang.org/stable/std/sync/struct.RwLock.html

The priority policy of the lock is dependent on the underlying operating system’s implementation, and this type does not guarantee that any particular policy will be used.

そして、私の記憶が正しければ、Linux上ではReaderロック優先になっています。

ここからは想像ですが、Windows上では別の優先順位ポリシーが採用されているのではないでしょうか。そして、質問者様のワークロードは、たまたま、Readerロック優先の方が効率的に動くのかもしれません。

このようなことが起こっているかの確認方法の一つに、優先順位ポリシーがOSに依存しないReader-Writerロックの実装を試してみることがあります。たとえば、parking_lotクレートのRwLockはeventual fairnessというポリシーを採用しており、どのOS上でも同じように動作します。

https://docs.rs/parking_lot/0.12.1/parking_lot/type.RwLock.html#fairness

This rwlock uses eventual fairness to ensure that the lock will be fair on average without sacrificing throughput. This is done by forcing a fair unlock on average every 0.5ms, which will force the lock to go to the next thread waiting for the rwlock.

これを使ってみて、LinuxとWindowsでどのように性能が変わるかを確認してみるのはいかがでしょうか？　もしstd::sync::RwLockが理由なら、parking_lot::RwLockを使うことで性能差がなくなるかもしれません。

追記 2022-10-29

std::sync::RwLockの優先順位ポリシーについて、追加情報があります。

• Linux版は今年6月にリリースされたRust 1.62からwriterロック優先に変更されたそうです。
  • Rustの日本語コミュニティーで 教えてもらいました。
  • 変更のpull request：https://github.com/rust-lang/rust/pull/95801#issue-1197239940
• Windows版は最近はOSが提供するSlim Reader/Writer (SRW) Locksを内部で使用しているそうです。
  • このチケットに書かれていました：https://github.com/rust-lang/rust/issues/93740
  • Microsoftのドキュメントによると、SRWは優先順位ポリシーを持たない（ロックが取得される順序を保証しない）ようです。
    • "There is no guarantee about the order in which threads that request ownership will be granted ownership; SRW locks are neither fair nor FIFO"

また、家族のWindows PCを借りて自分でも試してみました。（普段私はMacを使っていて、Windowsのことはあまり分かりません）

• Windows 11 Home
• WSL 2 Ubuntu 22.04
• Intel Core i7-12700Fを搭載しており、4つのEコア（高効率コア）と8つのPコア（高性能コア）がある
• Rust 1.64.0
• テストプログラムには、Rustで書かれたBitonic sorter（並列ソートアルゴリズムのひとつ）を使用
  • https://github.com/ghmagazine/rustbook/tree/master/ch03/bitonic-sorter

以下のことが分かりました。

• 電源オプションの電源モードがデフォルトの「バランス」に設定されていると、マルチスレッド、シングルスレッドに関係なく、WSLに対して性能が落ちる
  • シングルスレッドで1.6倍の時間がかかった
  • マルチスレッドで4.5倍の時間がかかった
  • Eコア（高効率コア）しか使われていない！
• 電源モードを「最適なパフォーマンス」に変更したところ、WSLに近い性能が出るようになった
  • シングルスレッドで1.1倍の時間がかかった
  • マルチスレッドで1.05倍の時間がかかった
  • 全コア使われているが、クロック周波数がやや低い

Windows 11 Homeでは電源オプションに応じたCPUスロットルがかかっており、パフォーマンスを優先する設定にしても完全には解除されないのかもしれません。

追記その2 2022-10-29

• テストプログラムには、Rustで書かれたBitonic sorter（並列ソートアルゴリズムのひとつ）を使用

そのプログラムはロック競合をほとんど起こさないものだったので、あまり参考にならなかったかもしれません。別のプログラムで試してみました。電源モードは「最適なパフォーマンス」に設定しています。

• 128スレッドで並行処理し、
• ロック競合が多発するケースではWindowsの方がLinxuよりも1.7倍ほど遅い
• 多発しないケースではWindowsの方がLinxuよりも1.6倍ほど速い

性能差があることが確認できましたが、このプログラムはかなり複雑なことをしており、調査には適さないです。調査用にシンプルなプログラムを書いて調べてみたいと思います。（途中経過はRustの日本語Zulipチャットに書いていきます）

Comments

[Watching]

正にその通りでした。ありがとうございます！
優先順位ポリシーが設定できるようなRwLockを探してみたのですが見つからなかったので、バッファを用意して溜まったらロックを取って書き込みするなどの方法で対応しようと思います！

[Watching]

正にその通りかと思っていましたが、違いました。parking_lotに変更したら同じ速度で動作しているかのように見えました。しかし、スレッド数の上限を100に制限したら、高速になった上に、更にWSLの方が2.5倍早くなるという現象が起きました。恐らくそれまではスレッドが多すぎたせいで同じ資源を取り合ってスレッドがブロックされていたようです。
関係ありそうに思えたRwLockですが、あまり関係なかったらしく、結局振り出しに戻ってしまいました。色々検証するのも疲れてしまったので、単純にlinuxの方が資源のロック、スレッド生成などの操作が得意だから早いだけなんじゃないかという事で納得したくなっています。どう思われますか？

[tatsuya6502]

parking_lotにしても差がついてしまいましたか...。回答に追記したのですが、家族のPCを借りて自分でも試してみたところ、その環境では電源モードの設定が「バランス」になっていたため、WSLと性能差がありました。「最適なパフォーマンス」に変更したところ、WSLに近い性能が出るようになりました。

またRustのRwLockのポリシーについても追記しました。