c++ - 随机索引数组是否对顺序索引有任何性能影响？

Question

假设我们有一个名为 DataList 的长数组.我们还有另外两个包含索引的数组，一个包含按升序排列的索引(即:0, 1, 2, 3, 4, ...)，名为 sIndexes ，另一个数组由随机打包的索引组成(即:6, 5, 1, 9, 7, ...)，名为 rIndexes .
这些索引数组( sIndexes 和 rIndexes )用于索引 DataList大批。当我们使用 sIndex要索引的数组 DataList ，它按顺序索引元素。当我们使用 rIndexes索引 DataList ，它在数组中的随机位置索引。
所以我的问题是，
使用随机索引而不是顺序索引时是否有任何性能差异？缓存未命中是否会导致性能损失(例如，如果索引指向缓存行中不可用的位置)？

Answer 1

线性访问要快得多，因为:

从 RAM 获取的最小大小是一个缓存行(通常为 64 字节)。如果你只使用其中的一个字节，你就是在浪费宝贵的内存带宽。

现代 CPU 可以检测常规访问模式并从 RAM 中预取数据，因此它会在您访问之前被缓存。 (或者至少它已经以最大内存带宽进行流式传输。)

如果在编译时检测到线性访问(您的代码可能不是这种情况)，则可以将其向量化为 SIMD 指令，同时处理多个项目。

随机访问会慢得多，除非您的整个数组适合 L2 缓存，或者您为每个项目做很多工作。 L2 缓存未命中通常非常昂贵。
有关详细信息，我推荐经典的 What Every Programmer Should Know About Memory[1]，这是一本冗长而引人入胜的读物。它是从 2007 年开始的，但 CPU 架构并没有从根本上改变；如果有的话，这变得更加重要。
以上适用于现代大型 CPU。存在没有缓存但可预测 SRAM 访问的小型嵌入式 CPU。在这种情况下，随机索引将执行相同的操作。
[1] https://www.gwern.net/docs/cs/2007-drepper.pdf