现代处理器(如i7)是否会跟踪指针并预先获取数据,同时迭代它们的列表？

Question

我想学习如何编写更好的代码,利用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++;
    }
}

这只是一些粗略的模拟代码,为了正确地学习这个,我们只是说所有的位置结构都是在整个堆中随机创建的.

英特尔的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,但是把它扔到这个地方看起来就像是一个丑陋的过早优化.我正在寻找一种方法,我可以下意识地编写缓存效率的代码.

Answer 1

我知道你没有问(也许并不需要对缓存的正确治疗讲道,但我想我反正贡献我的两分钱.需要注意的是这一切只适用于热码.请记住,过早的优化是万恶之源.

正如评论中指出的那样,最好的方法是拥有实际数据的容器.一般来说,平面数据结构比"指针意大利面"更受欢迎,即使您必须复制某些数据和/或为调整数据结构的大小/移动/碎片整理付出代价.

如您所知,平面数据结构(例如数据数组)只有在大多数时间线性和顺序访问它们时才能获得回报.

但这种策略可能并不总是可用.代替实际的线性数据,您可以使用其他策略,例如使用池分配器,并迭代池本身,而不是使用包含指针的向量.这当然有其自身的缺点,可能会有点复杂.

我相信你已经知道了,但是再次提到,从缓存中获取最大收益的最有效技术之一就是拥有更小的数据!在上面的代码中,如果你可以逃避int16_t而不是int32_t,你绝对应该这样做.您应该将许多bools和标志和枚举打包到位字段中,使用索引而不是指针(特别是在64位系统上),在数据结构中使用固定大小的散列值而不是字符串等.

现在,关于你的主要问题是处理器是否可以跟随随机指针并在需要之前将数据带入缓存.在非常有限的程度上,这确实发生了.作为可能是你知道的,现代的CPU采用了很多技巧,以提高他们的速度(即增加他们的指令退休率.)技巧就像有一个存储缓冲区,乱序执行,超标量流水线,每一种的多个功能单元,分支大多数时候,这些技巧都只是帮助CPU 继续执行指令,即使当前指令已经停止或需要很长时间才能完成.对于内存的负载(这是做的,当且仅当数据不在缓存中的最慢的东西),这意味着CPU应该尽快得到指令,计算出地址,并从存储控制器请求数据.然而,内存控制器只能有未完成的请求的数量非常有限(通常有两种这些天,但我不知道).这意味着,即使CPU确实非常复杂的东西,向前看到其他存储位置(例如你的posPointers向量的元素)并推断这些是你的代码将需要的新数据的地址,它不可能走得很远,因为内存控制器只有很多待处理的请求.

在任何情况下,AFAIK,我认为CPU实际上并没有这样做.请注意,这是一个艰难的情况下,因为你的随机分布的存储位置的地址本身在内存中(而不是在寄存器正在或从寄存器中的内容.可计算的),如果CPU的做到了,也不会由于存储器接口的限制,无论如何都会产生很大的影响.

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

Answer 2

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

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

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