一个缓存感知算法的简单例子？

Question

有人可以发布一些关于缓存感知算法的简单解释吗？虽然有很多链接可用，但这些网站上的阅读材料都具有学术性质，需要花费时间才能阅读和理解。

- Sesh

Answer 1

一个“缓存感知算法”旨在最小化内存页在处理器芯片上的缓存中进出移动。其想法是避免所谓的“缓存未命中”，这会导致处理器停顿，同时从RAM加载数据到处理器缓存中。

一个看起来不太优秀的“缓存感知算法”可以胜过理论上更快的传统算法，因为缓存感知算法更有效地使用内存。

一个“缓存感知算法”被明确编码以利用处理器的缓存行为。处理器的内存页大小和“缓存行”的详细信息被编码到算法中。因此，缓存感知算法将非常依赖于特定处理器。

一个“缓存无关算法”编码的方式比传统算法更适合缓存，但它不依赖于底层硬件的详细信息。

- Jim Mischel

---

他不是要求举例子吗？！ - ljs

不行。问题中说了，“简单解释”。 - Jim Mischel

这是一个糟糕的例子：https://dev59.com/iWgu5IYBdhLWcg3wkH6P#11227902，在运行函数之前对数据进行排序使其快了6倍。 - Mooing Duck

完全没有必要“高度特定于处理器”。几十年来，大多数台式机处理器都使用64字节的缓存行。用Mike Acton的话来说，“你不是为所有处理器进行优化，而是为某些处理器子集进行优化。没有人会为6502和Google Cloud同时编写代码。”“高度特定”意味着“Intel i5-4570K”，而不是“自2003年以来的所有amd64处理器”。 - undefined

Answer 2

我认为最简单的缓存感知算法之一就是按行优先和按列优先访问二维数组。由于二维数组通常在内存中被存储为数组所有行的拼接，逐行访问可以在适当的时间将数据放入缓存中。但是，按列优先访问数组可能会导致大量的内存跳跃和缓存未命中，从而导致速度变慢。

举个例子，下面是一段C++代码：

for (int i = 0; i < MAX_N; ++i) {
  for (int j = 0; j < MAX_N; ++j) {
   a[i][j] = 10;
  }
}

如果我交换所访问的单元格的索引（即，访问a[j][i]），那么在我的计算机上运行速度比原来快3-4倍。

- Ivan Vergiliev

---

我认为这在技术上是一个缓存无感知算法的例子，因为它并不明确知道缓存的大小。 - Ben Jones