问题标签 [cache-locality]

我意外地惊讶地发现，插入排序的键std::set比插入随机键快得多。这有点违反直觉，因为作为自平衡二叉搜索树的红黑树（我验证它std::set在我的系统上实现为红黑树）需要执行大量重新平衡操作来插入排序的序列键，因此插入排序的键应该比插入随机键花费更多的时间。

但事实是，插入排序的键可以比插入随机键快 15 倍！这是我的测试代码和一些结果：

有人解释一下吗？我猜这与缓存局部性有关，因为在插入排序键时，重新平衡通常涉及最近插入的那些节点。但以上只是我的猜测，我对缓存局部性知之甚少。

据我了解，产生“缓存局部性”高级概念的结构如下：

1. 用于虚拟内存转换的转换后备缓冲区 (TLB)。在 4096 字节对齐（页面大小）内访问相同的虚拟内存将防止操作系统需要对分层页表进行降序转换。

2. 缓存线意味着在 64 字节对齐（缓存线大小）内访问相同的虚拟内存将防止操作系统需要从 RAM 中获取指令。

我有几个问题：

1. 我从未见过对典型页表下降的定量估计。以时钟周期衡量，这实际上是否重要？

2. 我相信 64 字节缓存线是指 L1 缓存线 - L2 / L3 有不同的大小吗？内存在什么情况下加载到 L2/L3 中？

3. 除了缓存行和 TLB 之外，是否还有任何其他构造会产生“缓存局部性”？

这是一个相当假设的问题。

我对 cpu 缓存如何工作的了解有限。

我知道 CPU 会将后续字节加载到缓存中。

vector由于列表使用指向内存中随机位置的指针/间接，因此与假设或数组相比，它的局部性相对较差。

我的问题是：如果我编写一个所有节点的数据彼此相邻的分配器（通过线性分配器），这会改善缓存加载吗？间接性仍然存在，但不同节点的数据位于相似的位置。