多线程循环的效率

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也可能位于同一个缓存行中,因为它们在同一个类中定义为close.

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];

资源

你可能想要了解更多关于所有魔术的技巧.看一下作者的帖子:解剖干扰器:为什么它如此之快

Answer 2

有两个不同的原因可以解释为什么您应该选择选项 2 而不是选项 1。其中之一是缓存局部性/缓存争用，如 @qqibrow 的回答中所述；我不会在这里解释，因为已经有一个很好的答案解释了。

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

A = B + C;

而向量单元中对应的指令会同时进行多次加法：

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

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

您的for循环看起来像是使用向量单元的明显候选者；只要A、B、 和都不C是指向同一数组但具有不同偏移量的指针（这在 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];
}

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

不能保证编译器能够使用向量单元，但使用选项 2 比选项 1 更有可能使用向量单元。因此，您可能会发现选项 2 相对于选项 1 的优势是一个因素如果仅考虑缓存影响，则比您预期的要多 4/8/16。