多线程循环的效率

Question

问候贵族社区，

我想要以下循环：

for(i = 0; i < MAX; i++)
    A[i] = B[i] + C[i];

这将在使用线程的共享内存四核计算机上并行运行。对于这些线程要执行的代码，正在考虑以下两种选择，其中线程tid的ID是：0、1、2或3。

（为简单起见，假设MAX为4的倍数）

选项1：

for(i = tid; i < MAX; i += 4)
    A[i] = B[i] + C[i];

选项2：

for(i = tid*(MAX/4); i < (tid+1)*(MAX/4); i++)
    A[i] = B[i] + C[i];

我的问题是，是否有一种方法比另一种方法更有效，为什么？

Answer 1

第二个比第一个更好。简单的答案：第二个最小化错误共享

现代CPU不会将字节一一加载到缓存中。它在称为缓存行的批处理中读取一次。当两个线程试图修改同一高速缓存行上的不同变量时，一个线程必须在修改一个高速缓存后重新加载它。

什么时候会发生？

基本上，内存中附近的元素将位于同一缓存行中。因此，数组中的相邻元素将位于同一缓存行中，因为数组只是一块内存。并且foo1和foo2可能也位于同一缓存行中，因为它们在同一类中定义为紧密。

class Foo {

private int foo1;
private int foo2;

}

虚假分享有多糟糕？

我从处理器缓存效果库中引用示例6

private static int[] s_counter = new int[1024];
private void UpdateCounter(int position)
{
    for (int j = 0; j < 100000000; j++)
    {
        s_counter[position] = s_counter[position] + 3;
    }
}

在我的四核计算机上，如果我从四个不同的线程中调用带有参数0、1、2、3的UpdateCounter，则需要4.3秒才能完成所有线程。另一方面，如果我使用参数16,32,48,64调用UpdateCounter，则该操作将在0.28秒内完成！

如何检测虚假共享？

Linux Perf可用于检测高速缓存未命中，因此可以帮助您分析此类问题。

请参考来自CPU Cache Effects和Linux Perf的分析，使用perf从上面几乎相同的代码示例中找出L1缓存未命中：

Performance counter stats for './cache_line_test 0 1 2 3':
10,055,747 L1-dcache-load-misses     #    1.54% of all L1-dcache hits

[51.24%]

Performance counter stats for './cache_line_test 16 32 48 64':
  36,992 L1-dcache-load-misses     #    0.01% of all L1-dcache hits   [50.51%]

此处显示，没有错误共享，L1缓存命中的总数将从10,055,747下降至36,992。而且性能开销不在这里，而是在加载L2，L3高速缓存，在错误共享之后加载内存的系列中。

行业中有一些好的做法吗？

LMAX Disruptor是一个高性能线程间消息传递库，它是Apache
Storm中
工作人员内部通信的默认消息传递系统
。基础数据结构是一个简单的环形缓冲区。但是为了使其快速，它使用了许多技巧来减少错误共享。

例如，它定义了超类RingBufferPad以在RingBuffer中的元素之间创建填充：

abstract class RingBufferPad
{
    protected long p1, p2, p3, p4, p5, p6, p7;
}

同样，当它为缓冲区分配内存时，它会在缓冲区的前面和后面创建填充，以便不会受到相邻存储空间中数据的影响：

this.entries   = new Object[sequencer.getBufferSize() + 2 * BUFFER_PAD];

资源

您可能想更多地了解所有魔术。看看作者的其中一篇文章：剖析干扰者：为什么这么快