假设我们有一个名为 DataList 的长数组。我们还有另外两个包含索引的数组，一个包含升序排列的索引(即:0、1、2、3、4，...)，名为 sIndexes，另一个数组是随机打包的索引(即:6、5、1、9、7...)，名为rIndexes。
这些索引数组(sIndexes 和 rIndexes)用于索引 DataList 数组。当我们使用sIndex数组来索引DataList时，它会按顺序索引元素。当我们使用 rIndexes 来索引 DataList 时，它会在数组中的随机位置建立索引。
所以我的问题是，
使用随机索引与顺序索引相比是否存在性能差异？缓存未命中是否会导致性能损失(例如索引指向缓存行中不可用的位置)？
最佳答案
线性访问要快得多，因为:
- 从 RAM 获取的最小大小为一个缓存行(通常为 64 字节)。如果您只使用其中的一个字节，那么您就会浪费宝贵的内存带宽。
- 现代 CPU 可以检测常规访问模式，并从 RAM 中预取数据，因此在您访问数据之前就会对其进行缓存。 (或者至少它已经以最大内存带宽进行流式传输。)
- 如果在编译时检测到线性访问(您的代码可能并非如此)，则可以将其矢量化为 SIMD 指令，从而一次处理多个项目。
随机访问会慢很多，除非你的整个数组适合二级缓存，或者你对每个项目做了很多工作。 L2 缓存未命中的代价通常相当昂贵。
有关详细信息，我推荐经典的每个程序员都应该了解内存[1]，这是一本很长且引人入胜的读物。从2007年开始，CPU架构并没有发生根本性的变化；如果有的话，这已经变得更加相关了。
上述情况对于现代大型 CPU 来说是正确的。小型嵌入式 CPU 没有高速缓存，但具有可预测的 SRAM 访问。在这种情况下，随机索引将执行相同的操作。
关于c++ - 与顺序索引相比，随机索引数组是否会对性能产生影响？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65750020/