数组的缓存位置和摊销的复杂性
Cache locality of an array and amortized complexity
数组通常比链表访问速度更快。
这主要是由于数组的缓存位置。
我有两个疑问：
- 带入高速缓存的数据量取决于什么因素？是不是完全等于系统的缓存？我们怎么知道这是多少内存？
- 第一次访问数组通常成本较高，因为数组必须在内存中搜索并带入内存。随后的操作相对更快。我们如何计算访问操作的摊销复杂度？
- 什么是缓存未命中？这是否意味着（参考链表）所需的项目（当前指针->下一个）尚未加载到缓存内存中，因此必须再次搜索内存以获取其地址？
实际上，它比您在问题中提出的简单模型要复杂一些。
首先，您可能有多个缓存层（L1、L2、L3），每个缓存层都有不同的特性。特别是，每个缓存的替换策略可能会使用不同的算法作为效率和复杂性（即成本）之间的权衡。
然后，所有现代操作系统都实现了虚拟内存机制。仅缓存数据和指令（这是 L1..L3 的用途）是不够的，还需要缓存虚拟地址和物理地址之间的关联（在 TLB 中，事务后备缓冲区）。
要了解局部性的影响，您需要考虑所有这些机制。
问题一
内存和缓存之间交换的最小单位是缓存行。通常，它是 64 字节（但它取决于 CPU 模型）。让我们假设缓存是空的。
如果你迭代一个数组，你将支付每 64 个字节的缓存未命中。一个聪明的 CPU（和一个聪明的程序）可以分析内存访问模式并决定预取缓存中的连续内存块以增加吞吐量。
如果您在列表上进行迭代，访问模式将是随机的，您可能会为每个项目支付一次缓存未命中。
问题二
第一次访问时不搜索整个数组并将其放入缓存。只有第一个缓存行是。
不过，还有一个因素需要考虑：TLB。页面大小取决于系统。典型值为 4 KB。第一次访问数组时，将进行地址转换（其结果将存储在 TLB 中）。如果数组小于 4 KB（页面大小），则无需进行其他地址转换。如果它更大，每页将完成一个翻译。
将此与列表进行比较。多个项目适合同一页 (4 KB) 的概率远低于数组。它们可以放入同一缓存行（64 字节）的可能性极低。
我认为很难计算复杂度，因为可能还有其他因素需要考虑。但是在这种复杂性中，您必须考虑缓存行大小（对于缓存未命中）和页面大小（对于 TLB 未命中）。
问题3
缓存未命中是指给定的缓存行不在缓存中。它可以发生在 L1、L2 或 L3 级别。等级越高越贵
当虚拟地址不在TLB中时发生TLB未命中。在这种情况下，使用页表（成本高）完成到物理地址的转换，并将结果存储在 TLB 中。
所以是的，使用链表，您可能会比数组支付更多的缓存和 TLB 未命中。
有用链接：
关于 CPUs 缓存的维基百科文章：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/
数组通常比链表访问速度更快。 这主要是由于数组的缓存位置。 我有两个疑问：
- 带入高速缓存的数据量取决于什么因素？是不是完全等于系统的缓存？我们怎么知道这是多少内存？
- 第一次访问数组通常成本较高，因为数组必须在内存中搜索并带入内存。随后的操作相对更快。我们如何计算访问操作的摊销复杂度？
- 什么是缓存未命中？这是否意味着（参考链表）所需的项目（当前指针->下一个）尚未加载到缓存内存中，因此必须再次搜索内存以获取其地址？
实际上，它比您在问题中提出的简单模型要复杂一些。
首先，您可能有多个缓存层（L1、L2、L3），每个缓存层都有不同的特性。特别是，每个缓存的替换策略可能会使用不同的算法作为效率和复杂性（即成本）之间的权衡。
然后，所有现代操作系统都实现了虚拟内存机制。仅缓存数据和指令（这是 L1..L3 的用途）是不够的，还需要缓存虚拟地址和物理地址之间的关联（在 TLB 中，事务后备缓冲区）。
要了解局部性的影响，您需要考虑所有这些机制。
问题一
内存和缓存之间交换的最小单位是缓存行。通常，它是 64 字节（但它取决于 CPU 模型）。让我们假设缓存是空的。
如果你迭代一个数组，你将支付每 64 个字节的缓存未命中。一个聪明的 CPU（和一个聪明的程序）可以分析内存访问模式并决定预取缓存中的连续内存块以增加吞吐量。
如果您在列表上进行迭代，访问模式将是随机的，您可能会为每个项目支付一次缓存未命中。
问题二
第一次访问时不搜索整个数组并将其放入缓存。只有第一个缓存行是。
不过，还有一个因素需要考虑：TLB。页面大小取决于系统。典型值为 4 KB。第一次访问数组时，将进行地址转换（其结果将存储在 TLB 中）。如果数组小于 4 KB（页面大小），则无需进行其他地址转换。如果它更大，每页将完成一个翻译。
将此与列表进行比较。多个项目适合同一页 (4 KB) 的概率远低于数组。它们可以放入同一缓存行（64 字节）的可能性极低。
我认为很难计算复杂度，因为可能还有其他因素需要考虑。但是在这种复杂性中，您必须考虑缓存行大小（对于缓存未命中）和页面大小（对于 TLB 未命中）。
问题3
缓存未命中是指给定的缓存行不在缓存中。它可以发生在 L1、L2 或 L3 级别。等级越高越贵
当虚拟地址不在TLB中时发生TLB未命中。在这种情况下，使用页表（成本高）完成到物理地址的转换，并将结果存储在 TLB 中。
所以是的，使用链表，您可能会比数组支付更多的缓存和 TLB 未命中。
有用链接：
关于 CPUs 缓存的维基百科文章：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/