我想学习如何编写更好的代码，以利用CPU的缓存。使用连续内存似乎是理想的情况。话虽如此，我很好奇是否可以使用非连续内存进行类似的改进，但是要遵循一系列的指针，例如:
struct Position {
int32_t x,y,z;
}
...
std::vector<Position*> posPointers;
...
updatePosition () {
for (uint32_t i = 0; i < posPointers.size(); i++) {
Position& nextPos = *posPointers[i];
nextPos.x++;
nextPos.y++;
nextPos.z++;
}
}
这只是一些粗糙的模拟代码，为了正确学习，我们只说所有Position结构都是在堆上随机创建的。
像Intel i7这样的现代，智能处理器能否向前看，并很快就需要
X_ptr的数据？以下代码行会有所帮助吗？... // for loop
Position& nextPos1 = *posPointers[i];
Position& nextPos2 = *posPointers[i+1];
Position& nextPos3 = *posPointers[i+2];
Position& nextPos4 = *posPointers[i+3];
... // Work on data here
我已经阅读了一些演示幻灯片，这些幻灯片似乎表明这样的代码将导致处理器预取一些数据。真的吗？我知道有一些非标准的，特定于平台的方法可以调用像
__builtin_prefetch这样的预取，但是到处扔掉这似乎是一个丑陋的过早优化。我正在寻找一种可以下意识地编写高效缓存代码的方法。
最佳答案
我知道您没有提出要求(并且可能不需要对缓存进行适当的布道，但是我想我还是会贡献我的两分钱。请注意，所有这些仅适用于热代码。请记住，过早的优化是万恶之源。
正如评论中指出的那样，最好的方法是拥有实际数据的容器。一般来说，即使您必须复制一些数据和/或为调整/移动/整理数据结构的碎片而付出代价，平面数据结构也比“指针细面条”更可取。
如您所知，扁平数据结构(例如，数据数组)只有在大多数时间以线性和顺序方式访问它们时才能获得返回。
但是这种策略可能并不总是可用的。代替实际的线性数据，您可以使用其他策略，例如使用池分配器，并在池本身上进行迭代，而不是在保存指针的 vector 上进行迭代。这当然有其自身的缺点，并且可能会更加复杂。
我相信您已经知道了这一点，但是值得一提的是，从缓存中获取最大 yield 的最有效方法之一就是拥有较小的数据!在上面的代码中，如果您可以摆脱int16_t而不是int32_t，那么您绝对应该这样做。您应该将许多bool和标记以及枚举打包到位字段中，使用索引而不是指针(特别是在64位系统上)，在数据结构中使用固定大小的哈希值，而不是字符串，等等。
现在，关于您的主要问题，即处理器是否可以遵循随机指针，并在需要它们之前将数据带入缓存。在非常有限的程度上，这确实发生了。您可能知道，现代CPU使用了许多技巧来提高速度(即提高指令退休率)。技巧包括拥有存储缓冲区，乱序执行，超标量流水线，各种功能单元，分支在大多数情况下，这些技巧都可以帮助CPU继续执行指令，即使当前指令已停顿或完成时间过长也是如此。对于内存加载(这是最慢的操作，如果数据不在高速缓存中)，这意味着CPU应该尽快获取指令，计算地址，并从内存 Controller 请求数据。但是，内存 Controller 只能有非常有限数量的未完成请求(通常是两天，但我不确定。)这意味着即使CPU做了非常复杂的事情也可以展望其他内存位置(例如并推断出这些是代码将需要的新数据的地址，由于存储 Controller 只能有这么多的请求待处理，因此它的作用不会太远。
无论如何，AFAIK，我认为CPU尚未真正做到这一点。请注意，这是一个很难的情况，因为您随机分布的内存位置的地址本身就在内存中(而不是在寄存器中或可从寄存器的内容中计算出来)。而且，如果CPU做到了，它就不会由于内存接口(interface)的限制，无论如何都会产生如此大的影响。
您提到的预取技术对我来说似乎是有效的，并且已经使用过，但是只有当您的CPU在等待将来的数据到达时要做一些事情时，它才会产生明显的效果。与从内存中加载12个字节(实际上是加载一个缓存行)相比，增加三个整数所花的时间要少得多，因此，对于执行时间而言，它意义不大。但是，如果您在内存预取的基础上叠加了一些有值(value)的东西和更重量级的东西(例如，计算不需要内存中数据的复杂函数!)，那么您可以获得非常不错的加速比。您会看到，经历以上循环的时间本质上是所有缓存未命中时间的总和。并且您将免费获得坐标增量和循环簿记。因此，如果免费的东西更有值(value)，您将赢得更多!
关于c++ - 现代处理器(如i7)会在遍历指针列表时跟随指针并预取其数据吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15170803/