[アーティクル]
03/15/2017

March 2017

Volume 32 Number 3

.NET Framework - 不変コレクション

Hadi Brais | March 2017

副作用があると、コードの分かりやすさや正確性に悪影響があります。グローバル変数や静的変数を変更するメソッドには副作用があり、一部のパラメーターを変更するメソッドも副作用を伴います。コードを理解する場合は、呼び出されるメソッドのうち、副作用を伴うすべてのメソッドのコードを確認しなければなりません。複数のスレッドを扱う場合、副作用を伴うメソッドではスレッド同期を適切に実行する必要があります。

では、副作用を伴わないメソッドを作成するとしたらどうでしょう。そのコードはどのようなものになり、どのように実行されるのでしょう。その答えは、副作用が発生しないようにインスタンスを不変にすることだと分かります。

通常、型のインスタンスが不変になるように作成すると、そインスタンスの値は決して変化しないことになります。不変性は、ソフトウェアエンジニアリングの多くの要素と同じく、設計上の選択肢の 1 つです。実際には使用しなければならないというものではありませんが、シナリオによっては、コードパフォーマンスや分かりやすさの点で、不変性のメリットを得られる可能性があります。事実、不変性は役に立つ場面が多く、関数型プログラミングパラダイムでは成功につながる基本原則の 1 つになっています。F# は関数型言語なので、特に明示的に指定しない限り、インスタンスはすべて不変になります。一方、C# はオブジェクト指向を優先する言語なので、明示的に指定しなければ、すべてのインスタンスが可変になります。今回は、C# で不変性を利用する方法を示します。その前に、本稿で扱う「不変性」を定義します。

不変性の定義

技術的には、不変性には多くの種類があります。型の状態またはそのインスタンスの状態に対する変更を少しでも制限している型はすべて、ある意味では不変であると考えられます。System.String 型は、文字列のサイズ、文字、およびその順序が変化しないという意味では不変型です。すべてのデリゲート型の親である System.MulticastDelegate 型も System.String と同じ意味で不変です。どちらも基になるデータ構造に配列を使用し、配列をコピーすることで要求された変更に対応します。この対応方法は、要求される変更がどれほど小さなものであっても変わりません。不変性の種類の詳細については、bit.ly/2kGVx4Z (英語) を参照してください。

System.Collections.ObjectModel.ReadOnlyCollection<T> は不変ではありませんが、特定の可変 IList<T> オブジェクト用に不変インターフェイスを実装します。このインターフェイスでは、利用側がコレクション内の項目数やその相対順序を変更することはできません。ただし、個別の項目の不変性についてはまた別の話になります。各項目の不変性は、T の全体的な型階層によって変わります。もちろん、基になるリストへの参照を持つコードは、制限なくリストを変更できます。

今回説明する不変コレクションは、また別の種類の不変性を提供します。不変コレクションの必要性に対する関心を高めるために、次の例を考えてみます。

標準のテキストエディターには、ユーザーが記述したテキストを分析したり、処理したりする機能やツールがいくつか備わっています。たとえば、スペルチェックやコード分析などです。マルチコアコンピューターの普及により、ユーザーがテキストを入力している最中でも、こうしたツールをバックグラウンドで実行できるようになりました。ただし、注意しないと、スレッドセーフの問題が発生することがあります。バックグラウンドアナライザーは、ユーザーがテキストを変更すると同時に、そのテキストが格納されるバッファーを読み取ります。ここで、バッファーの代わりに、バックグラウンドプロセスでテキストのスナップショットを論理的に取得するとします。

これを適切かつ効率的に実現するにはどうすればよいでしょう。 String のような型を使えば適切に問題を解決できますが、効率的ではありません。この方法では、ツールを実行しながら同時にテキストを変更できるものの、変更のたびにテキストの新しいコピーが作成されるため、大きなドキュメントでは低速になり、メモリが浪費される可能性があります。別の適切なソリューションとして、System.Text.StringBuilder などの可変型を使用する方法があります。しかし、これもまた非効率です。ツールでは、ロックをかけてテキストのコピーを作成する必要があり、コピーが終わるまでユーザーは変更を進められなくなります。ReadOnlyCollection<T> の使用もあまり役立ちません。基になるコレクションが可変で、共有されるためです。

別の種類の不変性が必要です。それも、コピーの必要がまったくない、またはほとんどコピーしない方法で、できるだけ多くのデータをスレッド間で共有しながら、高コストのスレッド同期メカニズムを使用しないで、安全に変更できる不変性です。不変コレクションは、まさにそのような種類の不変性を提供します。この不変性は永続性として知られています。不変コレクションは前述のシナリオに役立つだけではなく、今回紹介するマルチスレッドやシングルスレッドのシナリオでも有効です。

