新建一个具有非常大的初始容量的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的数组然后填充它比简单地分配每个LinkedListNode更快,因为每个T都被添加到LinkedList.

我的直觉说,同时分配一大块连续内存比在堆上任何地方分配许多小块更昂贵,因为连续内存的块不太可能已经存在.

谢谢!
杰夫

Answer 1

分配许多小内存比分配一个大块要昂贵得多,获取全局堆锁并不便宜.List <>围绕LinkedList <>运行环,cpu缓存局部为王.

Answer 2

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

但是为了更广泛地解决你的问题,我会就不同类型的列表结构有意义的场景提供一些建议.

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

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