为什么双链表中的指针追逐可以避免缓存抖动（自驱逐）？
Why can pointer chasing in double-linked list avoid cache thrashing (self-eviction)?
我试图了解 this paper 缓存计时问题
在第 3.6 节中，作者解释了一种允许您填充连续缓存区域并测量此填充过程的时间的技术。他们提到：
“素数和探测步骤（即，以固定步长扫描内存缓冲区）的简单实现由于现代 CPU 中实现的两个优化而给出了糟糕的结果：内存访问的重新排序和内存的自动预读通过“硬件预取器”。我们的
攻击代码通过使用以下“指针追逐”技术绕过这两种中断。在初始化期间，攻击者的内存被组织成一个链表（可选，随机排列）；稍后，通过遍历此列表完成启动和探测（参见图 7）。为了最大限度地减少缓存抖动（自我驱逐），我们使用双向链表并向前遍历它以进行启动，但向后遍历以进行探测。此外，为了避免“污染”自己的样本，探测代码将每个获得的样本存储到它刚刚完成测量的同一缓存集中。在某些平台上，可以通过使用写入而不是读取或超过 W 读取来改善时序差距。"
我对这一段有疑问：
链表如何避免硬件预取和重排序导致的时序变化？
当前实现的硬件预取器仅处理固定步幅访问模式，因此根据内存地址任意排序的访问不会被识别为可预取。这样的硬件预取器仍然可以检测和使用意外的步幅模式。例如，如果 address[X+5] = address[X] + N 和 address[x+7] = address[x+5] + 2N（请注意，地址不必由常量访问计数分隔），预取器可能会预测 N 的步幅。这可能会适度减少明显的未命中延迟（某些预取是有效的）或引入一些缓存污染。
(如果 detected/predicted N 很小并且 linked 列表包含在相对于高速缓存大小的适度内存区域中（这样大多数步幅预取将用于解决将很快使用），基于步幅的预取 可能 有显着的积极影响。）
通过使用数据相关访问（遍历 link 需要访问数据），可以防止访问重新排序。在上一个节点的下一个指针可用之前，硬件无法加载下一个节点。
已经有支持预取此类模式甚至通用相关性的学术建议（例如，参见 this Google Scholar search for Markov prefetching），但（据我所知）尚未在商业硬件中实施。
附带说明一下，通过以与启动访问相反的顺序遍历探测访问，对于常见的、面向 LRU 的替换，可以避免过多的未命中。
我试图了解 this paper 缓存计时问题
在第 3.6 节中，作者解释了一种允许您填充连续缓存区域并测量此填充过程的时间的技术。他们提到：
“素数和探测步骤（即，以固定步长扫描内存缓冲区）的简单实现由于现代 CPU 中实现的两个优化而给出了糟糕的结果：内存访问的重新排序和内存的自动预读通过“硬件预取器”。我们的 攻击代码通过使用以下“指针追逐”技术绕过这两种中断。在初始化期间，攻击者的内存被组织成一个链表（可选，随机排列）；稍后，通过遍历此列表完成启动和探测（参见图 7）。为了最大限度地减少缓存抖动（自我驱逐），我们使用双向链表并向前遍历它以进行启动，但向后遍历以进行探测。此外，为了避免“污染”自己的样本，探测代码将每个获得的样本存储到它刚刚完成测量的同一缓存集中。在某些平台上，可以通过使用写入而不是读取或超过 W 读取来改善时序差距。"
我对这一段有疑问：
链表如何避免硬件预取和重排序导致的时序变化？
当前实现的硬件预取器仅处理固定步幅访问模式，因此根据内存地址任意排序的访问不会被识别为可预取。这样的硬件预取器仍然可以检测和使用意外的步幅模式。例如，如果 address[X+5] = address[X] + N 和 address[x+7] = address[x+5] + 2N（请注意，地址不必由常量访问计数分隔），预取器可能会预测 N 的步幅。这可能会适度减少明显的未命中延迟（某些预取是有效的）或引入一些缓存污染。
(如果 detected/predicted N 很小并且 linked 列表包含在相对于高速缓存大小的适度内存区域中（这样大多数步幅预取将用于解决将很快使用），基于步幅的预取 可能 有显着的积极影响。）
通过使用数据相关访问（遍历 link 需要访问数据），可以防止访问重新排序。在上一个节点的下一个指针可用之前，硬件无法加载下一个节点。
已经有支持预取此类模式甚至通用相关性的学术建议（例如，参见 this Google Scholar search for Markov prefetching），但（据我所知）尚未在商业硬件中实施。
附带说明一下，通过以与启动访问相反的顺序遍历探测访问，对于常见的、面向 LRU 的替换，可以避免过多的未命中。