今回は、不変コレクションの設計、実装、およびパフォーマンスを詳しく説明していきます。それにより、不変コレクションを効率的に使用すること、さらには独自の不変コレクションや不変型を記述することさえ可能になるでしょう。不変コレクションは、.NET Standard 1.0 以降をサポートする任意の .NET プラットフォームで使用できます (つまり、すべての Windows プラットフォーム、Xamarin、および .NET Core で使用できます)。不変コレクションは比較的新しく、NuGet パッケージとして配布されます。そのため、不変コレクションが役立つフレームワーク API が多数存在するにもかかわらず、.NET Framework 自体では使用されていません。そのような API では、代わりに、あまり理想的ではない ReadOnlyCollection<T> を使うか、可変コレクションのコピーを使用します。今回はパッケージバージョン 1.3.0 を使用します。ソースコードは CoreFX の一部として入手できます。

安全ではないコードまたはリフレクションを使用すると、ほぼすべての不変性の保証が損なわれる可能性があるので注意が必要です。通常、型が不変になるように記述している場合、こうした手法を使うことで不変性の保証が妨げられる可能性があることを意識します。これは、今回説明する不変コレクションでも同じです。

不変コレクションの定義

不変コレクションの内部について説明する前に、不変コレクションを定義する必要があります。不変コレクションとは、コレクションの構造が常に保持され、なおかつ要素レベルでの割り当てを許可しないインスタンスのコレクションで、変更を実行する API を提供します。コレクションの構造とは、要素の数とその相対順序を指します (相対順序は、配列構造の場合はインデックスによって決まり、リンク構造の場合はリンクによって決まります)。

たとえば、ImmutableStack<T> に要素をプッシュすると、2 つの独立した不変スタックが返されます。1 つは新しい要素を含むスタック、もう 1 つは新しい要素を含まないスタックです。一方、変更可能な Stack<T> に要素をプッシュすると、そのスタックが事実上変更され、新しい要素が格納されたスタックが 1 つだけ返されます。不変コレクションも可変コレクションも要素自体については保証を提供しないことに注意してください。T が Int32 または String なら、要素も不変になります。ただし、T が StringBuilder のようなものであれば、要素の可変性は非常に高くなります。

不変オブジェクトを構築するには初期化しなければなりません。したがって、初期化中のオブジェクトは可変です。(プライベートメソッド以外から返されることによって) オブジェクトへの参照が発行されたら、残りの有効期間はずっと、そのオブジェクトは事実上不変になります。

不変コレクションは 2 つの目的を想定して設計されています。1 つは、できるだけ多くのメモリを再利用し、コピーを回避して、ガベージコレクターの負荷を減らすことです (このような実装は一般的に永続的と呼ばれます)。2 つ目の目的は、可変コレクションで提供されるのと同じ処理を、同等の時間内にサポートすることです。

不変スタック

可変 Stack<T> 型は配列を使用して実装します。ですが、配列は不変コレクションには適しません。現在のインスタンスを維持する方法が、配列全体をコピーし、その新しい配列に対して変更を実行するしか方法がないためです。こうすると、不変スタックは許容できないほど遅くなります。不変スタックを円滑に実装するにはリンクリストを使用します。各要素は、次の下位要素へのポインター (一番下の要素の場合は null ポインター) を含みます。不変スタックは先頭の要素へのポインターとして表されます。この方法では、スタックに変更を加えることなく、特定のスタックの要素をプッシュおよびポップすることができます。同時に、スタックのすべての要素が最終的なスタックと共有されます。このように設計がシンプルなため、不変スタックは最も簡単な不変コレクションになっています。可変スタックと不変スタックの違いは後ほどさらに詳しく説明します。

ここからは、不変スタックを作成して使用する方法を見ていきます。ImmutableStack<T> などの不変コレクションはすべて、System.Collections.Immutable 名前空間で定義されています。メモリを最大限に共有するため、不変コレクションではパブリックコンストラクターが用意されていません。不変コレクションのインスタンスを作成するには、不変コレクションに対応する静的型で定義したいずれかの CreateXxx<T> メソッドを使用する必要があります。不変スタックの場合、この型は ImmutableStack という名前です。この型は次のファクトリメソッドを提供します。

public static ImmutableStack<T> Create<T>();
public static ImmutableStack<T> Create<T>(T item);
public static ImmutableStack<T> Create<T>(params T[] items);
public static ImmutableStack<T> CreateRange<T>(IEnumerable<T> items);

