java - 多线程循环的效率

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

第二个比第一个好。简单答案:第二个最小化 false sharing

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

这会在什么时候发生？

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

class Foo {

private int foo1;
private int foo2;

}

虚假分享有多糟糕？

我引用了 Gallery of Processor Cache Effects 中的示例 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;
    }
}

On my quad-core machine, if I call UpdateCounter with parameters 0,1,2,3 from four different threads, it will take 4.3 seconds until all threads are done. On the other hand, if I call UpdateCounter with parameters 16,32,48,64 the operation will be done in 0.28 seconds!

如何检测虚假分享？

Linux Perf 可用于检测缓存未命中，从而帮助您分析此类问题。

引用CPU Cache Effects and 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缓存、false sharing后加载内存这一系列。

工业界有什么好的做法吗？

LMAX Disruptor是一个高性能的线程间消息传递库，它是 Apache Storm 中用于内部工作通信的默认消息传递系统。底层数据结构是一个简单的环形缓冲区。但是为了让它更快，它使用了很多技巧来减少虚假共享。

例如，它定义了父类(super class)RingBufferPad在 RingBuffer 中的元素之间创建填充:

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

此外，当它为缓冲区分配内存时，它会在前面和尾部创建填充，这样它就不会受到相邻内存空间中数据的影响:

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

source

您可能想了解更多有关所有魔术的信息。看看作者的帖子之一:Dissecting the Disruptor: Why it's so fast