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

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

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缓存友好算法吗?

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

PPSarrays可能包含数百万个元素。

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上):

基准结果

很容易看出小arrays(低于~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缓存进行一次通过),我获得了更好的结果,但是对于较小的arrays(其中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]

单线程,一次通过

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

dataindex都是按顺序访问(读取)的,这对于CPU缓存来说已经是最佳的。 这留下了随机写入,但写入内存并不像读取它那样缓存友好。

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

使用多个块作为result – 多个线程

我们可以为结果分配或使用缓存友好大小的块(块是result array区域),并多次循环indexdata (当它们保留在缓存中时)。

在每个循环中,我们只将元素写入适合当前结果块的结果 。 对于写入来说这也是“缓存友好”,但是需要多个循环(循环的数量甚至可以变得相当高 – 即size of data / size of result-block )。

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


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

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

如果您的问题处理的数据多于您在此处显示的数据,那么最快的方法 – 可能是缓存最友好的 – 将是进行大型和广泛的合并排序操作。

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

只要选择好的段,这应该是一个非常缓存友好的算法。 明智地,我的意思是,不同线程使用的数据映射到(所选处理器的)不同缓存行上,以避免缓存抖动。

如果您有大量数据并且确实是瓶颈,则需要使用基于块的算法,您可以尽可能地从相同的块读取和写入。 最多需要2遍数据才能确保新数组完全填充,并且需要适当设置块大小。 伪代码在下面。

 def populate(index,data,newArray,cache) blockSize = 1000 for i = 0; i < size(index); i++ //We cached this value earlier if i in cache newArray[i] = cache[i] remove(cache,i) else newIndex = index[i] newValue = data[i] //Check if this index is in our block if i%blockSize != newIndex%blockSize //This index is not in our current block, cache it cache[newIndex] = newValue else //This value is in our current block newArray[newIndex] = newValue cache = {} newArray = [] populate(index,data,newArray,cache) populate(index,data,newArray,cache) 

分析

朴素的解决方案按顺序访问索引和数据数组,但是以随机顺序访问新数组。 由于新数组是随机访问的,因此基本上以O(N ^ 2)结束,其中N是数组中的块数。

基于块的解决方案不会从一个块跳到另一个块。 它按顺序读取索引,数据和新数组,以读取和写入相同的块。 如果索引将位于另一个块中,则会对其进行高速缓存,并在其所属的块出现时进行检索,或者如果已经传递了该块,则将在第二次传递中检索该索引。 第二遍不会受到伤害。 这是O(N)。

唯一需要注意的是处理缓存。 这里有很多创造机会的机会,但一般来说,如果很多读写操作最终都在不同的块上,那么缓存就会增长,这不是最佳选择。 这取决于数据的构成,这种情况发生的频率以及缓存实现。

让我们想象一下,缓存中的所有信息都存在于一个块中,并且它适合内存。 并且假设缓存有y个元素。 天真的方法至少可以随机访问y次。 基于块的方法将在第二遍中获得。

我注意到你的索引完全涵盖了域,但是是随机顺序。

如果您要对索引进行排序,但也将相同的操作应用于索引数组到数据数组,那么数据数组将成为您所追求的结果。

有很多种类算法可供选择,所有这些都可以满足你的缓存友好标准。 但它们的复杂性各不相 我会考虑快速排序或合并排序。

如果您对此答案感兴趣,我可以使用伪代码进行详细说明。

我担心这可能不是一个成功的模式。

我们有一段表现良好的代码,我们通过删除副本来优化它。

结果是它表现不佳(由于缓存问题)。 我看不出你如何能够产生一个解决问题的单程算法。 使用OpenMP,可能允许这将导致在多个线程之间共享的停顿。

我假设重新排序只以同样的方式发生一次。 如果它多次发生,那么事先创建一些更好的策略(通过适当的排序算法)将提高性能

我编写了以下程序来实际测试N块中目标的简单拆分是否有帮助,我的发现是:

a)即使在最坏的情况下,单线程性能(使用分段写入)也不可能超过天真策略,并且通常至少比2倍更差

b)但是,某些细分(可能取决于处理器)和数组大小的性能接近统一,从而表明它实际上会改善多核性能

这样做的结果是:是的,它比不进行细分更“缓存友好”,但对于单个线程(并且只有一个重新排序),这不会对你有所帮助。

 #include  #include  #include  void main(char **ARGS,int ARGC) { int N=1<<26; double* source = malloc(N*sizeof(double)); double* target = malloc(N*sizeof(double)); int* idx = malloc(N*sizeof(double)); int i; for(i=0;i>M) == j) { target[k]=source[i]; }; }; }; gettimeofday(&then,NULL); printf("%d,%f\n",targetblocks,(0.0+then.tv_sec*1e6+then.tv_usec-now.tv_sec*1e6-now.tv_usec)/N); };