.NET 4以来、System.Collections.Concurrent以下に、 Concurrentなコレクションがいくつか追加されました。

Concurrent、英単語の意味としては「同時に起こる」という意味の形容詞。 プログラミングにおいては、「複数のプログラムやスレッドから同時にアクセスされる」という意味で使われ、 「並行」とか「同時実行」とか訳されます。 たいてい、「Concurrentなんとか」みたいな名前のものは「同時実行があっても問題が起きない」という意味になります。

ただし、「問題を起こさない」って言ってもいろいろな意味があって、それぞれのコレクションの性質をちゃんとわかっておかないと困ったりします。 (.NET のSystem.Collections.Concurrentに限らず、たいていのプログラミング言語のたいていのライブラリで、Concurrentと名の付くものは同様の注意が必要です。)

ということで、今日はConcurrentDictionaryのGetOrAddメソッドを例にとって挙動をちょっと説明。

GetOrAdd

こいつ: GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)

名前通り、キーに応じた値がすでにあればその値を返し、なければ valueFactory を呼んで、新しい値を作って辞書に登録しつつ、その作った値を返します。

話を簡単にするために、まずちょっと、同時実行が必要ない状況で例を出しますが、以下のような挙動になります。

using System;
using System.Collections.Concurrent;

class Program
{
    static void Main(string[] args)
    {
        const int theKey = 1;
        var d = new ConcurrentDictionary<int, string>();

        // まず、GetOrAdd の同時実行が起こらない場合を見てみる
        // 普通の逐次実行なので、同時実行にはならない
        for (int i = 0; i < 4; i++)
        {
            var item = d.GetOrAdd(theKey, key =>
            {
                // インスタンス新規作成
                // 単一のキーでアクセスしているので1回限り
                Console.WriteLine($"Add: {i}");
                return i.ToString();
            });

            // 同じインスタンスが返ってきているか確認
            Console.WriteLine($"Get: {item}");
        }
    }
}

Add: 0
Get: 0
Get: 0
Get: 0
Get: 0

この例では、同じキーで何度も GetOrAdd を呼んでいます。 値の生成($"Add: {i}"と表示される部分)は最初の1回でしか通りません。

並列動作

このforループを並列化することを考えます。

ConcurrentDictionary の必要性

単に同時実行で問題を起こさないようにするなら、わざわざConcurrentDictionaryなんていう新しいクラスを作らなくても、 lockステートメントを掛ければ済む話です。

Concurrentを名乗らない普通のDictionaryを使って、 自前でlockを掛けるのであれば、例えば以下のように書けばいいでしょう。

static class DictionaryExtensions
{
    public static TValue GetOrAdd<TKey, TValue>(this IDictionary<TKey, TValue> d, TKey key, Func<TKey, TValue> valueFactory)
    {
        lock (d)
        {
            TValue value;
            if (!d.TryGetValue(key, out value))
            {
                value = valueFactory(key);
                d[key] = value;
            }
            return value;
        }
    }
}

このコードの何が嫌かというと、lock範囲が広すぎること。

• Getにもlockが掛かる。新規追加(Add)の頻度が低い時に完全に無駄
• Add のときに、valueFactory呼び出し中にもずっとlockが掛かっていて、valueFactoryの中身次第ではlock時間が長くなりすぎる

lockは、意外と重たい処理です。可能な限り避けて、可能な限り短くする必要があります。

ConcurrentDictionaryは、lock範囲を極力小さくすることで、パフォーマンス向上を図っているクラスです。

ConcurrentDictionaryの癖

ただし、ConcurrentDictionaryのGetOrAddには少々癖があります。

ドキュメントをちゃんと読むと書いてあるんですが、

• valueFactoryは複数回呼ばれる可能性があります
• 返す値・辞書内に格納する値は必ず1つであることが保証されています

という挙動。

その結果、最初にあげた例で、forループをParallel.Forに変えて並列化すると、以下のような挙動をします。

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        const int theKey = 1;
        var d = new ConcurrentDictionary<int, string>();

        // 並列動作
        // 並列なので、ループの中身が複数のスレッドで同時に動くことがある
        Parallel.For(0, 4, i =>
        {
            var item = d.GetOrAdd(theKey, key =>
            {
                // 同時に来られると、ここは複数回動く可能性がある
                Console.WriteLine($"Add: {i}");
                return i.ToString();
            });

            // Add が複数回動いても、Get で帰ってくる値は必ず単一の保証あり
            Console.WriteLine($"Get: {item}");
        });
    }
}

実行する環境によって/実行するたびに結果は異なりますが、一例としては以下のような実行結果になります。

Add: 0
Add: 3
Get: 0
Add: 1
Get: 0
Add: 2
Get: 0
Get: 0

(この環境では)Addは4回動いています。 しかし、戻り値として返っているのはそのうち1つだけで、Getのところに表示されている値は全部同じです。

癖の回避: Lazyとの組み合わせ

lockを減らすためとはいえ、ちょっと癖のある挙動です。この癖を回避したければ一工夫要ります。 その工夫として、別途、Lazyクラス(System名前空間)と組み合わせる方法があります。

以下のような書き方をします。

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
        const int theKey = 1;
        var d = new ConcurrentDictionary<int, Lazy<string>>(); // 値を Lazy<string> に変える

        // 並列動作
        // 並列なので、ループの中身が複数のスレッドで同時に動くことがある
        Parallel.For(0, 4, i =>
        {
            var lazy = d.GetOrAdd(theKey, key => new Lazy<string>(() =>
            {
                // 複数個の Lazy インスタンスが作られることはあるけども、
                // Lazy が作られただけでは valueFactory は呼ばれない
                Console.WriteLine($"Add: {i}");
                return i.ToString();
            }));

            // lazy 自体は単一のインスタンスが返る保証あり

            // この時点で初めて Add: の行が呼ばれる
            // Lazy のデフォルトの挙動では、valueFactory が呼ばれるのは1回限りの保証あり
            var item = lazy.Value;

            Console.WriteLine($"Get: {item}");
        });
    }
}

結果は以下のようになります。

Add: 0
Get: 0
Get: 0
Get: 0
Get: 0

値は0である保証はなくて、Add: 1とかAdd: 2が表示されることもありますが、少なくとも

• Add:の行が表示されるのは1回限り
• Add:の行とGet:の行で表示されている値は同じ

という保証はされています。

これで、GetOrAdd全体をlockするよりはだいぶパフォーマンスのよいコードになります。 特に、Addがほとんどなく、Get頻度が高い場合にはかなり顕著な差になるでしょう。