これらのメソッドはすべて、コレクションに格納される項目の型を指定するジェネリック型パラメーター T を持ちます。最初のメソッドは空の不変スタックを作成します。このメソッドは、内部的にはシングルトン ImmutableStack<T>.Empty を返すだけです。2 番目のメソッドは、指定した項目をプッシュしたスタックを作成します。このメソッドは、ImmutableStack<T>.Empty.Push(item) に相当します。3 番目と 4 番目のメソッドは、指定した項目を順番にプッシュしたスタックを作成します。CreateRange<T> メソッドは次のように実装します。

var stack = ImmutableStack<T>.Empty;
foreach (var item in items)
{
  stack = stack.Push(item);
}
return stack;

すべての不変コレクション用のファクトリメソッドは、いずれも利便性のために用意されています。これらはすべて、内部的には空のコレクションから開始して、指定した項目をそのコレクションに追加していきます。項目は常に浅くコピーされます。

ここで、空のスタックから開始する次の一連の操作を考えてみます。

ImmutableStack<Int32> s1 = ImmutableStack<Int32>.Empty;
ImmutableStack<Int32> s2 = s1.Push(1);
ImmutableStack<Int32> s3 = s2.Push(2);
ImmutableStack<Int32> s4 = s3.Push(3);
ImmutableStack<Int32> s5 = s4.Push(4);
ImmutableStack<Int32> s6 = s4.Pop();
ImmutableStack<Int32> s7 = s6.Pop();

Push メソッドと Pop メソッドは、結果の不変スタックへの参照を返します。対照的に、可変 Stack<T> の Push メソッドと Pop メソッドは void と T をそれぞれ返します。この設計は、不変スタックを変更すると、スタックそのものが別のスタックになり、可変スタックを変更すると、実際にそのスタックに変更が加えられるという考え方を反映しています。同じ一連の操作を可変スタック上で実行すると、最終結果は異なったものになります (図 1 参照)。不変スタックが不変である理由は、ノードのポインターと値を変更する方法が存在しないためです。

図 1 可変スタックとは対照的に、不変スタックに変更を加えると別のスタックになる

空の不変スタックノードには T の既定値 (Int32 の場合、T は 0) が格納されます。また可変スタックは、配列のサイズを小さくしていくのではなく、ポップされた項目の値のみを既定値に設定します。配列の占有されていない部分はスラック領域と呼ばれます。

不変スタックの先頭の項目を取得するには、Peek メソッドを使用するか、Push の別のオーバーロードを使用します。Push は出力パラメーターを持ち、このパラメーターを使って項目を返します。

不変リスト

リストデータ構造はスタックよりも複雑になります。その主な原因はインデックス操作です。リスト構造では、指定したインデックスの項目に対する検索、追加、および削除が提供されます。可変 List<T> では配列が使用されるため、配列を使用するのは合理的ですが、前述のように汎用の不変リストでは非効率です。リンクリストを使用することも適切ではありません。指定したインデックスの項目に到達するまでに、多くの要素を走査しなければならない可能性があるためです。代わりに、平衡二分木を使用することで、すべての操作を優れたパフォーマンスで実行できるようになります。ほとんどの不変コレクションは平衡二分木を使用して実装されます。それ以外の不変コレクションではリンクリストを使用し、配列を使用するものは 1 つだけです。これは不変配列と呼ばれ、後ほど説明します。

ツリー内のすべてのノードには、リストの項目が 1 つ含まれます。つまり、すべてのノードがインデックスを持ちます。ImmutableList<T> 型は、ツリーに対する深さ優先の順序走査が、インデックス 0 の項目から最後の項目まで順番にリストを走査する場合と一致するように、ツリーを編成します。

次のプログラムを考えてみます。

ImmutableList<Int32> l1 = ImmutableList.Create<Int32>();
ImmutableList<Int32> l2 = l1.Add(1);
ImmutableList<Int32> l3 = l2.Add(2);
ImmutableList<Int32> l4 = l3.Add(3);
ImmutableList<Int32> l5 = l4.Replace(2, 4);

図 2 は、空の不変リストから開始する一連の操作の実行中に、基になるバイナリツリーに何が起きるかを示しています。各ボックスはツリーのノードを表します。文字 "E" が表示されたボックスは空のツリーシングルトンを表しています (何も指していない矢印は、E ボックスを指していると解釈します)。図の右側のボックスと矢印は不変ですが、左側のボックスと矢印は一時的に可変になっています。これは、frozen という内部のブール型フラグを使って指定します。このフラグには 2 つの目的があります。これについては後ほど説明します。

