c# - 新建具有非常大初始容量的 List<T> 并填充它与简单地填充 LinkedList<T> 的性能

Question

哪个更快，为什么:

IEnumerable<T> clxnOfTs = GetSeriouslyHugeCollection();
var list = new List<T>(clxnOfTs.Count);
foreach (T t in clxnOfTs) list.Add(t);

或

IEnumerable<T> clxnOfTs = GetSeriouslyHugeCollection();
var linkedList = new LinkedList<T>();
foreach (T t in clxnOfTs) linkedList.Add(t);

假设这将在具有大量内存的新型多核服务器上运行。

所以，实际上，问题是一次性预分配支持 List 的数组然后填充它是否比在每个 T 添加到 LinkedList 时简单地分配每个 LinkedListNode 更快。

我的直觉告诉我，一次性分配一个非常大的连续内存块比在堆上的任何地方分配许多小块更昂贵，因为连续内存块不太可能已经存在。

谢谢!
杰夫

Answer 1

因此，与任何与性能相关的问题一样，如果您真的关心答案，您应该创建一个真实的测试工具，以两种方式编写代码，并对其进行概要分析。

但为了从更一般的意义上解决您的问题，我会就不同类型的列表结构有意义的场景提供一些建议。

List<T>当您通常在列表末尾添加/删除项目并且很少在中间添加或删除项目时(从性能的角度来看)是有意义的。当您对列表的容量有一些期望时，它也最有效提前时间。自 List<T>在内部连续分配内存，从缓存局部性的角度来看它表现得更好。自 List<T>使用数组作为其支持结构，它对于随机(索引)访问也非常有效。

LinkedList<T>在需要经常从列表的中间或前面插入或删除项目的问题上效果更好。因为它不必重新分配或移动列表的内容来执行此操作，它将执行好多了。自 LinkedList<T>使用链接节点结构，它不提供对数据的有效随机(索引)访问。因此，如果您尝试使用像 ElementAt() 这样的 LINQ 运算符，它的性能会很差。 .从缓存局部性的角度来看，链表通常表现更差，因为它们通常被实现为按需分配节点。一些实现使用在池中分配的预缓存和回收节点来最小化此问题 - 但是，我不相信 .NET 实现会这样做。