1. 「ロックなし」パターン(Lock-Free / Wait-Free)
あなたは既に Concurrent コレクションがスレッドセーフであることを知っています。でも、どうやってコードに lock をべた付けせずにそれを実現しているのでしょう?答えは高度なアルゴリズム、つまり lock-free(ロックなし) と wait-free(待機なし) にあります。
lock-free と wait-free アルゴリズムの概念の簡単な説明
Lock-Free(ロックなし)
要点: 少なくとも 1つの スレッドは常に前進できることを保証します。たとえ他のスレッドが遅延や中断に遭ってもです。
lock との違い: lock を使うと競合するスレッドはロックが解放されるのを待ちます。lock-free アルゴリズムではスレッドは古典的な意味でお互いを待たず、競合が起きたら単にリトライします。
例: レジの列で:lock の場合は並んで待つ。lock-free では近づいて空いてなければ少し時間をおいて再試行する — 共有の列で「待つ」わけではありません。
Wait-Free(待機なし)
要点: より強い保証で、各スレッドは 有限回の自分自身のステップ で必ず前進します。他のスレッドに関係なく誰も無限にループし続けません。
違い: lock-free では競合によりあるスレッドが無限にリトライする可能性があるが、wait-free ではそれが起きません。
実務: wait-free を実装するのはかなり難しいので、現実には lock-free やハイブリッドなアプローチの方が一般的です。
2. Concurrent コレクションはどうやってスレッドセーフを達成するか
lock-free アルゴリズムの基本ブロックは CPU レベルの 原子操作 です。.NET ではこれらに System.Threading.Interlocked クラスを通じてアクセスします。
Interlocked 操作
プリミティブ型(int, long)に対する高速な原子操作:例えば Interlocked.Increment, Interlocked.Decrement, Interlocked.CompareExchange。
例:Interlocked.Increment(ref value) — 原子的なインクリメント; Interlocked.CompareExchange(ref location, value, comparand) — 原子的に比較して一致すれば更新。
CAS (Compare-And-Swap) — 比較して交換
CAS 操作は .NET では Interlocked.CompareExchange として実装されています。一般的なロジックは次の通り:
- 変数の現在値を読む。
- 読んだ値に基づいて新しい値を計算する。
- 変数がまだ元の値と等しければそれを書き込もうとする。違っていれば再試行する。
例:Interlocked を使ったシンプルな lock-free カウンター
using System.Threading;
using System.Threading.Tasks;
class CounterExample
{
static int regularCounter = 0;
static int interlockedCounter = 0;
static void IncrementRegular(int iterations)
{
for (int i = 0; i < iterations; i++)
{
regularCounter++; // スレッドセーフではない!
}
}
static void IncrementInterlocked(int iterations)
{
for (int i = 0; i < iterations; i++)
{
Interlocked.Increment(ref interlockedCounter); // 原子的!
}
}
}
//Main で:
Task t1 = Task.Run(() => IncrementRegular(500_000));
Task t2 = Task.Run(() => IncrementRegular(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"普通のカウンター: {regularCounter}"); // ほとんどの場合 1_000_000 より小さい
regularCounter = 0; // 次のテストのためにリセット
t1 = Task.Run(() => IncrementInterlocked(500_000));
t2 = Task.Run(() => IncrementInterlocked(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Interlocked カウンター: {interlockedCounter}"); // 正確に 1_000_000 になる
メソッド Interlocked.Increment はインクリメントの原子性を保証します:複数スレッドの同時アクセスでもデータは失われません。
3. なぜこれがスケーラビリティとパフォーマンスで重要か
オーバーヘッドを減らす: 従来のロック(lock)はコンテキストスイッチやカーネル側の待ちを引き起こす可能性があります。Lock-free はこれらのコストを最小化します。
デッドロックが発生しにくい: スレッド同士で待ち合うことがないため deadlock を作りにくいです。
より良いスケーラビリティ: マルチコア環境ではスレッド同士の干渉が減り、単一の共有ロックによる「ボトルネック」が無くなります。
応答性の向上: 長時間の待機で誰かが「ハング」することが少なくなります。
ConcurrentQueue<T> の内部を非常に簡単に見る
単純化すると:キューはリンクされたセグメントで構成されます。Enqueue 時はスレッドが原子的に「尾」を CompareExchange で進め、TryDequeue では「頭」を変わっていなければ原子的に進めます。実際の実装は ABA 問題や GC を考慮してもっと複雑ですが、要点は「重い」ロックの代わりに原子操作を使っていることです。
4. Concurrent コレクションのパフォーマンス
lock を使った普通のコレクションとのパフォーマンス比較
低い競合状態では差は小さく、単純な lock を使った普通のコレクションが同等の場合もあります。しかし高い競合では Concurrent コレクションが一般に大幅に高速です。共有ロックによる待機がないためです。
例:比較(アイデア、実行はせず)
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Diagnostics; // Stopwatch 用
using System.Threading.Tasks;
class PerformanceTest
{
static List<int> regularList = new List<int>();
static ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
static object lockObject = new object();
const int Iterations = 1_000_000;
const int NumTasks = 4; // 並列タスク数
public static void RunTests()
{
Console.WriteLine("パフォーマンステスト(追加):");
// 普通の List と lock のテスト
regularList.Clear();
Stopwatch sw = Stopwatch.StartNew();
Parallel.For(0, NumTasks, (i) =>
{
for (int j = 0; j < Iterations / NumTasks; j++)
{
lock (lockObject)
{
regularList.Add(j);
}
}
});
sw.Stop();
Console.WriteLine($"List + lock: {sw.ElapsedMilliseconds} ms. Count: {regularList.Count}");
// ConcurrentQueue のテスト
concurrentQueue.Clear();
sw = Stopwatch.StartNew();
Parallel.For(0, NumTasks, (i) =>
{
for (int j = 0; j < Iterations / NumTasks; j++)
{
concurrentQueue.Enqueue(j);
}
});
sw.Stop();
Console.WriteLine($"ConcurrentQueue: {sw.ElapsedMilliseconds} ms. Count: {concurrentQueue.Count}");
// NumTasks > 1 のとき ConcurrentQueue の方がかなり速くなることを期待できます
}
}
結論: コレクションの周りに lock を見かけたら、それはしばしば Concurrent の代替に切り替えるサインです。
6. 役立つ細かい注意点
contention がパフォーマンスに与える影響
Contention: 多くのスレッドが同時に同一リソースにアクセスする状態。競合が高いほど待ちが増え、パフォーマンスは悪化します。
Concurrent コレクションは競合を減らすよう設計されています:例えば ConcurrentBag<T> はスレッドローカルなストレージを使い、ConcurrentDictionary<TKey, TValue> はストライプロック(segmented locking)を使います。
パフォーマンスの鍵は contention の削減: 可能ならデータをスレッドごとに分けるか、複数のコレクションを使ってください。
特定のシナリオに合ったコレクションの選択
| コレクション | 順序 | 使うとき | 使わない方がいいとき |
|---|---|---|---|
|
FIFO (First-In, First-Out) | タスクキュー、ロギング、イベントの非同期処理、Producer-Consumer パターン。 | 順序が重要でない、LIFO が必要、サイズ制限とブロックが欲しい場合。 |
|
LIFO (Last-In, First-Out) | 操作履歴(Undo/Redo)、グラフ探索(DFS)、「最後に追加されたもの」を優先するオブジェクトプール。 | FIFO が重要、順序の安定性が必要な場合。 |
|
順序は保証されない | オブジェクトプール、プロデューサとコンシューマがよく同じスレッドで動く場合、TPL シナリオでローカリティが重要な場合。 | 要素の順序が重要な場合。 |
|
なし | キャッシュ、ユーザーセッション、統計集計、並列集約。 | 辞書が不要な場合。 |
| BlockingCollection<T> (基底は ConcurrentQueue など) | FIFO(またはベースコレクション次第) | ブロッキング操作やサイズ制限、便利な終了処理が必要な Producer-Consumer。 | ブロッキング操作やサイズ制限が不要な場合。 |
7. 最適化のアドバイス
「ホット」な場所で頻繁に ToArray() を使わない
ToArray() はコレクション全体の新しいコピーを作るので、メモリと時間のコストが高いです。スナップショットが必要なときだけ、そしてできるだけ少ない頻度で使ってください。要素数が必要な場合は Count を使います(呼び出し時点のスナップショットであることを忘れずに)。
Concurrent コレクションの列挙には注意
イテレータは並列の変更に対して安定性を保証しません:要素を見落としたり一貫性のないビューを得たりする可能性があります。安定したビューが欲しいなら先に ToArray() でスナップショットを取ってからイテレートしてください。
// 悪い例: 変更中に要素を見落としたり変更を見てしまう可能性がある
foreach (var item in myConcurrentQueue) { /* ... */ }
// 良い例: 固定スナップショットでイテレーション
var snapshot = myConcurrentQueue.ToArray();
foreach (var item in snapshot) { /* ... */ }
コレクションを通る「トラフィック」を最小化する
タスクやデータをまとめて処理しましょう:Add / Take の呼び出し回数が少なければ contention も減ります。例えば 1000 回の個別メッセージの代わりに 1000 件まとめた「パケット」を送るなど。
競合の発生源を計測する
性能劣化が見られるなら、どこで最も contention が発生しているかを測定してください。設計を変えてスレッドがローカルデータや別個のコレクションで動くようにできるかもしれません。
GO TO FULL VERSION