図 2 ツリーの内部状態 (左) と、変更完了後のパブリックアクセス可能な状態 (右側)

最初の項目をツリーに追加するには、両方のポインターが空のノードを指す新しいノードを作成します。新しく作成したノードはすべて、frozen フラグを false に設定して (一時的に可変にして) 開始します。この時点で、他には何も行う必要がなくなります。そのため、図の右側に示すように、frozen フラグを true に設定してツリーを不変にします。こうすることで、残りの有効期間中ずっと、ツリーが不変になります。

2 つ目の項目を追加するには、そのノードを最初のノードの右側の子にする必要があります。これは、ツリーがそのように編成されているためです。ただし、最初のノードは不変になっているため、そのポインターを変更することはできません。2 つ目の項目を追加する方法は 1 つだけで、2 つ目の項目のノードを作成するだけでなく、最初の項目についても別のノードを作成します。そのため、l2 と l3 は完全に異なるツリーを指しています。

同様に、3 つ目の項目は 2 番目のノードの右側の子にする必要があります。3 つ目の項目を追加するには、最初の項目と 2 つ目の項目の両方について新しいノードを作成するしかありません。ただし、今回は結果のツリーがアンバランスになります。ルートの左右のサブツリーに 2 以上の高さの差が付いた場合に、この状況が発生します。ツリーのバランスを確保するには、図 2 の右下に示すツリーのようにツリーを再編成する必要があります。これが可能なのは、ツリーがまだ可変であり、ImmutableList<T> 型以外のコードはツリーにアクセスすることも、変更を確認することもできないためです。ツリーへの参照が返される前に、各ノードの frozen フラグを true に設定してツリーを不変にします。これが frozen フラグの 1 つ目の目的です。

コードの最終行では Replace 関数を呼び出しています。こうすることで、指定された項目を検索し、別の項目に置き換えます。この場合、新しい項目を保持する新しいノードが作成され、同じツリーの他のノードが新しいツリーで再利用されます。

ツリーの編成方法により、リストに対する 1 回の操作は、追加、挿入、削除、検索など、操作を問わず時間量 O(log N) を持ちます。このとき、N は現在リスト内にある項目数を表します。一方、可変リスト List<T> に対する操作の時間量は、O(1) (操作をそのまま実行できる) か、O(N) (基になる配列をコピーする必要がある) のどちらかになります。

不変リストでは 1 回の操作はすばやく実行できます。ただし、大きな数字 M 回の操作を連続して実行する必要がある場合は、O(M log N) の時間が掛ります。この時間を短縮するには、frozen フラグを活用し、すべての変更を 1 つにまとめます。この最適化を実現するのが Builder です。

ImmutableList<T> を含むほとんどの不変コレクションでは Builder という型を定義します。この型では同一の基になるデータ構造が使用され、同じ API が提供されます。異なるのは、Builder では操作のたびに frozen フラグが設定されない点です。可変状態で作成されたノードが保持されるため、多くの操作をより効率的に実行できます。不変リストの Builder 型は ImmutableList<T>.Builder です。

Builder インスタンスを作成するには、不変コレクションインスタンスが必要です。空のコレクションで開始して ImmutableList.CreateBuilder<T> 静的メソッドを使用するか、特定の不変コレクションで ToBuilder インスタンスメソッドを使用します。後者の場合、約束どおり、既存のノードはすべて不変のままになります。新しいノードのみが可変になります。すべての操作を実行したら、ToImmutable インスタンスメソッドを呼び出すことですべてのノードの frozen フラグを true に設定できるため、効率的にコレクションを不変にすることができます。ImmutableList<T> では複数のインスタンスメソッドが提供されます。たとえば、AddRange と RemoveRange です。これらのメソッドは、IEnumerable<T> への参照を受け取り、内部で Builder を使用して、指定した項目に対する操作を実行します。

操作の中には、Builder によるメリットを得られないことで、必然的にコストが高くなるものもあります。Reverse インスタンスメソッドは、項目の順序を反転させるために、ツリー内のリーフノード以外のノードをすべてコピーする必要があります。Sort インスタンスメソッドは、すべての項目を配列にコピーし、配列を並べ替えて、並べ替えた配列から不変リストを作成することにより実装されます。

可変 List<T> は内部的には配列を使用します。配列の真中で項目を挿入または削除する場合、新しい配列を作成し、他の項目をすべてコピーすることが必要になります。また、断片化したアドレス空間では、非常に大規模な配列を割り当てることが不可能な場合もあります。可変 LinkedList<T> を使うことでこれらの問題がどちらも解決されます。ImmutableList<T> は両方の利点を提供しますが、他の操作の効率が低くなります。ImmutableList<T> は、List<T> と LinkedList<T> の両方に対応する不変コレクションです。StringBuilder は基本的には List<Char> です。

