C++多线程独立数据的性能问题

Question

让我们来创建一个非常简单的C++类，它只有一个数据成员：

class Container {
public:
    std::vector<Element> elements;
    Container(int elemCount);
};

现在创建N个线程，它们执行一个非常简单的任务：

1. 创建一个本地容器并设置特定的向量大小
2. 循环遍历该向量并逐个增加每个元素的值
3. 重复步骤2 10,000次（以秒为单位而不是毫秒）

完整的代码清单可以在Pastebin上找到。

根据CoreInfo，我的CPU（Intel Core i5 2400）有4个核心，每个核心都有自己的L1/L2缓存。

Logical to Physical Processor Map:
*---  Physical Processor 0
-*--  Physical Processor 1
--*-  Physical Processor 2

Logical Processor to Cache Map:
*---  Data Cache          0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Instruction Cache   0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Unified Cache       0, Level 2,  256 KB, Assoc   8, LineSize  64
-*--  Data Cache          1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Instruction Cache   1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Unified Cache       1, Level 2,  256 KB, Assoc   8, LineSize  64
--*-  Data Cache          2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Instruction Cache   2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Unified Cache       2, Level 2,  256 KB, Assoc   8, LineSize  64
---*  Data Cache          3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Instruction Cache   3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Unified Cache       3, Level 2,  256 KB, Assoc   8, LineSize  64
****  Unified Cache       4, Level 3,    6 MB, Assoc  12, LineSize  64
---*  Physical Processor 3

对于向量大小最多为100,000个元素，计时与预期完全相符：

Elements count: 100.000

Threads: 1
loops: 10000 ms: 650

Threads: 4
loops: 2500 ms: 168
loops: 2500 ms: 169
loops: 2500 ms: 169
loops: 2500 ms: 171

然而，对于更大的向量尺寸，多核性能表现如下：

Elements count: 300.000

Threads: 1
loops: 10000 ms: 1968

Threads: 4
loops: 2500 ms: 3817
loops: 2500 ms: 3864
loops: 2500 ms: 3927
loops: 2500 ms: 4008

我的问题：

1. 请问有人能向我解释这个原因吗？这是假共享吗？如果是，如果线程不共享任何数据，并且所有核心都有自己的L1/L2高速缓存和缓存行，那么这是怎么可能的？
2. 如果在多个线程中处理独立数据，是否有可能实现（或接近）线性加速效率？

编辑：感谢所有回答。关于您的问题：

@user2079303：Element仅包含一个双精度数据成员。sizeof(Element)=8。请参见Pastebin获取完整源代码。

@bku_drytt：resize()是正确的。我的意图是在每个线程中创建一个包含elemCount元素的向量（无论它们的初始值如何）。

@Jorge González Lorenzo：您在共享的L3缓存方面是绝对正确的。我进行了另一组测试，仅使用单个线程：

Elements count: 50.000
Threads: 1
loops: 50000 ms: 1615

Elements count: 200.000 (4 times bigger)
Threads: 1
loops: 50000 ms: 1615 (slightly more than 4 time bigger)

Elements count: 800.000 (even 4 times bigger)
Threads: 1
loops: 50000 ms: 42181 (MUCH more than 4 time bigger)

- Marcel

---

Element有多大？你记得启用优化编译吗？ - eerorika

你是故意在构造函数中调用 resize() 而不是 reserve() 吗？ - bku_drytt

我的猜测是，你正在使用4个线程（每个线程有一个向量）填充L3共享缓存，从而导致许多缓存未命中，而在单个线程执行中，向量适合缓存。L1和L2是每个核心的专用缓存，但L3不是。公平的比较应该是使用比4个线程执行时大4倍的向量来运行单个线程执行。 - Jorge González Lorenzo

您的 CPU 有 6 MB 的 L3 缓存。100k * 8byte = 0.76MB。乘以 4，即为 3 MB。再乘以 3（300k 元素），即为 9 MB，这已经超出了 L3 缓存的容量。当带宽受限时获得线性加速是不可能的，但如果您实际上正在进行真正的工作，则情况会有所不同。问题在于，所有的“工作”都很容易被单个缓存未命中掩盖（并且与单线程版本相比，您将有 10k * 4 更多的缓存未命中）。 - Voo

@Voo：这似乎真的是答案。在我的原始问题中，我要求解决方案。以下假设是否正确？ 1）确定共享L2 / L3缓存的大小 2）确定适合缓存的元素数量（当然要乘以线程数减去一些保留量） 3）使用多个线程执行计算 4）如果有更多元素需要处理，请从步骤2重复。 - Marcel

这真的取决于你实际的问题和访问模式。并没有一种万能方案适用于每种访问模式（不过，如果符合您的算法，您可能想查找一下“缓存无关算法”，它们非常酷）。如果您真的只是带宽有限，那么聪明地使用线程也无法改变这个事实。 - Voo

Answer 1

你正在使用4个线程填充L3共享缓存（每个线程有一个向量，因此需要x4的存储空间），从而导致许多缓存未命中，而在单线程执行中，向量适合其中。L1和L2是每个核心的，但L3不是。公平比较应该是使用比4个线程执行更大4倍的向量来运行单线程执行。

- Tim B