最快的方式获取内存值数组

Question

在索引结构的核心,我发现自己想知道是否可以针对以下问题进行优化:

我有一个大的(几GB的RAM)小结构数组(在RAM中),我有一个较小的索引数组(大约10e4元素).指数几乎随机分布.我有一个无关紧要的函数(对于数学家来说是"关联的"),比如说"sum".

我想在小数组中指定的索引处聚集从大数组中检索到的值.

目前我花了大部分时间从内存中取出(因为索引是随机扩展的,并且表很大,有很多缓存未命中,但是因为我对索引有所了解,所以应该有一些预取可用).我发现很难分析是否正在进行一些预取优化,或者我可以从这样的优化中获得多少加速？

所以我的问题是,从已知内存位置获取的最快方法是什么.是否有一些黑暗艺术编程魔术呢？是否有一些特定于架构/平台的方法？我正在寻找c ++或c#解决方案.

Answer 1

在不知道关于您的问题或当前实现的任何其他内容的情况下,一种(某种程度上)提高性能(在某种程度上)的简单方法是手动预取"sum"函数将要操作的值.

暂时忽略体系结构和编译器的细微差别,手动预取可能如下所示:

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个字节,这些天)反正,这是非常好的!

因此,而不是试图读取整个values[indices[i]]进v_next,我们就可以读出一个单字节,并假设values数组正确对齐,内存显著量(一个完整的缓存行)将被加载,并在手最终处理.

两个要点:

1. 如果您SmallStruct实际上不是很小并且不完全适合缓存行,则必须重新排列其成员以确保其中所需的部分DoSomethingWith()是连续的并且打包并适合一个缓存行.如果它们仍然不适合,您应该考虑将算法分成两个或更多个通道,每个通道对适合一个缓存行的数据进行操作.
2. 如果您只是从要访问的下一个值读取一个字节(或一个字,或其他任何字节),请确保编译器不会优化读取的值!

替代实施

上面的第二点可以用代码表示,如下所示:

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*,您可以使用特定于编译器的内在函数而不是求助于汇编.这些内在函数适用_mm_prefetch于Microsoft和Intel C++编译器,以及__builtin_prefetchGCC.(如果你最终使用了这个,请记住你想要最低级别的预取,即T0.)

请注意,这些都是touch我上面使用的函数的实现.

我知道没有库以可重用的方式执行此操作.另外,我不熟悉C#库以了解它们是否可用.