通过已知索引、收集、分散重新调整的数组缓存友好复制

Question

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

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

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

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

朴素算法适用于 O(N)，但它执行随机内存访问。

你能推荐具有相同复杂度的 CPU 缓存友好算法吗？

附言在我的特定情况下，数据数组中的所有元素都是整数。

公务员事务局数组可能包含数百万个元素。

PPPS 我接受 SSE/AVX 或任何其他 x64 特定优化

Answer 1

将索引和数据合并到一个数组中。然后使用一些缓存友好的排序算法对这些对进行排序(按索引)。然后摆脱索引。 (您可以将合并/删除索引与排序算法的第一遍/最后一遍结合起来对此进行一点优化)。

对于缓存友好的 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次方值。

This C++ code was used for benchmarking (如果你想在 32 位系统上运行它，稍微减小 kMaxSize 常量)。

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

很容易看出小型数组(少于 200 万个元素)即使对于朴素算法也是缓存友好的。此外，您可能会注意到排序方法在图表的最后一点开始对缓存不友好(size/radix 在 L3 缓存中接近 0.75 缓存行)。在这些限制之间，排序方法比朴素算法更有效。

理论上(如果我们仅将这些算法所需的内存带宽与 64 字节缓存行和 4 字节值进行比较)排序算法应该快 3 倍。实际上，我们的差异要小得多，大约 20%。如果我们为 data 数组使用更小的 16 位值(在这种情况下，排序算法大约快 1.5 倍)，这可能会有所改善。

排序方法的另一个问题是当 size/radix 接近某个 2 的幂时它的最坏情况行为。这可能会被忽略(因为没有那么多“坏”尺寸)或通过使该算法稍微复杂一些来解决。

如果我们将 channel 数增加到 3，则所有 3 个 channel 主要使用 L1 缓存，但内存带宽增加了 60%。我用这段代码得到了实验结果:TL; DR .在(通过实验)确定最佳基数值后，对于大于 4 000 000 的大小(其中 2-pass 算法使用 L3 缓存一次)我得到了更好的结果，但对于较小的数组(其中 2-pass 算法使用 L2缓存两次)。正如预期的那样，16 位数据的性能更好。

结论:性能差异远小于算法复杂度差异，因此朴素方法几乎总是更好；如果性能非常重要并且只使用 2 或 4 字节值，则排序方法更可取。