多线程循环的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不会将字节逐个加载到缓存中。它在称为缓存线的批处理中读取一次。当两个线程试图修改同一缓存线上的不同变量时，必须在修改缓存后重新加载缓存

什么时候会发生这种情况

基本上，内存中附近的元素将位于同一缓存线中。所以，数组中的相邻元素将位于同一缓存线中，因为数组只是一块内存。而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!

如何检测虚假共享

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

参考CPU Cache Effects and Linux Perf中的分析，使用perf从上面几乎相同的代码示例中查找一级缓存未命中：

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缓存命中总数将从10055747下降到36992。性能开销并不在这里，而是在加载二级、三级缓存、在错误共享后加载内存的过程中

行业中是否有一些好的做法

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

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

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

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

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

source

你可能想了解更多关于所有魔术的知识。看看作者的一篇帖子：Dissecting the Disruptor: Why it's so fast

Answer 2

有两个不同的原因让您更喜欢选项2而不是选项1。其中之一是缓存位置/缓存争用，如@qqibrow的回答所述；我不会在这里解释，因为已经有一个很好的答案来解释它

另一个原因是矢量化。大多数高端现代处理器都有向量单元，能够在多个不同的数据上同时运行相同的指令（特别是，如果处理器有多个核，那么几乎可以肯定每个核上都有一个向量单元，甚至可能有多个向量单元）。例如，在没有矢量单元的情况下，处理器具有执行加法的指令：

A = B + C;

向量单元中的相应指令将同时执行多个加法：

A1 = B1 + C1;
A2 = B2 + C2;
A3 = B3 + C3;
A4 = B4 + C4;

（加法的确切数量因处理器型号而异；在int上，常见的“向量宽度”包括4和8个同时加法，最近的一些处理器可以同时进行16个加法。）

你的for循环看起来很适合使用向量单元；只要^ {< CD3>}、^ { CD4>}和^ {CD5>}都指向同一个数组，但用不同的偏移（在C++中，但不是java），编译器将允许优化选项2到

for(i = tid*(MAX/4); i < (tid+1)*(MAX/4); i+=4) {
    A[i+0] = B[i+0] + C[i+0];
    A[i+1] = B[i+1] + C[i+1];
    A[i+2] = B[i+2] + C[i+2];
    A[i+3] = B[i+3] + C[i+3];
}

然而，向量单元的一个限制与内存访问有关：向量单元只有在访问相邻位置（例如数组中的相邻元素或Cstruct的相邻字段）时，才能够快速访问内存。上面的选项2代码几乎是代码矢量化的最佳情况：矢量单元可以作为单个块从每个阵列访问它需要的所有元素。如果您尝试对选项1代码进行矢量化，那么矢量单元将花费很长时间在内存中查找它正在处理的所有值，矢量化的收益将被抵消；它的运行速度不太可能比非矢量化代码快，因为内存访问速度不会更快，而且通过比较，加法不需要时间（因为处理器可以在等待来自内存的值到达时进行加法）

虽然不能保证编译器能够使用向量单元，但使用选项2比使用选项1更有可能做到这一点。因此，如果只考虑缓存效应，您可能会发现选项2比选项1的优势比您预期的多4/8/16倍