数组的缓存局部性和平摊复杂度

数组的访问速度通常比链表快。这主要是由于数组的缓存局部性。我有两个疑问:

实际上，它比您在问题中提供的简单模型要复杂一些。

首先，您可能有多个缓存层(L1、L2、L3)，每个缓存层都有不同的特征。特别是，每个缓存的替换策略可能使用不同的算法来权衡效率和复杂性(即成本)。

那么，所有现代操作系统都实现了虚拟内存机制。缓存数据和指令(这就是L1..)是不够的。L3用于)，还需要缓存虚拟地址和物理地址之间的关联(在TLB中，事务暂存缓冲区)。

要理解局部性的影响，你需要考虑所有这些机制。

问题1

内存和缓存之间交换的最小单位是缓存线。通常，它是64字节(但这取决于CPU模型)。让我们假设缓存是空的。

如果你在一个数组上迭代，你将为每64字节的缓存缺失付出代价。智能CPU(和智能程序)可以分析内存访问模式，并决定在缓存中预取连续的内存块，以提高吞吐量。

如果你在一个列表上迭代，访问模式将是随机的，并且你可能会为每一项支付缓存缺失。

问题2

在第一次访问时不搜索整个数组并将其放入缓存。只有第一条缓存行是。

然而，还有另一个因素需要考虑:TLB。页面大小取决于系统。典型值为4kb。第一次访问数组时，将发生地址转换(其结果将存储在TLB中)。如果数组小于4 KB(页面大小)，则不需要进行其他地址转换。如果大于，则每页翻译一次以上

将其与列表进行比较。多个项目放入同一页(4 KB)的概率远低于数组。它们可以放在同一缓存行(64字节)中的概率非常低。

我认为计算复杂性是困难的，因为可能还有其他因素要考虑。但是在这种复杂性下，您必须考虑缓存行大小(缓存丢失)和页面大小(TLB丢失)。

问题3

缓存缺失是指给定的缓存行不在缓存中。它可以发生在L1、L2或L3级别。级别越高，价格越贵。

虚拟地址不在该TLB中，发生TLB miss。在这种情况下，使用页表完成到物理地址的转换(开销很大)，并且结果存储在TLB中。

所以，是的，与数组相比，使用链表可能会为更高数量的缓存和TLB丢失付出代价。

的有用链接:

维基百科关于cpu缓存的文章:https://en.wikipedia.org/wiki/CPU_cache
关于这个主题的另一篇好文章:http://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips
关于同一主题的一篇古老但优秀的文章:http://arstechnica.com/gadgets/2002/07/caching/
各种缓存效果的图库:http://igoro.com/archive/gallery-of-processor-cache-effects/

相关内容