不変配列

ImmutableArray<T> 型は、ImmutableList<T> と同様、不変リストを実装しますが、その方法が異なります。ImmutableArray<T> は、型 T[ ] の配列を囲むシンラッパーにすぎません。ImmutableArray<T>が "シン" なのは、参照型フィールドを 1 つ格納する値型であるためです。配列自体はマネージヒープから割り当てられます。変更操作を実行するには、配列全体のコピーを作成し、コピー後の配列に対して操作を実行します。この点から見ると、ImmutableArray<T> は String を一般化したものと言えます。ImmutableArray<T> は文字だけではなく、任意の型の項目の文字列を表すことができるためです。

ImmutableArray<T> を使用すると、すべての変更操作で O(N) 時間必要になりますが、ImmutableList<T> を使えば O(log N) 時間で済みます。ただし、ImmutableArray<T> には優れている点が 3 つあります。第 1 に、インデックスを考慮した場合、ImmutableArray<T> を使うと項目に O(1) 時間でアクセスできますが、ImmutableList<T> を使用すると O(log N) 時間掛かります。第 2 に、どちらの実装も反復回数に正比例しますが、ImmutableArray<T> の場合はすべての項目が連続して格納されるため、キャッシュに適しています。ImmutableArray<T> を反復処理する場合、ImmutableList<T> を反復処理するよりも何倍も高速になる可能性があります。第 3 に、ImmutableArray<T> の方がメモリ消費量が少なくなります。これはポインターを使用しないためです。一般に、特定の状況でどちらを使用するかを決めるには、計測が必要になる場合があります。どちらの型も IImmutableList<T> インターフェイスを実装しています。コード全体でこのインターフェイスを使用することで、簡単に型どうしを切り替えることができます。

当然、一括操作を実行し、Builder オブジェクトをプールすることで、パフォーマンスを改善して、ガベージコレクション (GC) の負担を減らすことができます。一括操作メソッド XxxRange または ImmutableArray<T>.Builder を使用できます。ImmutableArray<T>.Builder は、List<T> と同じように実装されます。

標準設計の LINQ 演算子は IEnumerable<T> 参照で動作するため、値型 ImmutableArray<T> に LINQ 演算子を適用するにはボックス化が必要になります。不変コレクションの NuGet パッケージには、ボックス化を回避するために ImmutableArray<T> 専用に設計された LINQ 演算子の実装がいくつか含まれます。これは、System.Linq.ImmutableArrayExtensions に含まれています。

不変辞書

ImmutableDictionary<TKey, TValue> 型は、平衡二分木を使用して辞書を表します。ツリーの各ノードには、生成されるハッシュが同じになる項目をすべて保持する ImmutableList<KeyValuePair<TKey, TValue>> (これも平衡二分木です) が含まれます。一方、可変 Dictionary<TKey, TValue> は、キーと値のペアの配列を、衝突解決用のオープンアドレスと共に使用します。全体的には、ImmutableDictionary<TKey, TValue> の方が Dictionary<TKey, TValue> よりも何倍も遅くなり、メモリ消費量もずっと多くなります。辞書 Builder を使用しても少ししか役に立ちません。それは、基になる構造がツリーで構成されたツリーのままであるためです。ImmutableDictionary<TKey, TValue> を使用する場合は、厳密にパフォーマンスを計測し、許容可能かどうかを判断します。許容範囲を超えている場合は、独自にカスタマイズした不変辞書を記述する必要があるかもしれません。

不変コレクションのパフォーマンスとメモリ消費量

ところで、主に不変コレクションを使用するのが理想的な場合でも、許容できるパフォーマンスが得られないことがあります。そのため、不変コレクションの実装方法とそのパフォーマンスに対する影響を理解しておくことが重要です。

では、不変リストのパフォーマンスと可変リストのパフォーマンスを比較してみましょう。不変コレクションに対する一般的な操作の時間量は、bit.ly/2ko07HS (英語) で確認できます。このページではあまり詳しく説明されていないため、実際に使用してみることにします。可変リスト、不変リスト、および不変リスト Builder に対して、それぞれ 1,000 万個の 8 バイト整数を最後または先頭に追加するだけの 3 つのプログラムを作成しました。図 3 がその結果です (ここに示しているのは概算値です。時間は秒単位で、メモリはメガバイト単位です。JIT 最適化が有効になっています。可変リストの作成には既定のコンストラクターを使用しています)。

