缓存阵列的局部性和分期复杂性

阵列通常比链接列表更快。这主要是由于数组的缓存局部性。我有两个疑问：缓存阵列的局部性和分期复杂性

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

首先，您可能有多个缓存层（L1，L2，L3），每个缓存层具有不同的特性。尤其是，每个高速缓存的替换策略可以使用不同的算法作为效率和复杂度（即成本）之间的折衷。

然后，所有现代操作系统实现虚拟内存机制。仅缓存数据和指令（这是L1..L3的用途）是不够的，还需要缓存虚拟地址和物理地址（在TLB中，事务后备缓冲区）之间的关联。

要理解地点的影响，您需要考虑所有这些机制。

问题1

的最小单元的存储器之间交换和高速缓存是高速缓存行。通常，它是64个字节（但取决于CPU型号）。让我们假设缓存是空的。

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

如果您在列表上迭代，访问模式将是随机的，您可能会为每个项目支付缓存未命中。

问题2

整个数组没有查找到并在第一次访问缓存带来的。只有第一个缓存行是。

但是，还有另一个要考虑的因素：TLB。页面大小取决于系统。典型值是4 KB。第一次访问数组时，会发生地址转换（并将其结果存储在TLB中）。如果数组小于4 KB（页面大小），则不需要执行其他地址转换。如果它更大，则每页翻译一次就完成了。

将此与列表进行比较。多个项目适合在同一页面（4 KB）的概率远低于阵列。它们可以放入同一个缓存行（64字节）的概率非常低。

我认为计算复杂性很困难，因为可能还有其他因素需要考虑。但是，在这种复杂性中，你必须考虑高速缓存行大小（对于高速缓存未命中）和页面大小（对于TLB未命中）。

问题3

缓存未命中是当定高速缓存行不在缓存中。它可能发生在L1，L2或L3级别。级别越高，代价越高。

当虚拟地址不在TLB中时，发生TLB未命中。在这种情况下，使用页表格（昂贵）转换为物理地址，并将结果存储在TLB中。

所以，是的，对于链表，您可能会支付更高数量的缓存和TLB未命中数组。

相关链接：

2015-08-10 14:44:20

回答