oup*_*phi 6 c optimization caching linked-list cpu-cache
我想知道链接列表与C中的连续数组相比有什么优缺点.因此,我读了一篇关于链表的维基百科文章. https://en.wikipedia.org/wiki/Linked_list#Disadvantages
根据这篇文章,缺点如下:
- 由于指针使用的存储空间,它们使用的内存多于数组.
- 必须从头开始按顺序读取链接列表中的节点,因为链接列表本质上是顺序访问.
在反向遍历方面,链表中出现了困难.例如,单个链表很难向后导航,而双链表更容易阅读,内存浪费在分配上.
节点存储不明确,大大增加了访问列表中各个元素所需的时间,尤其是CPU缓存.
我理解前3分,但我最后一点很难:
节点存储不明确,大大增加了访问列表中各个元素所需的时间,尤其是CPU缓存.
关于CPU Cache的文章没有提到任何关于非连续内存阵列的内容.据我所知,CPU缓存仅缓存经常使用的地址,总共10 ^ -6缓存未命中.
因此,我不明白为什么CPU缓存在非连续内存阵列方面的效率会降低.
Zby*_*000 11
CPU缓存实际上做了两件事.
你提到的那个是缓存最近使用过的内存.
然而另一个是预测将来会使用哪种内存.该算法通常非常简单 - 它假定程序处理大量数据,每当它访问某些内存时,它将预取更多的字节.
这不适用于链表,因为节点随机放在内存中.
此外,CPU加载更大的内存块(64,128字节).同样,对于具有单个读取的int64数组,它具有用于处理8或16个元素的数据.对于链表,它会读取一个块,其余的可能会被浪费,因为下一个节点可能位于完全不同的内存块中.
最后但并非最不重要的是,与上一节相关 - 链接列表为其管理需要更多内存,最简单的版本将至少为指向下一个节点的指针增加sizeof(指针)字节.但它不再是CPU缓存了.
这篇文章只是在摸索，并弄错了一些地方（或至少是有问题的），但是总体结果通常是相同的：链接列表要慢得多。
要注意的一件事是，“节点不连续存储（原文如此）”是一个过分的主张。的确，通常，例如，由返回的节点malloc可能会在内存中散布，特别是如果在不同时间或从不同线程分配节点时。但是，实际上，许多节点通常同时分配在同一线程上，而这些节点通常最终会在内存中非常连续，因为好的malloc实现非常好！此外，在性能方面，您可能经常在每个对象的基础上使用特殊的分配器，该分配器从一个或多个连续的内存块中分配固定大小的音符，这将提供很大的空间局部性。
因此，您可以假设至少在某些情况下，链表将为您提供合理的良好空间局部性。这在很大程度上取决于您是一次添加所有列表元素中的大多数（链接列表的确可以），还是在更长的时间内不断添加元素（链接列表的空间位置较差）。
现在，在列表变慢的方面，链接列表掩盖的主要问题之一是与某些相对于数组变量的操作相关的常量常数。每个人都知道，在给定元素索引的情况下访问元素O(n)位于链表和O(1)数组中，因此，如果要按索引进行大量访问，则不必使用链表。同样，每个人都知道，将元素添加到列表的中间需要花费O(1)链表中的O(n)时间和数组中的时间，因此前者在这种情况下会获胜。
他们并没有解决什么是具有相同算法的复杂性甚至操作可能是很多在实践中慢一个实现...
让我们遍历列表中的所有元素（也许正在寻找特定值）。O(n)无论您使用链接表示形式还是数组表示形式，这都是一项操作。所以这是一条领带，对吗？
没那么快！实际表现可能相差很大！这是在x86 gcc中find()以-O2优化级别进行编译时的典型实现的外观，这要归功于godbolt的简化。
int find_array(int val, int *array, unsigned int size) {
for (unsigned int i=0; i < size; i++) {
if (array[i] == val)
return i;
}
return -1;
}
.L6:
add rsi, 4
cmp DWORD PTR [rsi-4], edi
je .done
add eax, 1
cmp edx, eax
jne .notfound
struct Node {
struct Node *next;
int item;
};
Node * find_list(int val, Node *listptr) {
while (listptr) {
if (listptr->item == val)
return listptr;
listptr = listptr->next;
}
return 0;
}
.L20:
cmp DWORD PTR [rax+8], edi
je .done
mov rax, QWORD PTR [rax]
test rax, rax
jne .notfound
只是盯着C代码，这两种方法看起来都很有竞争力。数组方法将增加i，进行两次比较，并进行一次内存访问以从数组中读取值。链表版本，如果要具有几个（相邻）内存访问权限来读取Node.val和Node.next成员，以及几个比较。
汇编似乎可以证明这一点：链表版本有5条指令，数组版本2有6条指令。所有指令都是简单的指令，在现代硬件上每个周期的吞吐量为1或更高。
如果您进行测试- 两个列表都完全驻留在L1中，您会发现数组版本每次迭代的执行周期约为1.5 cyles，而链表版本的执行周期约为4！这是因为链表的版本受其对循环的依赖所限制listptr。一行可以listptr = listptr->next归结为on指令，但是一条指令永远不会每4个周期执行一次以上，因为每次执行都取决于前一条指令的完成（您需要先完成阅读listptr->next才能计算listptr->next->next）。即使现代的CPU每个周期可以执行2个加载周期，但这些加载大约需要4个周期才能完成，因此这里遇到了串行瓶颈。
数组版本也有负载，但是地址不取决于先前的负载：
add rsi, 4
cmp DWORD PTR [rsi-4], edi
它仅取决于rsi，只需通过将每个迭代加4即可计算得出。add在现代硬件上，An 的延迟时间为一个周期，因此不会造成瓶颈（除非您获得低于1个周期/迭代的延迟）。因此，阵列循环能够利用CPU的全部功能，并行执行许多指令。链表版本不是。
这不是“查找”所独有的-任何需要迭代许多元素的链接操作都将具有这种指针追踪行为，这在现代硬件上本质上是缓慢的。
1我省略了每个汇编函数的结尾和序言，因为它实际上并没有做任何有趣的事情。两种版本都完全没有尾声，两者的口号非常相似，剥离了第一次迭代并跳入了循环的中间。完整代码可在任何情况下进行检查。
2值得注意的是，gcc并没有像它在这里那样出色，因为它既可以rsi作为数组的指针，也可以eax作为索引i。这意味着两个单独的cmp指令和两个增量。最好只rsi在循环中保留指针，然后将(array + 4*size)其与“未找到”条件进行比较。那将消除一个增量。另外，您可以cmp通过rsi从-4*size零到零运行，并使用[rdi + rsi]rdi是的位置索引到数组来消除一个array + 4*size。表明即使在今天，优化编译器也无法解决所有问题！