図 3 可変リスト、不変リスト、および不変配列で使用される時間とメモリ量

	可変	ImmutableList	ILBuilder	ImmutableArray	IABuilder
追加	0.2	12	8	非常に悪い	0.2
先頭に追加	非常に悪い	13.3	7.4	非常に悪い	非常に悪い
32 ビットサイズ	128	320	320	128	128
64 ビットサイズ	128	480	480	128	128

可変リストは配列ベースのため、可変リストへの追加は低コストです。配列はサイズが倍増することもありますが、その場合でも項目の追加は高速操作になります。一方、不変リストはツリーに基づくため、不変リストに項目を追加するコストははるかに大きくなります。Builder を使用した場合でさえ、まだ 40 倍近く遅いという結果です。これは大きな差です。ただし、これは厳密には公平な比較ではありません。公平に比較するなら、スレッド同期を使用して同じようにスナップショットセマンティクスを提供する可変リストと不変リストの間で比較することになるでしょう。しかし、それではシングルスレッドシナリオにおける不変コレクションの魅力は大幅に低下します。時間量が O(log N) しか掛からないとしても、見えない定数係数が非常に大きくなります。その理由については後ほど説明します。

先頭への追加操作の場合は、まったく話が異なります。このような操作を List<T> で完了するには何時間も掛かります。これは、短期間しか存在しない 1,000 万個の配列を割り当てて、コピーしなければならないためです。しかも、この配列はサイズが右肩上がりで大きくなります。不変リストとその Builder ではほとんど同じパフォーマンスが維持されます。

図 4 には、不変リストへの項目の追加中に Visual Studio 2015 の診断ツールを使用して生成した、マネージメモリの割り当てグラフの一部を示しています。グラフ上部のマーカーは、記録された任意の世代の GC を示します。グラフから、GC が頻繁に発生していることがわかります。約数 10 ミリ秒ごとに発生しています。PerfView を使用して、これらの小規模な GC すべての実行に費やされた合計時間を特定しました。Builder を使用しなければ、この GC の時間は約 4 秒です。これは、不変リストを直接使用した場合と、Builder を使用した場合の差です。この差が実際に GC に起因するものなのか、または偶然にすぎないかを判断するために、Builder を使用するプログラムでも PerfView を使用しました。その結果、この差は実際に GC が原因であることが判明しました。これは各 GC の動作を確認すれば簡単にわかります。不変リストは短期間しか存在しないオブジェクトと中期間存在するオブジェクトを多数作成します。一方、Builder は既存のオブジェクトのポインターを変更します。不変リストを直接使用する場合は GC が 100 回超トリガーされましたが、Builder と可変リストを使用する場合の GC のトリガー回数は 10 回未満でした。

図 4 不変リストに項目を追加する場合は GC の実行頻度が非常に高い

Builder は可変リストに比べて非常に低速です。これには相互に関連する 4 つの理由があります。第 1 に、Builder はキャッシュミスが多く発生するリンク構造を使用しています。第 2 に、項目を 2 個追加するとツリーがアンバランスになり、バランスを取り戻すためにローテーションが必要になります。第 3 に、項目を追加する際に (log N) ノードを走査する必要があります。第 4 に、項目が追加されるたびに、ホスティングノード用に個別のメモリ割り当てがトリガーされます。

これは、GC が問題の部分であるという意味ではありません。それどころか、実際は自動メモリ管理によって、大幅に簡単に不変コレクションを記述および使用できるようになります。GC により、まったく使用されていないすべての不変オブジェクトが自動的にクリーンアップされます。

ここで、不変スタックと可変スタックも比較してみましょう。このように比較することで、リンクデータ構造を使用したことから生じる、オブジェクトの割り当ておよびそれに伴うキャッシュミス (これは、後ほど発生する可能性のある全体のキャッシュミスからすればごく一部にすぎません) のコストを定量化できます。不変スタックは GC に適合しています。最終的なスタックに含まれるオブジェクトしか割り当てないためです。不変スタックは非常に効率が高いため Builder さえありません。可変スタックに対して 1,000 万個の 8 バイト整数をプッシュすると約 0.17 秒掛かります。一方、同じ整数を不変スタックにプッシュした場合は約 1 秒です。6 倍近く遅くなりますが、これは悪いことではありません。大規模な不変スタックまたは任意のリンク構造に対して反復処理を実行すると、類似の可変コレクションに対して反復処理を実行する場合に比べて、何倍も遅くなることがあります。その主な原因はキャッシュミスとページフォールトです (また、共有のために NUMA アーキテクチャの NUMA ノード間で転送が行われることも原因になります)。

