问现代处理器(如i7)会在遍历指针列表时跟随指针并预取数据吗？

EN

我知道你没有问(可能也不需要关于正确处理缓存的说教，但我想无论如何我都要贡献我的两点意见。请注意，所有这些都只适用于热代码。请记住，过早优化是万恶之源。

正如评论中所指出的，最好的方法是拥有实际数据的容器。一般来说，平面数据结构比“指针意大利面”更可取，即使你必须复制一些数据和/或为调整/移动/整理数据结构而付出代价。

正如你所知道的，平面数据结构(例如一组数据)只有在你大部分时间线性地和顺序地访问它们时才会有回报。

但是这个策略可能并不总是有用的。代替实际的线性数据，您可以使用其他策略，如使用池分配器，以及遍历池本身，而不是遍历保存指针的向量。这当然有它自己的缺点，而且可能会更复杂一些。

我相信您已经知道了这一点，但值得再次提及的是，最有效地利用缓存的技术之一就是使用较小的数据！在上面的代码中，如果您可以使用int16_t而不是int32_t，那么您肯定应该这样做。您应该将许多bool、标志和枚举打包到位字段中，使用索引而不是指针(特别是在64位系统上)，在数据结构中使用固定大小的哈希值而不是字符串，等等。

现在，关于您的主要问题，处理器是否可以跟踪随机指针，并在需要之前将数据放入缓存中。在非常有限的范围内，这种情况确实会发生。正如你可能知道的，现代的CPU使用了很多技巧来提高它们的速度(例如，增加它们的指令退役速率)。有一个存储缓冲区，乱序执行，超标量流水线，每种类型的多个功能单元，分支预测等技巧。大多数时候，这些技巧都只是帮助CPU继续执行指令，即使当前指令已经停止或需要太长时间才能完成。对于内存加载(这是最慢的事情，如果数据不在高速缓存中)，这意味着CPU应该尽快到达指令，计算地址，并从内存控制器请求数据。但是，内存控制器只能有非常有限数量的未完成请求(这些天通常是两个，但我不确定)。这意味着，即使CPU做了非常复杂的事情来查看其他内存位置(例如，posPointers向量的元素)，并推断出这些是您的代码将需要的新数据的地址，它也不会走得太远，因为内存控制器只能有这么多待处理的请求。

在任何情况下，AFAIK，我认为CPU实际上还没有做到这一点。注意，这是一种困难的情况，因为随机分布的内存位置的地址本身就在内存中(而不是在寄存器中，或者可以从寄存器的内容中计算出来)。如果CPU做到了，由于内存接口的限制，它也不会有太大的影响。

你提到的预取技术对我来说似乎是有效的，我也见过它的使用，但只有当你的CPU在等待未来的数据到达时有事情要做时，它才会产生明显的效果。递增3个整数比从内存中加载12个字节(实际上是加载一个缓存线)所需的时间要少得多，因此对执行时间的影响不大。但是，如果你有一些有价值的、更重要的东西要覆盖在内存预取之上(例如，计算一个不需要内存中数据的复杂函数！)然后你可以得到非常好的加速。您可以看到，通过上述循环的时间本质上是所有缓存未命中的时间总和；并且您可以免费获得坐标增量和循环记账。所以，如果免费的东西更有价值，你会赢得更多！

现代处理器有硬件预取机制：Intel Hardware prefetcher。它们推断对存储器的跨步访问模式，并预取在不久的将来可能被访问的存储器位置。

然而，在完全随机的指针追逐的情况下，这样的技术是无能为力的。处理器不知道正在执行的程序正在执行指针跟踪，因此它不能相应地预取。在这种情况下，硬件机制对于性能是有害的，因为它们会预取不太可能使用的值。

你能做的最好的事情就是尝试在内存中组织你的数据结构，这样更有可能访问内存的连续部分。