Peredvizhnikovエンジン: C++20で書かれたロックフリーのゲームエンジン

 (github.com/eduard-permyakov)
4 ポイント 投稿者 GN⁺ 2023-09-11 | 1件のコメント | WhatsAppで共有
  • C++20で書かれた完全なロックフリーゲームエンジンで、言語のコルーチンプリミティブ上に並行計算のアクターモデルを実装
  • アクターモデル抽象化を使うことで、スレッド間同期の詳細から切り離された状態で複雑な並列ロジックを開発可能
  • 完全なロックフリー実装により、任意のスレッド終了状況でも進行保証、デッドロック防止、重要イベントへの応答の予測可能なレイテンシ、耐障害性を提供
  • ワーカースレッドの1つが非同期に終了しても、エンジンが動作を継続することを保証
  • 実装には、Software Transactional Memory、ロックフリーキュー、ロックフリー直列化プリミティブ、std::atomic_shared_ptr、ロックフリースケジューラ、ロックフリーメモリアロケータ、コンパイル時DAG などが含まれる
  • ロックフリーアルゴリズム、設計根拠、ベンチマークは、Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler 文書で扱われている
  • データ指向設計を支援するため、コンポーネント単位のアクセスに最適化され、大規模データセットをサポートするインメモリデータベースを実装
  • インメモリデータベースは、Flat Hash MapとBitwise Trie with Bitmapデータ構造を基盤としている
  • 現在サポートされるプラットフォームはLinuxのみで、ソースのビルドにはClang++ 16が必要
  • ソースコードはGPLv3ライセンスで提供され、一部または全コードを別ライセンスで利用する権利が個別に付与される場合がある

関連記事

