1

自作ゲームで木構造のシーングラフを持っています。
親ノードは複数の子ノードを持ちゲームの進行に応じてノードが追加されたり削除されたりします。ようはコレクションの変更です。async/await を使った非同期プログラミングでこれを行うとタイミングによっては foreach でぐるぐる回している最中に別スレッドからコレクションを変更することになり例外が発生します(これ自体は当然の動作)。

質問は非同期プログラミングでのコレクション操作のベストな方法を教えて下さい、という事です。

  1. SemaphoreSlim で排他制御を行う
  2. コレクションを必ず ToArray() でコピーしてから使う
  3. 追加および削除を1つのスレッドで行うようにロジックを変更する

どれも一長一短で決めかねています。ご意見をお聞かせ下さい。


回答を考慮して追加

  1. System.Collections.Concurrent 名前空間のスレッドセーフなコレクションを使用する
  2. System.Collections.ImmutableList 名前空間の不変なコレクションを使用する

4.はConcurrentBag, ConcurrentStack, ConcurrentQueue, ConcurrentDictionaryなど。既存のListに比べて呼び出し方法が大分異なる。基本はキューとスタックなのでProducer-Consumerパターン。
5.は.Net標準ではないがマイクロソフト提供のライブラリ。NuGetでインストール可能。「不変」(Immutable)なコレクションなのでマルチスレッド環境でも問題が起きない。コレクションの変更はコピーして変更を加えて差し替えるので比較的コストが高い。参照するだけなら問題はない。

排他制御がコードに現れない、既存のListとほぼ同様のインターフェースを持つ、書き換えはそんなに起きないので無視できる、などを評価して5番のImmutableListがベストですね。
今のところ.Net標準ではないですがそのうち標準として取り込まれるような気がします。これは便利だ。

4
  • 興味深い話題だと思うのですが、コレクションを更新/参照するスレッド(タスク)の数や頻度に前提はおけるでしょうか?
    – yohjp
    Commented 2015年1月30日 11:13
  • 3
    ベストプラクティスというのは主観的なものなので、やはりタイトルが気になりました。質問文では例外を防ぎたいとのことなので、それに即したタイトルにしたほうがわかりやすくなると考えます。
    – 3100
    Commented 2015年1月31日 7:14
  • 1
    ベストプラクティスは主観的なものではありません。普遍的で多く人間の経験に基づいた最適解です。とはいえ文言自体はどうでもよくてマルチスレッド環境下でのコレクションの操作はどうあるべきかというのが問題の本質です。
    – プリン
    Commented 2015年1月31日 12:00
  • 必ず同期を取る必要があるケースと、多少の誤差があっても構わないケースで対応方法が異なると思います。後者であればスナップショットを取ればいいので.ToArray()、非同期系のコレクションを使用できますが、そうでない場合、lockすべきでしょう。
    – PITA
    Commented 2015年2月1日 2:01

4 件の回答 4

6

System.Collections.Concurrent名前空間のコレクションを使用します。
この名前空間に属するコレクションは、非同期に同時アクセス可能です。
lockする必要は、ありません。

もう一つの方法としては、System.Collections.Immutable名前空間に所属する
不変コレクションを使用します。
不変コレクションは、コレクションの変更を行うと新しいコレクションへの参照が作成されます。

System.Collections.Immutableは、標準では利用できないかも知れません。
nuget経由で導入することができます。

これらのコレクションを使用すると、lockフリーにプログラミング可能になります。
列挙操作中にコレクションを変更しても例外は、発生しません。

5

当該コレクションへの、Read/Writeの頻度がRead>Writeである場合、

  • System.Threading.ReaderWriterLockSlim

の利用を検討してみるのもありかもしれません。
但し、一般的なMonitorを使ったLockよりは、オーバーヘッドが大きめなので、たとえば、頻度がWirte>Readのような場合は、かえって効率が悪化する可能性があります。

個人的には、

  1. System.Collections.Concurrent名前空間内のコレクションの利用を検討する
  2. System.Collections.Immutable名前空間内のコレクションの利用を検討する
  3. その他の方法を検討する

というプライオリティで検討することが多いことを付言します。

3
  • 1
    尚、蛇足に過ぎますが、Monitorにせよ、ReaderWriterLockSlimにせよ、スレッドアフィニティが必要としますから、async付のメソッド出利用することはできません。 ですから、この場合、排他制御が必要な部分をTaskに封じる形でawait付で呼び出すのが良いかと思います。
    – 時計屋
    Commented 2015年1月31日 10:39
  • 1
    FYI: 本家SOの回答"ReaderWriterLockSlim and async/await"にasync用のReader-WriterLock実装例がありました。
    – yohjp
    Commented 2015年2月2日 1:35
  • 些末でTaskにいれるまでもないけど、制御したいみたいなシナリオでは可読性も上がって良い感じですね。 ご教授いただきまして多謝でした!
    – 時計屋
    Commented 2015年2月2日 3:20
4

木構造のシーングラフ(以下ツリーと呼びます)に一貫性を保たないといけない前提で回答しています。
そうでない場合はSystem.Collections.ConcurrentやSystem.Collections.Immutableのコレクション(以下ロックフリーコレクションと呼びます)を使えば十分だと思います。

解決案1 ツリーをロックする

通常async/awaitパターンを使うとlockステートメントが自由に使用できなくなりますが、その解決案としてusingを使えるようにしたものがあります。

非同期:awaitを含むコードをロックするには?(AsyncLock編)
Building Async Coordination Primitives, Part 6: AsyncLock

ReaderWriterLockを使いたい場合はこちらを選択します。
Building Async Coordination Primitives, Part 7: AsyncReaderWriterLock

AsyncLockの使用例

readonly AsyncLock _lock = new AsyncLock(); 

async HogeAsync()
{
  using(var releaser = await _lock.LockAsync()) 
  {
    // この中でawaitを使用することが出来ます。
    await this.FooAsync(); 
  }
}

この方法の利点

任意の操作をatomicにする事ができるため、常にツリー構造に一貫性を保つことができます。
更新スレッドが複数ある場合でも正しくロックしている限りは一貫性を保つこと出来ます。

この方法の欠点

AsyncLockはSemaphoeSlimと同じで再入できるように作られていません。
上記のコード例で言うと、FooAsyncメソッド内でLockAsyncを呼び出すとデッドロックします。
ロックするかどうかの引数を持たせたり、特定のメソッドでしかロックしないように気を付ける等、あまりスマートではない工夫が必要です。

解決案2 ツリーを2本用意する

更新用ツリーと読み取り用ツリーの2本を用意します。
foreachで読み取る側はスナップショットのツリーを参照します。
ツリーの更新は更新用ツリーに対して行います。
更新が終わったら更新用ツリーをまるごとcloneし、コピーしたものと読み取り用ツリーをInterlocked.Exchangeメソッドで入れ替えます。

この方法の利点

読み取り用ツリー構造に一貫性を保つことができます。
ロックが不要になるためデッドロックの心配を無くすことができます。

この方法の欠点

ツリーに大量のノードがある場合はその分大量のメモリを消費し、clone操作がCPUへの負担となります。
また更新スレッドが複数あって同時に更新が行われ、それらの更新が全て完了しても更新用ツリーが一貫性を保っていない状態のままになった場合、それをコピーした読み取り用ツリーも一貫性を保っていないものになります。

補足 ツリーに一貫性を保たないとどうなるか

例えばツリーを読み取っている最中に、ノードの付け替え操作が非同期に行われると、読み取り側にとって当該ノードが突然消失したように見えたり、同じノードが2回現れたりします。
RDBにおけるPhantom Read現象と似たようなものと思って下さい。

別の例として新しいN個のノードをそれぞれ別の親ノードの子として同時に追加したい場合です。
ロックフリーコレクションではこの操作をatomicに行う事はできません。
読み取り側にとって”同時に追加された”ようには見えなくなります。

このような事態を想定したゲームロジックになっていないと、再現性の無い難解なバグや見た目を損なう原因となり、デバッグが非常に難しくなります。

4
  • ロックが1個だけだと同時に1スレッドしか動かないので並列処理にならないのでは
    – pgrho
    Commented 2015年1月30日 14:28
  • async/awaitを使っているというだけで、ツリー操作そのものには並列性を求めておられるようには思いませんでしたので、文字通りに1番単純な方法を紹介しました。パフォーマンスが気になるなら、紹介記事の元ネタである”Parallel Programming with .NET”の”Building Async Coordination Primitives”シリーズにはReaderWriterLockのasync版もあります。また、ツリーの状態が必ずしも一貫性の取れた状態でなくてもよい要件であれば、PITAさんの仰るロックフリーな手法も有用だと思います。ただしノードの付け替えをしたい場合に、その操作をatomicに行う事ができませんし、Phantom Read現象が起こります。このあたりはRDBとNOSQLとの対比を連想していただければ分かりやすいかと思います。
    – enigma
    Commented 2015年1月30日 19:26
  • おっしゃるとおり(async/awaitを使った時はlockステートメントが使えないので)SemaphoSlimを使ってコレクション全体をちまちま自力で排他制御するのが一番オーソドックスだと思います。ただしこの方法はそこら中にWait/Releaseが点在することになりコードがとても醜くなるのが欠点です。汎用的なスレッドセーフなコレクションは言うほど簡単な話ではなく、またロックフリーな不変なコレクションは最善に近いと思いますが無条件に使えるものでもない。ようするに2015年現在でもこの辺の非同期処理をどう記述すべきかはオープンな問題です。
    – プリン
    Commented 2015年2月1日 0:22
  • 要件に依るところが大きいので、なかなかベストプラクティスとして唯一つの解決策を提案するのは難しい問題だと思います。伝わりづらい箇所やコメントを踏まえた上で回答を編集しました。
    – enigma
    Commented 2015年2月2日 2:22
1

私ならこんな感じですかね

  • 更新するスレッドを1つに制限する
  • 描画用のツリーと作成中のツリーを分け、変更はしない
  • 複数の更新担当オブジェクトがいる場合、各オブジェクトの更新可能範囲を制限する。役割分担のためにデータを論理的なツリーにして描画用のツリーは各論理ノードのものを組み合わせる

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。