我有一个大的(几GB的RAM)数组的小结构(在RAM中),我有一个较小的索引数组(大约10e4个元素).指数几乎随机扩散.我有一个独立的秩序(对于数学家来说是“联想的”),例如“总和”.
我想收集从小数组中指定的索引从大数组中检索的值.
目前,我花费大部分时间从内存中获取(由于索引是随机扩展的,而且表格很大,所以存在很多缓存未命中,但是由于我对索引的了解应该有一些可用的预取).我发现很难确定一些预取优化是否正在进行,或者我可以从这样的优化中获得多少加速？
所以我的问题是,从已知的内存位置获取最快的方法是什么.有没有一些黑暗的编程魔法呢？有没有一些架构/平台具体的方法呢？我正在寻找c或c#解决方案.
解决方法
现在忽略了架构和编译器的细微差别,手动预取可能如下所示：
SmallStruct values [value_count] = {/*whatever*/};
int indices [index_count] = {/*whatever*/};
...
SmallStruct v = values[indices[0]];
for (int i = 1; i < index_count; ++i)
{
SmallStruct v_next = values[indices[i]];
DoSomethingWith (v); // Note the *v*
v = v_next; // You don't want to copy,but this is the simplest form
}
DoSomethingWith (v); // Do the final item
以上是最简单的预取形式.您可以展开循环一点,以避免上面提到的复制,也可能希望做一个以上的单独的预取.
这种优化是有效的,因为大多数(所有的)现代架构可以在飞行中具有多个存储器请求,这意味着这些请求是重叠的,并且那些(大概是未被缓存的)请求的平均等待时间被它们的并发划分(这是一个很好的事情！)所以,你有多少未使用的缓存行是不关键的重要的因素是内存系统在任何给定时间可以持续的并发内存读取的数量.
关于缓存线的影响的注释
上述(毫无疑问的简单)代码忽略了两个非常重要的事实：整个SmallStruct不能在一个内存访问(从cpu的角度)读取,这是一件坏事,而且内存总是以缓存行为单位读取(64或128字节,这些天)反正这是非常好的！
因此,我们可以读取一个单字节,而不是将整个值[indices [i]]读入v_next,而是假设值数组正确对齐,将加载大量内存(一个完整的高速缓存行)并在手边进行最终处理.
两个重点：
>如果您的SmallStruct实际上并不完全符合缓存行,则必须对其成员进行重新排列,以确保其在DoSomethingWith()中所需的部分是连续的并打包并适合一个缓存行.如果仍然不适合,您应该考虑将算法分成两个或更多个遍,每个通过操作符合一个缓存行中的数据.
>如果您只是从下一个值中读取一个字节(或一个字,或任何一个),请确保编译器不会优化该读取！
替代实施
上面的第二点可以用代码表示,如下所示：
touch (&values[indices[0]]);
for (int i = 0; i < index_count; ++i)
{
if (i + 1 < index_count)
touch (&values[indices[i + 1]]);
DoSomethingWith (values[indices[i]]);
}
touch()函数在语义上是这样的(虽然实现可能会更多地涉及到)
void touch (void * p)
{
char c = *(char *)p;
}
要预取多个值,您可以执行以下操作：(更新：我将代码更改为(我相信)更好的实现.)
const int PrefetchCount = 3;
// Get the ball rolling...
for (int j = 0; j < PrefetchCount; ++j)
touch (&values[indices[j]]);
for (int i = 0; i < index_count; ++i)
{
if (i + PrefetchCount < index_count)
touch (&values[indices[i + PrefetchCount]]);
DoSomethingWith (values[indices[i]]);
}
再次注意,上述所有实现都非常简单和简单.此外,如果您预取的太多,您可以吹一下L1缓存和您的表现.
进行实际预取
x86-64 cpu有一条指令,用于要求cpu将高速缓存行内存数据预取到缓存中.实际上,使用这条指令,您可以向cpu提示该应用程序将使用该特定内存位置,并且cpu将尝试将其带入缓存.如果您足够快,数据将在您需要时准备就绪,您的计算不会停顿.
该指令是PREFETCH *,您可以使用编译器特定的内在函数,而不是使用汇编.这些内在函数在Microsoft和Intel C编译器中被称为_mm_prefetch,在GCC上称为__builtin_prefetch. (如果你最终使用这个,只要记住你想要最低级别的预取,即T0.)
请注意,这些进入我上面使用的触摸功能的实现.
我知道没有一个可重复使用的图书馆.此外,我不熟悉C#库以了解这些是否可用.
