12

我想学习如何编写更好的代码来利用 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 结构都是在整个堆中随机创建的。

英特尔 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，但是到处乱扔似乎是一个丑陋的过早优化。我正在寻找一种可以下意识地编写缓存高效代码的方法。

4

2 回答 2

6

我知道你没有问（并且可能不需要关于正确处理缓存的布道，但我认为无论如何我都会贡献我的两分钱。请注意，所有这些仅适用于热代码。请记住，过早的优化是万恶之根。

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

如您所知，扁平数据结构（例如，数据数组）只有在大多数情况下以线性顺序访问它们时才会得到回报。

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

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

现在，关于您的主要问题，即处理器是否可以跟随随机指针并在需要之前将数据带入缓存。在非常有限的程度上，这确实发生了。您可能知道，现代 CPU 采用了许多技巧来提高它们的速度（即提高它们的指令退休率）。诸如拥有存储缓冲区、乱序执行、超标量管道、各种功能单元、分支等技巧预测等。大多数时候，这些技巧都只是帮助 CPU继续执行指令，即使当前指令已停止或完成时间过长。对于内存加载（这是最慢的事情，如果数据不在缓存中），这意味着 CPU 应该尽快获取指令，计算地址，并从内存控制器请求数据。但是，内存控制器只能处理非常有限数量的未完成请求（现在通常是两个，但我不确定。）这意味着即使 CPU 做了非常复杂的事情来提前查看其他内存位置（例如你的向量的元素posPointers）并推断这些是你的代码将需要的新数据的地址，它不能走得太远，因为内存控制器只能有这么多的请求待处理。

无论如何，AFAIK，我认为 CPU 还没有真正做到这一点。请注意，这是一个困难的情况，因为随机分布的内存位置的地址本身就在内存中（而不是在寄存器中或可以从寄存器的内容中计算出来。）如果 CPU 做到了，它就不会由于内存接口的限制，无论如何都会产生很大的影响。

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

于 2013-03-02T18:42:57.983 回答
4

现代处理器具有硬件预取机制：英特尔硬件预取器。他们推断内存的跨步访问模式并预取可能在不久的将来访问的内存位置。

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

您可以做的最好的事情是尝试以更有可能访问内存的连续部分的方式组织内存中的数据结构。

于 2013-03-02T05:00:35.470 回答