1件のコメント

 
GN⁺ 2023-09-11
Hacker Newsのコメント

  • Actorフレームワークでは、メソッドポインタのキューに普通の std::deque を使い、メッセージをキューに入れるときは Benaphore 方式でロックしている
    もともとはFutexのように、アトミック操作とロックプリミティブを併用するものだが、私のロックプリミティブはリトライ回数に応じてスピンロック/ミューテックスの組み合わせとして動作する。ベンチマーク上、メッセージのpush関数がブロックされることは非常にまれで、OSのコンテキストスイッチが起きる可能性も低いため、たまにロックされたスレッドがスワップアウトされても、ロックフリーアルゴリズムのコストを正当化できるほど頻繁には起こらない
    要するに、ロックフリーキューより非ロックフリーキューのほうがはるかに速いが、誰もロックを取得できないコンテキストスイッチによって、ごくまれに長い遅延が発生することは受け入れる必要がある。現代のハードウェアでは、ワーカースレッドごとに毎秒 1,000万メッセージ をキューに入れられる

    • 「もともとはFutex」と言っていたが、Benaphore はかなり古いアイデアであり、Futexは単に「Linux式Benaphore」ではない
      肝心なのは、カーネルオブジェクト、つまり別個のロックプリミティブが実際には不要だという点にある。このアイデアが「誰でも知っているやり方」から「OSに今すぐ入れるべき機能」へ変わるのはそこだ
      Futexの設計では、衝突処理のためのOS同期オブジェクトの代わりに、OSがアドレス→スレッドの対応リストを保持する。スレッドTがアドレスXのfutexで眠ると、XがTを指すようにリストへ入り、Xのfutexを起こせという要求が来ると、OSがリストを走査してTを起こす
      違いは制限に現れる。Benaphoreのようなものは高価なシステム全体のリソースなので、BeOSではマシンあたり6万5536個程度しか許可していなかったと記憶している。しかしFutexは単なるメモリなので、制限を設ける理由がない
    • こういう興味深い記事なら、コードへのリンクを張るべきだ。主張の裏付けにもなるし、私のような人間はアイデアが面白くて、すぐ実装を見たくなる
    • 細かい状況によって大きく変わる。競合が多いと性能は急激に落ち、アトミック命令でさえボトルネックになり得る（https://stackoverflow.com/q/2538070）
      多くの場合は、単にロックを使って気にしなくてよい、という観察は正しいと思う。ただし、もっと良くできるアプリケーションや状況もある。コンシューマが1回のロック操作でキュー内のすべての項目を取り出し、プロデューサがコンシューマへシグナルを送る方式も、注意すればキューの効率とスループットを高められる。たとえば項目を入れるたびにシグナルを送るのではなく、キューが空の状態から空でなくなったときだけ送るべきだ
    • ロックフリーのデータ構造は、競合が少ないときにスループットを上げるというより、競合の影響を減らすことに意味があるのでは？
    • その「コストが許容できる」というのは、言及されている予測不能でまれな長い遅延が絶対に発生してはならないという強い要件を持つ人たちには例外だ

  • ロックフリーのスケジューラは確かに興味深く見えるし、特にイベントブロードキャストの線形化可能性が目を引く。ただし論文のベンチマークでは、actor 12ペア（そして12コア？）での最高が毎秒4万3500メッセージで、単一コアのグラフも毎秒約5000メッセージなので、この種のベンチマークとしては驚くほど低い
    エンジンがLinuxと、より重要なことにx86を要求しているため（アセンブリ命令のため）、まだ再現できていないが、actor 1ペアあたり少なくとも毎秒約100万リクエストは期待する。Erlangのような場合を考えると、それより低ければオーバーヘッドが許容できないほど大きくなる
    このエンジンはメッセージパッシングに注力しているが、経験上この方式は非常に扱いにくい。状態機械は難しく、複数の下位actorと一緒に作業するとさらに難しくなる。本質的にactorは、メッセージパッシングというより、ロックなしで状態を隔離するものに近いと思う。Swift actorsはうまくやったと思っていて、メッセージの代わりにメソッド呼び出しを使うと推論しやすいだけでなく、実行時にコンテキストが変わり得る箇所を追加で示してくれ、必ずしもスケジューラを介入させる必要もない。共有状態は遅く、スケーラビリティを損なう
    最近、C++20コルーチンでSwift actorsに似たものを実装したヘッダーオンリーライブラリを作った。興味があれば「coroactors」で探せばよい。競合がないときは毎秒約 1,000万リクエスト、競合がありスケジューラに依存する場合は毎秒100万〜300万リクエストでも、オーバーヘッドが大きすぎると思った。特に、ミューテックスで保護した共有状態に対する通常のメソッド呼び出しと比べるとそうだ。コルーチンは伝染しやすく、ますます多くの関数が async コルーチンになり、非自明なコードベースではコルーチン呼び出しやメッセージパッシングが増える。だからオーバーヘッドは可能な限り低くなければならず、そうでないと有用な仕事をするよりもタスク切り替えに多くの時間を使うことになる

  • actor ベースとされており、actor にメッセージを送ることは、ミューテックスの下で actor 関数を実行するのと同等だと説明している。つまり N 個のスレッドがメッセージを送っても、actor のコードを実行するスレッドは 1 個なので、ミューテックスのように直列化される。
    だから技術的には「完全にロックフリー」ではあり得ても、actor を使う以上、並列化の改善はない。

    • 必ずしもそうではない。ミューテックスベースの actor では、actor スレッドが中断されると、元のスレッドが再開されるまで、そのミューテックス、つまり actor のコードはロックされたまま残る。中断されたスレッドが所有するミューテックスがロックされているため、並列性がさらにあっても、その actor コードを「再起動」したり「再開」したりはできない。
      この実装は、すでに進行中だが中断された actor の作業を、別の並列スレッドが拾って続行できるように、再開可能な関数に大きく依存している。優れた設計ドキュメントの 3 ページを見ればよい: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      だから厳密には「より並列的」ではないかもしれないが（actor の数は同じなので）、同じ作業集合を完了するために、より多くの並列性をうまく活用しているように見える。
    • 「actor にメッセージを送ることは、ミューテックスの下で actor 関数を実行するのと同等だ」という話はどこにあるのか？ 私の理解では、actor モデルはメッセージ渡しと非同期実行を意味する。むしろ actor が N 個あれば、N 個のスレッドが並列に実行され得る。
    • 並列化の改善がないというのは正しいが、並列性を減らすものでもない。並行性を考えるための別のやり方であり、私にとってはより簡単なやり方だ。
      考えやすければ、同じリソース上でどこに競合が生じるかも見えやすくなり、実際に潜在的な並列性を改善する助けになる。SMP が高速化できる特定の機会に気づいたら、actor モデルから少し外れて、メッセージキューを複数スレッドが受け取るようにできるし、それが不可能なら actor をさらに追加してデータをよりよく分割すればよい。

  • STM の競合が激しいクリティカルセクションを、従来のミューテックス実装と比較してデバッグしたりプロファイリングしたりした人はいるだろうか？ 結局、共有メモリへの同時アクセスを仲裁する何かは必要で、ただ飯はない。ミューテックスは最適化、プロファイリング、理解が非常によく進んでいる。
    一方で STM も同じ水準なのかはよく分からない。トランザクションが無限に（？）再試行されることもあるのでは？

    • この場合、仲裁者はスケジューラだ。実際に非同期ブロックを呼び出し、失敗すれば潜在的に再試行する主体である。元のコードには、一度に 1 つのアクセスを保証するためのアトミックブロック、ブロックの逐次実行、状態を持つブロックなどがある。
      中核は scheduler.cpp で、std::coroutines を使っている。
      他の言語の async/await に似ている。スケジューラには作業（コルーチン）のキューと、それを実行するスレッドプール（N>0）がある。
      ここではデータを持った作業同士がメッセージをやり取りする。メモリ使用量が増える代わりに、ロックは必要ない。
    • 実際、飢餓のない STM ではトランザクションの再試行回数が制限される。一例として 2PLSF があり、ほかにも複数の方式がある https://zenodo.org/record/7886718

  • BEAM っぽい？
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • こういうエンジンをデバッグするのがどれほど難しいかについての言及は見当たらなかった。

  • 実装を読む時間はないが、README だけを見ると、ゲームスレッド間の古典的な分散システムのように聞こえる。リトライ・バックオフのようなパターンがよく出てきそうだ。

  • ロックフリーは格好よく聞こえるが、意味のあるレベルでアトミック操作を使うコードには、形式的で、できれば機械検証された証明が伴うべきだと思う。逐次一貫性ではないアトミック順序を正しく使うのは難しすぎる。間違って書かれたコードを何度も見てきたし、そこから生じるバグは最悪だ。

  • ゲームデモはどこにあるのか？ 今どきゲームエンジンとして見るなら、実際のツール、Maya や 3DSMax のようなエクスポータ、そしてコラボレーション用のツール・指標・通知のようなものも必要だ。

    • 同意しない。「ゲームエンジン」が必ずしも「Unity や Unreal を置き換えられるもの」を意味するわけではない。

  • 「ロックフリー」と言っているが、まだそうではなさそうだ。
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent