

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

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

  1. [`SemaphoreSlim`](https://msdn.microsoft.com/en-us/library/system.threading.semaphoreslim%28v=vs.110%29.aspx) で排他制御を行う
  2. コレクションを必ず `ToArray()` でコピーしてから使う
  3. 追加および削除を1つのスレッドで行うようにロジックを変更する

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

* * *

回答を考慮して追加

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

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

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


CC BY-SA 3.0
2015-01-30T10:26:21.970
5622
2022-06-09T08:12:47.837
2015-02-01T09:53:23.283
5005
5005
question
c# game-development
async/awaitを使った非同期プログラミングにおいてコレクションの変更を行う際のベストプラクティスは


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

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


CC BY-SA 3.0
2015-01-30T10:56:33.003
5624
2015-01-30T10:56:33.003
5750
5622
answer


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

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

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

[非同期：awaitを含むコードをロックするには？（AsyncLock編）](https://atmarkit.itmedia.co.jp/ait/articles/1411/18/news135.html)  
[Building Async Coordination Primitives, Part 6:
AsyncLock](https://web.archive.org/web/20160713103709/http://blogs.msdn.com:80/b/pfxteam/archive/2012/02/12/10266988.aspx)

ReaderWriterLockを使いたい場合はこちらを選択します。  
[Building Async Coordination Primitives, Part 7:
AsyncReaderWriterLock](https://web.archive.org/web/20160522234750/http://blogs.msdn.com:80/b/pfxteam/archive/2012/02/12/10267069.aspx)

### AsyncLockの使用例

[code]

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

### この方法の利点

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

### この方法の欠点

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

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

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

### この方法の利点

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

### この方法の欠点

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

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

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

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

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


CC BY-SA 4.0
2015-01-30T11:56:48.430
5626
2022-06-09T08:12:47.837
2022-06-09T08:12:47.837
3060
3277
5622
answer


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

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

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

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


CC BY-SA 3.0
2015-01-30T13:34:32.087
5633
2015-01-30T13:34:32.087
2207
5622
answer


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

  * System.Threading.ReaderWriterLockSlim

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

個人的には、

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

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


CC BY-SA 3.0
2015-01-31T02:05:52.767
5648
2015-01-31T09:56:22.677
2015-01-31T09:56:22.677
7287
7287
5622
answer