そうは言っても、配列ベースの可変コレクションは、スラック領域の浪費による悪影響を受けます。大規模なコレクションからほとんどの項目を削除しても、基になる配列は縮小せず、不必要にメモリを占有し続けます。リンクベースの不変コレクションの場合は、項目ごとに 1 つのオブジェクトが必ず維持されます。しかし、通常のユースケースを考えると、この点がリンクコレクションにとっての強みになることはほとんどありません。

不変コレクションを使用するタイミング

不変性の最も重要なメリットは、コードの動作を非常に推測しやすくなることです。その結果、正確かつ洗練されたコードを短時間で作成できるようになります。シングルスレッドのプログラムを考えてみましょう。コードの特定行における不変コレクションの状態を確認する必要があるとします。これは、そのコレクションが作成されたコード内の位置を突き止めることにより、簡単に特定できます。通常、このような場所は数が少なく、そのいずれか 1 つに該当します。このプロセスを続けることで、可変ソースにたどり着くか、コレクションが空になります。不変コレクションがメソッドに渡されたかどうかは重要ではありません。不変コレクションは構造が維持されることが保証されているため、これらのメソッドで起こったことは考慮する必要がありません。項目の型が不変であれば、コレクションの完全な状態を推測できます。このような推測は、マルチスレッドプログラムでも同じくらい簡単です。ただし、共有可変コレクションを使用する場合は大幅に難しくなります。したがって、関数型プログラムの場合と同様に、不変性が一般的な設計原則になる可能性があります。

ここで、次のメソッドシグネチャを考えてみましょう。

void Foo<T>(Stack<T> s);

このメソッドには可変スタックパラメーターがあるため、メソッドによりスタックが変更される可能性があります。事実、それがこのメソッドの目的であるとも言えるでしょう。ただし、実際にスタックを変更すると、呼び出し元でコピーを作成しない限り、スタックの古い状態は失われます。メソッドでスタックを変更した場合でも、メソッドは何も返す必要はありません。このシグネチャからわかることはもう 1 つあります。それは、スレッドセーフ性が保証されないことです。

スレッドセーフが問題にならない場合で、なおかつメソッドによってスタックが変更されることが見込まれていて、そのような変更に関心がある場合は、このシグネチャが最適です。メソッドで、スタックを読み込むことや、調査することしか目的にしていない場合 (または、スタックを変更する可能性はあるが、呼び出し元ではその変更をまったく気にしない場合) は、次のシグネチャの方が適切です。

void Foo<T>(ReadOnlyCollection<T> s);

これには 2 つの問題があります。1 つ目の問題は、ReadOnlyCollection<T> で List<T> が構築されている必要があることです。そのため、呼び出し元はスタックをリストにコピーしなければなりません。パラメーターをインターフェイス型 IReadOnlyCollection<T> にすることでこの問題を回避できます。Stack<T> でこのインターフェイス型が実装されるためです。その後、メソッドで同じくらい簡単に元の Stack<T> に変換することができます。2 つ目の問題は、通常、メソッドでスタックに変更を加える場合、最初にスタックを可変コレクションにコピーする必要があることです。このシグネチャもまたスレッドセーフ性を保証しません。これが便利なのは、最初の可変コレクションが List<T> で、メソッドでその List<T> を変更することがない場合のみです。

コレクションにアクセスするスレッドが複数存在する可能性があるシナリオでは、次のシグネチャの方が適切でしょう。

void Foo<T>(ConcurrentStack<T> s);

ConcurrentStack<T> は可変です。そのため、すべてのスレッドですべての変更が確認されます。このシグネチャが適するのは、次に挙げる 2 つの状況のうち、少なくとも 1 つは満たしている場合に限られます。 1 つ目の状況は、他のスレッドによって変更が加えられる可能性がある場合に、そうした変更が行われた瞬間に、メソッドでその変更を考慮することが見込まれる場合です。もう 1 つの状況は、メソッドによって変更が加えられた瞬間に、その変更を他のスレッドで確認する必要がある場合です。どのスレッドも、特定の変更を個別に確認できることに注意してください。それ以外の場合で、一部のスレッドで一群の変更だけを確認する必要があったり、変更を確認する必要がなかったりする場合は、グローバルにロックをかけて、スタックのプライベートコピーを作成しなければなりません。前述の 2 つの状況は、スナップショットセマンティクスと呼ばれます。

