多线程循环的效率

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 中定义得很近。

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 is a High Performance Inter-Thread Messaging Library and it's the default messaging system for Intra-worker communication in Apache Storm 底层数据结构是一个简单的环形缓冲区。但是为了让它更快，它使用了很多技巧来减少虚假共享。

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

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

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

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

source

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

Answer 2

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

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

A = B + C;

而vector单元中对应的指令会同时做多次加法：

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

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

您的 for 循环看起来很明显可以使用向量单元；只要 A、B 和 C 的 none 是指向同一数组但具有不同偏移量的指针（这在 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。

多线程循环的效率

Efficiency of Multithreaded Loops

c++

java

performance

multithreading

shared-memory

选项 1：

选项 2：