.NET 6のAPI変更に関するこのシリーズ記事で、今回はコレクションを取り上げる。
List、Stack、Queueのキャパシティについて
DictionaryやHashSetに大量のデータを挿入する前には、想定されるコレクションのサイズを指定してEnsureCapacityを呼び出しておくとよい。こうすることで、コレクションが事前に1回だけサイズ変更を行うようになるため、繰り返しサイズ変更を行う必要を回避することができる。
このEnsureCapacityメソッドがList<T>、Stack<T>、Queue<T>の各クラスにも追加され、同じようなパフォーマンス上のメリットを享受できるようになった。
このグループからの注目すべき例外はCollection<T>である。他とは違ってCollection<T>は、他のコレクションをラップすることが可能なのだが、それが必ずしもEnsureCapacityメソッドをエクスポートしているとは限らないからだ。Collection<T>のサブクラスであるObservableCollection<T>も同じように、EnsureCapacityメソッドをエクスポートしていない。
Collection<T>とObservableCollection<T>の設計上の問題はこれに留まらない。AddRangeメソッドがないことも、長く開発者の不満の的になっている。List<T>が提供するような、ハイパフォーマンスな構造体ベースのIEnumeratorも存在しない。List<T>をラップするコンストラクタとそれに関連する問題を伴わない、新たな代替クラスを提供する時が来たのではないだろうか。
可変構造体とDictionary
まれなケースではあるが、変更可能(mutable)な構造体のDictionaryが必要になる場合がある。これが難しいのは、変更可能な構造体では予期しないコピーが簡単に行われるため、結果として2つの値の同期が失われる可能性があるからだ。
回避策は、構造体を意図的にコピーした上で変更し、結果を元の場所にコピーして戻す、という方法になる。小さな構造体ならばこれでよいが、構造体の規模が大きいと、この処理は高価なものになる可能性がある。また、可変構造体を使用する理由として、パフォーマンスが最初にあげられることが多い点からも、コピーアウト/コピーインを使う方法は非生産的である。
このような不必要なコピーを回避するため、可変構造体は配列に格納するのが一般的だった。List<T>のインデクサとは違い、配列の要素は直接アクセスできるからだ。
C# 7では参照戻り値(ref returns)が導入された。これによってインデクサは、構造体のコピーではなく、参照を返すことが可能になった。
public ref int this[int index]
{
get { return ref _internalArray[index]; }
}
このテクニックは、.NET Core 2.1から導入されたSpan<T>構造体で使用されている。また、.NET 5以降では、CollectionsMarshal.AsSpanメソッドを使ってコレクションのSpanラッパを簡単に取得することができる。
同じ機能をDictionaryでも提供するため、CollectionMarshal.GetValueRefOrNullRefという関数が新たに設けられた。この関数には、いくつかの興味深い点がある。
まず第1に、拡張メソッドではない。誤った使用をされやすいのではないか、と恐れた開発者たちが、意図的に見つけ難くしようと考えたのだ。(Span<T>が存在する場合はコレクションのサイズを変更できないため、AsSpan関数も安全でない可能性がある。)
次に興味深いのは、この関数が内部メソッドDictionary<TKey, TValue>.FindValueとして既に存在していた点である。単にGetValueRefOrNullRefを通じて、このメソッドを公開したに過ぎないのだ。
public static ref TValue GetValueRefOrNullRef<TKey, TValue>(Dictionary<TKey, TValue> dictionary, TKey key) where TKey : notnull
=> ref dictionary.FindValue(key);
FindValue自体では、C#プログラミングではあまり馴染みのないテクニックをいくつも使用している。ここに示した最後の数行には、後方へのジャンプを含む、goto文の奔放な利用が見られる。
// The chain of entries forms a loop; which means a concurrent update has happened.
// Break out of the loop and throw, rather than looping forever.
goto ConcurrentOperation;
}
}
goto ReturnNotFound;
ConcurrentOperation:
ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
ReturnFound:
ref TValue value = ref entry.value;
Return:
return ref value;
ReturnNotFound:
value = ref Unsafe.NullRef<TValue>();
goto Return;
}
GetValueRefOrNullRefをコールした後は、CompilerServices.Unsafe.IsNullRefを使って結果が実際の値への参照なのか、あるいはnullなのかを確認する必要がある。これは、構造体参照かnullかどうかをチェックする構文がC#に存在しないためだ。
Dictionaryのシリアライゼーション拡張
Listスタイルのコレクションのシリアライズは比較的分かりやすいが、DictionaryやHashSetのようにコンポーネントのハッシュが必要なコレクションではいくつかの課題がある。そのひとつは、コンテンツだけでなく、比較に使用するアルゴリズムもシリアライズする必要があることだ。これによってデシリアライザは、コレクションを生成する際の比較子において、通常の順序かカルチャ固有か、大小文字を区別するかしないか、といったことの必要性を認識するのである。
こうした課題の大半は文字列を基本とするキーで解決可能であるため、StringComparerに2つの新メソッドが追加されることになった。
public static bool IsWellKnownOrdinalComparer(IEqualityComparer<string?>?comparer, out bool ignoreCase);
public static bool IsWellKnownCultureAwareComparer(IEqualityComparer<string?>?comparer, [NotNullWhen(true)] out CompareInfo?compareInfo, out CompareOptions compareOptions);
この2関数をチェックすることによって、シリアライザは、後のデシリアライズに必要な情報を収集することができる。これがすべてのシナリオをカバーする訳ではないが、既知のカルチャをベースとしない独自の比較子が必要になることはレアケースだ。
このソリューションは、しかし、完璧ではない。SOAP XMLもJSONもプロパティをコレクションに関連付けることができないので、シリアライザは情報を格納する独自の方法を決めなくてはならない。
プライオリティキュー
新しいPriorityQueueクラスは、優先度スコアに基づいてアイテムをリスト配置するキューが必要なシナリオを想定して設計されている。実装方法はいくつかあるが、その多くは"アイテムの優先度を変更できるか？"という質問によって大きく分類される。
.NETのPriorityQueueは、優先度の変更を許可しないタイプである。このように決定したのは、優先度スコアを固定にすることで、変更可能な場合に比べて"2~3倍高速"なパフォーマンスが得られるからだ。
優先度スコアが変更不可能であることを確実に示すため、次のように、キューされるオブジェクトとは別に指定する方法を採用している。
public void Enqueue(TElement element, TPriority priority);
設計面での次の問題は安定性だ。同じ優先度の2つのアイテムをキューに追加した場合、同じ順序で取り出すことができることが保証されていれば、そのキューは安定していると判断される。.NETでは、安定的なキューアルゴリズムを提供しないことを決定した。これにより、不安定なアルゴリズムの方が高速であれば、そちらを選択することが可能になっている。
もうひとつの設計判断は、キューの列挙を許可するかどうかである。一見するとこれは、奇妙な命題に思えるかも知れない。for-eachループをキューで使用可能にしたくない理由があるのだろうか？
最初の問題は、IEnumerableの暗黙のコントラクトである。ほとんどの開発者は、同じコレクションを2回列挙すれば、両方の処理で同じ結果が得られるものと想定している。列挙が必ずしも実行されるとは限らない場合も含めて、この想定は、一般的なパターンとして組み込まれているのだ。次の例を考えてほしい。
public static TElement[] CopyToArray<TElement>(this IEnumerable<TElement> source)
{
var count = source.Count();
var result = new TElement[count];
var i = 0;
foreach (var item in source)
result[i++] = item;
return result;
}
式source.Count()はカウントを取得するためにキューのアイテムを列挙して数え、その数を通知する。結果として、for-eachループには空のキューが渡されることになり、配列には何も格納されない。
列挙子を非破壊的にする、という考えもあるが、これにはまた別の問題がある。優先度キューにおいて、内部的な順序付けは必須ではない。これはつまり、列挙子が、すでに処理したアイテムを追跡できなくてはならない、ということだ。何らかの理由で複数の列挙子を同時に実行すれば、それぞれが最終的にキューの完全なコピーを行うことになる。
このような理由から、PriorityQueueクラスでは、IEnumerable<T>は実装されていない。これは同時に、ICollection<T>や同様のインターフェースも実装できない、ということだ。
for-eachループでPriorityQueueを使いたい場合は、次の拡張メソッドを利用することができる。
public static IEnumerable<TElement> GetDequeuingEnumerator<TElement, TPriority>(this PriorityQueue<TElement, TPriority> queue)
{
while (queue.TryDequeue(out var item))
yield return item;
}
本シリーズのこれまでのレポートについては、以下のリンクを参照して頂きたい。