问通过已知索引、聚集、散布进行重新调整的数组的高速缓存友好复制

EN

将索引和数据合并到单个数组中。然后使用一些缓存友好的排序算法对这些对进行排序(按索引)。然后去掉索引。(您可以将合并/删除索引与排序算法的第一次/最后一次传递结合起来，以稍微优化这一点)。

对于高速缓存友好的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上)：

​

​

很容易看出，即使对于朴素算法，小数组(小于2,000,000个元素)也是缓存友好的。此外，您可能会注意到，排序方法在图表的最后一点开始对缓存不友好(在L3缓存中，size/radix接近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字节值，则排序方法更可取。

如果您的问题处理的数据比这里显示的多得多，那么最快的方法-可能也是对缓存最友好的方法-将是执行一个大范围的合并排序操作。

因此，您可以将输入数据划分为合理的块，并让单独的线程对每个块进行操作。此操作的结果将是两个与输入非常相似的数组(一个数据索引和一个目标索引)，但是索引将被排序。然后，让最后一个线程将数据合并到最终的输出数组中。

只要选择了正确的段，这应该是一个非常适合缓存的算法。我的意思是，不同线程使用的数据映射到(您选择的处理器)不同的缓存线上，以避免缓存颠簸。

我注意到你的索引完全覆盖了这个域，但是是随机排列的。

如果要对索引进行排序，但也要对索引数组和数据数组应用相同的操作，则数据数组将成为您想要的结果。

有许多排序算法可供选择，所有算法都将满足您的缓存友好标准。但它们的复杂性各不相同。我会考虑快速排序或合并排序。

如果你对这个答案感兴趣，我可以用伪代码来详细说明。