リストを並列処理で追加するときのパフォーマンス比較

# はじめに

並列処理は複雑になりがちで、大抵の場合難しいです。そのため C# / .net では、標準ライブラリに並列処理の助けとなる型が用意されています。

今回はこれらのパフォーマンスの違いを検証してみます。

- [`System.Threading.Lock`](https://learn.microsoft.com/ja-jp/dotnet/api/system.threading.lock?view=net-9.0) クラス: 異なるスレッド間のコード領域で相互除外を実現するためのメカニズムを提供します。`lock(obj)` の構文で使用します。
- 参考: [【.NET 9.0】System.Threading.Lock のパフォーマンス](https://qiita.com/abetakahiro123/items/5bd007e490153edcd667)
- [`System.Collections.Concurrent.ConcurrentBag<T>`](https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.concurrent.concurrentbag-1?view=net-9.0): スレッド セーフで順序付けられていないオブジェクトのコレクションを表します。
- [`System.Collections.Concurrent .BlockingCollection<T>`](https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.concurrent.blockingcollection-1?view=net-9.0): スレッド セーフなコレクションのブロック機能と境界機能を提供します。

```cs
var handle = new Lock();
lock (handle)
{
    // ここに処理を書く
}

var bag = new ConcurrentBag<int>();
Parallel.For(0, 10, n =>
{
    bag.Add(n); // スレッドセーフ
});

var collection = new BlockingCollection<int>();
Parallel.For(0, 10, n =>
{
    collection.Add(n); // スレッドセーフ
});
```

## サンプルコード

<details>
<summary>テストコード</summary>

```cs
using System.Collections.Concurrent;

public class __ParallelListTest
{
    static void HowToUse()
    {
        var handle = new Lock();
        lock (handle)
        {
            // ここに処理を書く
        }

        var bag = new ConcurrentBag<int>();
        Parallel.For(0, 10, n =>
        {
            bag.Add(n); // スレッドセーフ
        });

        var collection = new BlockingCollection<int>();
        Parallel.For(0, 10, n =>
        {
            collection.Add(n); // スレッドセーフ
        });
    }

    static void AddSingleThread(Performance p)
    {
        p.AddTest("ListUnlocked", () =>
        {
            var list = new List<int>();
            for (int n = 0; n < 100000; n++)
            {
                list.Add(n);
            }
        });

        p.AddTest("ListLocked", () =>
        {
            var handle = new Lock();
            var list = new List<int>();
            for (int n = 0; n < 100000; n++)
            {
                lock (handle)
                {
                    list.Add(n);
                }
            }
        });

        p.AddTest("ConcurrentBag", () =>
        {
            var list = new ConcurrentBag<int>();
            for (int n = 0; n < 100000; n++)
            {
                list.Add(n);
            }
        });

        p.AddTest("BlockingCollection", () =>
        {
            var list = new BlockingCollection<int>();
            for (int n = 0; n < 100000; n++)
            {
                list.Add(n);
            }
        });
    }

    static void AddParallel(Performance p)
    {
        // 複数のスレッドから同時に操作すると例外になる
        // p.AddTest("ListUnlocked", () =>
        // {
        //     var list = new List<int>();
        //     Parallel.For(0, 100000, n =>
        //     {
        //         list.Add(n);
        //     });
        // });

        p.AddTest("ListLocked", () =>
        {
            var handle = new Lock();
            var list = new List<int>();
            Parallel.For(0, 100000, n =>
            {
                lock (handle)
                {
                    list.Add(n);
                }
            });
        });

        p.AddTest("ConcurrentBag", () =>
        {
            var list = new ConcurrentBag<int>();
            Parallel.For(0, 100000, n =>
            {
                list.Add(n);
            });
        });

        p.AddTest("BlockingCollection", () =>
        {
            var list = new BlockingCollection<int>();
            Parallel.For(0, 100000, n =>
            {
                list.Add(n);
            });
        });
    }

    static void RandomAccessParallel(Performance p)
    {
        p.AddTest("Array", () =>
        {
            var array = new int[100000];
            Parallel.For(0, 100000, n =>
            {
                array[n] = n;
            });
        });

        p.AddTest("Dictionary", () =>
        {
            var dic = new Dictionary<int, int>(100000);
            for (var n = 0; n < 100000; n++)
            {
                dic[n] = 0;
            }

            Parallel.For(0, 100000, n =>
            {
                dic[n] = n;
            });
        });

        p.AddTest("ListLocked", () =>
        {
            var handle = new Lock();
            var list = new List<int>(100000);
            Parallel.For(0, 100000, n =>
            {
                lock (handle)
                {
                    list.Add(n);
                }
            });
        });

        p.AddTest("ConcurrentBag", () =>
        {
            var list = new ConcurrentBag<int>();
            Parallel.For(0, 100000, n =>
            {
                list.Add(n);
            });
        });

        p.AddTest("BlockingCollection", () =>
        {
            var list = new BlockingCollection<int>(100000);
            Parallel.For(0, 100000, n =>
            {
                list.Add(n);
            });
        });
    }
}
```

</details>

## パフォーマンス

### シングルスレッドでリストに追加する場合

```cs
var list = new List<int>();
for (int n = 0; n < 100000; n++)
{
    list.Add(n);
}
```

|Test|Score|%|CG0|
|---|---:|---:|---:|
|AddSingleThread (4)||||
|ListUnlocked|470|100.0%|134|
|ListLocked|102|21.7%|29|
|ConcurrentBag|93|19.8%|24|
|BlockingCollection|14|3.0%|3|

実行環境: Windows11 x64 .NET Runtime 9.0.0  
**Score** は高いほどパフォーマンスがよいです。  
**GC0** はガベージコレクション回数を表します（少ないほどパフォーマンスがよい）。

- 同期処理しない場合との参考とした比較です
- 同期処理するとパフォーマンスが下がるため、同期処理しないで済む場合はなるべく避けたほうが良さそうです

### 並列処理でリストに追加する場合

```cs
var handle = new Lock();
var list = new List<int>();
Parallel.For(0, 100000, n =>
{
    lock (handle)
    {
        list.Add(n);
    }
});
```

|Test|Score|%|CG0|
|---|---:|---:|---:|
|AddParallel (3)||||
|ListLocked|6|100.0%|1|
|**ConcurrentBag**|163|**2,716.7%**|23|
|BlockingCollection|6|100.0%|1|

- 単純な並列処理でのリストの追加をする場合、`ConcurrentBag` が非常に優れています
- 特に理由がないなら `ConcurrentBag` を使用するのが良さげです

### 配列にランダムアクセスする場合

```cs
var array = new int[100000];
Parallel.For(0, 100000, n =>
{
    array[n] = n;
});
```

|Test|Score|%|CG0|
|---|---:|---:|---:|
|RandomAccessParallel (5)||||
|Array|435|100.0%|54|
|Dictionary|108|24.8%|36|
|ListLocked|4|0.9%|0|
|ConcurrentBag|165|37.9%|23|
|BlockingCollection|6|1.4%|1|

- この例は同期処理を省略できるパターンです
- `lock` を使用した同期処理と比較して 100 倍のパフォーマンスの差があります
- `Dictionary` に事前にキーを割り当てた状態（並列処理時にキーの並びが変更されない）なら並列処理中でも同期処理を省略できそうな気がしますが、`ConcurrentBag` を使用するほうがパフォーマンスが出そうです

## おわりに

並列処理でリストが必要になったら [`System.Collections.Concurrent.ConcurrentBag<T>`](https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.concurrent.concurrentbag-1?view=net-9.0) を使うのが良さそうです。

[標準ライブラリには他にもいくつかコレクションが用意されている](https://learn.microsoft.com/ja-jp/dotnet/api/system.collections.concurrent?view=net-8.0)ようです。