ImmutableList <T>中的性能降低Microsoft.Bcl.Immutable中的删除方法

Question

ImmutableList从NuGet软件包Microsoft.Bcl.Immutable版本1.0.34以及1.1.22-beta中体验Microsoft的一些意外性能

从不可变列表中删除项目时,性能非常慢.对于ImmutableList包含20000个整数值(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毫秒.这不是你可以在所有场景中做的事情,但可以很好地了解.

Answer 1

该Remove方法必须扫描整个列表以找到要删除的元素。删除本身是 O(1) 因为只需要弹出最后一个元素。两种算法都具有二次性能。

为什么运行时间会有巨大差异？可能ImmutableList是因为内部是树结构。这意味着要扫描列表，会有大量的指针解引用和不可预测的分支和内存访问。那很慢。