通过已知索引重新调整,聚集,分散对数组进行缓存友好复制

假设我们有一个数据数组和另一个带索引的数组.

data = [1, 2, 3, 4, 5, 7]
index = [5, 1, 4, 0, 2, 3]

我们想要从data位置的元素创建一个新的数组index.结果应该是

[4, 2, 5, 7, 3, 1]

朴素算法适用于O(N),但它执行随机存储器访问.

你能建议具有相同复杂性的CPU缓存友好算法吗？

PS在我的特定情况下,数据数组中的所有元素都是整数.

PPS阵列可能包含数百万个元素.

PPPS我可以使用SSE/AVX或任何其他x64特定的优化

将索引和数据合并到一个数组中.然后使用一些缓存友好的排序算法对这些对进行排序(按索引).然后摆脱索引.(您可以将合并/删除索引与排序算法的第一个/最后一个通道相结合,以稍微优化一下).

对于缓存友好的O(N)排序,使用足够小的基数排序radix(CPU缓存中最多一半的缓存行).

这是类似基数排序算法的C实现:

void reorder2(const unsigned size)
{
    const unsigned min_bucket = size / kRadix;
    const unsigned large_buckets = size % kRadix;
    g_counters[0] = 0;

    for (unsigned i = 1; i <= large_buckets; ++i)
        g_counters[i] = g_counters[i - 1] + min_bucket + 1;

    for (unsigned i = large_buckets + 1; i < kRadix; ++i)
        g_counters[i] = g_counters[i - 1] + min_bucket;

    for (unsigned i = 0; i < size; ++i)
    {
        const unsigned dst = g_counters[g_index[i] % kRadix]++;
        g_sort[dst].index = g_index[i] / kRadix;
        g_sort[dst].value = g_input[i];
        __builtin_prefetch(&g_sort[dst + 1].value, 1);
    }

    g_counters[0] = 0;

    for (unsigned i = 1; i < (size + kRadix - 1) / kRadix; ++i)
        g_counters[i] = g_counters[i - 1] + kRadix;

    for (unsigned i = 0; i < size; ++i)
    {
        const unsigned dst = g_counters[g_sort[i].index]++;
        g_output[dst] = g_sort[i].value;
        __builtin_prefetch(&g_output[dst + 1], 1);
    }
}

它在两个方面与基数排序不同:(1)它不进行计数通过,因为所有计数器都是预先知道的; (2)它避免使用2的幂值作为基数.

这个C++代码用于基准测试(如果你想在32位系统上运行它,稍微减少kMaxSize常量).

以下是基准测试结果(在具有6Mb高速缓存的Haswell CPU上):

很容易看出小阵列(低于~2 000 000个元素)即使对于朴素算法也是缓存友好的.此外,您可能会注意到排序方法在图表的最后一点开始对缓存不友好(size/radix在L3缓存中具有接近0.75的缓存行).在这些限制之间,排序方法比朴素算法更有效.

理论上(如果我们只比较这些算法所需的内存带宽与64字节高速缓存行和4字节值),排序算法应该快3倍.在实践中,我们的差异要小得多,约为20%.如果我们对data数组使用较小的16位值(在这种情况下排序算法快约1.5倍),这可以得到改善.

排序方法的另一个问题是当size/radix接近某个2的幂时它的最坏情况行为.这可以被忽略(因为没有那么多"坏"大小)或通过使这个算法稍微复杂来修复.

如果我们将传递次数增加到3,则所有3次传递主要使用L1缓存,但内存带宽增加60%.我用这段代码得到实验结果:TL; DR.在确定(实验性地)最佳基数值后,对于大于4 000 000的大小(其中2遍算法使用L3缓存进行一次通过),我获得了更好的结果,但是对于较小的阵列(其中2遍算法使用L2)的结果稍差缓存两个通道).正如可能预期的那样,16位数据的性能更好.

结论:性能差异远小于算法复杂度的差异,因此天真的方法几乎总是更好; 如果性能非常重要并且仅使用2或4个字节值,则排序方法更可取.

data = [1, 2, 3, 4, 5, 7]

index = [5, 1, 4, 0, 2, 3]

我们想要从索引位置的数据元素创建一个新数组.结果应该是

result -> [4, 2, 5, 7, 3, 1]

单线程,一次通过

我认为,对于几百万个元素和单个线程,天真的方法可能是最好的.

既data和index被访问(读)顺序,这已经是最适合于CPU的高速缓存.这留下了随机写入,但写入内存并不像读取它那样缓存友好.

这只需要一次顺序传递数据和索引.并且有些(有时很多)写入的机会也已经是缓存友好的.

使用多个块result- 多个线程

我们可以分配或使用缓存友好大小的块的结果(块是在各地区result array),并通过循环index和data多次(而他们留在缓存).

在每一个循环中,我们然后只写元件,以result该当前结果块配合.对于写入来说这也是"缓存友好",但是需要多个循环(循环的数量甚至可以变得相当高 - 即size of data / size of result-block).

当使用多个线程时,上面的选项可能是一个选项:data并且index,只读,将由缓存中某个级别的所有内核共享(取决于缓存架构).result每个线程中的块将是完全独立的(一个核心永远不必等待另一个核心的结果,或者在同一区域中写入).例如:1000万个元素 - 每个线程可以处理500.000个元素的独立结果块(数字应该是2的幂).

将值组合成一对并首先对它们进行排序:这将比naive选项花费更多的时间(并且也不会对缓存友好).

而且,如果只有几百万个元素(整数),它就不会产生太大的影响.如果我们要谈论数十亿或者不适合内存的数据,其他策略可能更可取(例如,如果结果集不适合内存,则将结果集映射到内存中).