c# - Microsoft.Bcl.Immutable 中的 ImmutableList Remove 方法性能低下

Question

体验 Microsoft 的一些意外性能 ImmutableList来自 NuGet 包 Microsoft.Bcl.Immutable版本 1.0.34 和 1.1.22-beta

从不可变列表中删除项目时，性能非常慢。对于 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内部是一个树结构。这意味着要扫描列表，存在大量指针取消引用和不可预测的分支和内存访问。那很慢。