シナリオが異なれば、さまざまなコレクション型を使用することが必要になります。また、メソッドの動作やその使用方法を説明するために優れたドキュメントも望まれることでしょう。不変コレクションを使えば、こうしたことがすべて簡略化されます。次の 2 つのシグネチャはほとんどのシナリオに対応します。

void Foo1<T>(ImmutableStack<T> s);
ImmutableStack<T> Foo2<T>(ImmutableStack<T> s);

実に美しい API でしょう。1 つ目のシグネチャは、メソッドにより加えられる変更にまったく関心が持たれていない場合に使用します。それ以外の場合は、2 つ目のシグネチャを使用します。不変コレクションが適さない状況は 2 つしかありません。スループット (項目が処理される速度) が必要な場合と、プロデューサー/コンシューマーセマンティクスです。前に示したように、汎用の不変コレクションはスループットが低くなります。シングルスレッドシナリオでは特にそうです。プロデューサー/コンシューマーセマンティクスでは、可変同時実行コレクションの方がより洗練されていて、優れたパフォーマンスを得られます。プロデューサー/コンシューマーセマンティクスとスナップショットセマンティクスの違いは、読み取りエージェントまたは使用エージェントの動作方法にあります。前者の場合は要素が使用 (永久的に削除) されます。一方、後者の場合は要素が処理され、書き込みエージェントまたは生成エージェントによってのみ要素が削除されます。個人的に、スナップショットセマンティクスをチェンジャー/プロセッサーセマンティクスと呼ぶのが気に入っています。その理由は、変更エージェントと処理エージェントが存在しているためです。処理エージェントは条件付きで変更を行うことができます。その条件とは、他のコピーと共に必要とされる別のコピーに、その変更を保持することです。これらの変更が全体的に行われるとしたら、プロデューサー/コンシューマーセマンティクスの領域になるでしょう。

便利なインターフェイスと API

可変コレクションやコレクション関連インターフェイスを不変コレクションに変換する ToXxx 拡張メソッドは数多く存在します。これらのメソッドは、可変コレクションを再利用するのではなく、可変コレクションをコピーすることで、不変性を維持します。多くの不変コレクションは、並べ替え用や検索用のメソッドなど、便利なメソッドを提供しています。これは、可変コレクションによって提供されているメソッドと同様のものです。このことは、両方の種類のコレクションを使用する混合コードに役立ちます。

不変コレクションを既存のコードベースでもっと使いやすいものにするために、一部の不変コレクションは一般的で適切なインターフェイスを実装しています。たとえば、IEnumerable<T>、IList<T>、ICollection<T> などです。IList<T>.Insert など、宣言されている一部のメソッドは、コレクションを変更するためのものです。これらのメソッドは、NotSupportedException をスローすることで実装されます。不変コレクションは、NuGet パッケージで定義された対応する不変インターフェイスも実装します。

System.Collections.Immutable.ImmutableInterlocked 型は、不変コレクションの項目を適切に更新したり、不変コレクションを参照したりするための、インターロック交換メカニズムを実装するメソッドを多数提供します。たとえば、次のメソッドは項目への参照を受け取り、指定された変換ツールに応じて項目を更新します。

public static bool Update<T>(ref T location, Func<T, T> transformer) where T : class;

このような操作の影響はすべてのスレッドで監視できます。その一方で、そのすべてのスレッドで常に同じ項目が監視されていることが保証されます。

まとめ

今回は、不変コレクションのメリットを説明し、不変スタック、不変リスト、不変配列、および不変辞書の設計と実装について詳しく解説しました。NuGet パッケージに含まれる不変コレクションは他にも数多く存在します。ほぼすべての可変コレクションに対応する不変コレクションが存在し、それらは NuGet パッケージで見つけられます。今回紹介した型を読者のコードで効果的に使用していただければさいわいです。不変パターンを気に入って、不変型を独自に記述することを考えている場合は、Andrew Arnott が作成した Roslyn ベースツールを使うことで、可変型を記述するのと同じくらい簡単に不変型を作成できます。詳細については、bit.ly/2ko2s5O (英語) を参照してください。

Hadi Brais は、インド工科大学デリー校で博士号を取得した研究者で、次世代のメモリシステム向けのコンパイラ最適化について研究しています。彼は、自身の時間のほとんどを C/C++/C# のコード作成や、ランタイム、コンパイラフレームワーク、およびコンピューターアーキテクチャの詳細な調査に費やしています。彼のブログは hadibrais.wordpress.com (英語) で、連絡先は hadi.b@live.com (英語のみ) です。

この記事のレビューに協力してくれた技術スタッフの Andrew Arnott と Immo Landwerth に心より感謝いたします。