c# - ImmutableList によるパフォーマンスの低下Microsoft.Bcl.Immutable のメソッドを削除

Question

ImmutableListNuGet パッケージMicrosoft.Bcl.Immutableバージョン 1.0.34 および 1.1.22-betaから Microsoft の予期しないパフォーマンスが発生する

不変リストからアイテムを削除すると、パフォーマンスが非常に遅くなります。20000 個の整数ImmutableList値 (1...20000) を含む場合、値 20000 から 1 への削除を開始すると、リストからすべてのアイテムを削除するのに約 52 秒かかります。各削除操作の後にリストのコピーを作成するジェネリックList<T>で同じことを行うと、約500ミリ秒かかります。

ImmutableListはジェネリックをコピーするよりも速いと思っていたので、これらの結果には少し驚きましたList<T>が、おそらくこれは予想されることでしょうか?

サンプルコード

// Generic List Test
var genericList = new List<int>();

var sw = Stopwatch.StartNew();
for (int i = 0; i < 20000; i++)
{
    genericList.Add(i);
    genericList = new List<int>(genericList);
}
sw.Stop();
Console.WriteLine("Add duration for List<T>: " + sw.ElapsedMilliseconds);
IList<int> completeList = new List<int>(genericList);

sw.Restart();

// Remove from 20000 -> 0.
for (int i = completeList.Count - 1; i >= 0; i--)
{
    genericList.Remove(completeList[i]);
    genericList = new List<int>(genericList);
}
sw.Stop();
Console.WriteLine("Remove duration for List<T>: " + sw.ElapsedMilliseconds);
Console.WriteLine("Items after remove for List<T>: " + genericList.Count);


// ImmutableList Test
var immutableList = ImmutableList<int>.Empty;

sw.Restart();
for (int i = 0; i < 20000; i++)
{
    immutableList = immutableList.Add(i);
}
sw.Stop();
Console.WriteLine("Add duration for ImmutableList<T>: " + sw.ElapsedMilliseconds);

sw.Restart();

// Remove from 20000 -> 0.
for (int i = completeList.Count - 1; i >= 0; i--)
{
    immutableList = immutableList.Remove(completeList[i]);
}
sw.Stop();
Console.WriteLine("Remove duration for ImmutableList<T>: " + sw.ElapsedMilliseconds);
Console.WriteLine("Items after remove for ImmutableList<T>: " + immutableList.Count);

アップデート

ImmutableList通常の foreach ループのように、の先頭からアイテムを削除すると、パフォーマンスが大幅に向上します。すべてのアイテムを削除するのにかかる時間は 100 ミリ秒未満です。これはすべてのシナリオでできることではありませんが、知っておくとよいでしょう。