“伪共享”凌乱记

发表于 2年以前 | 总阅读数：381 次

本文属于并发编程系列，通过之前的文章我们了解到了CPU中缓存行的概念。简单复习一下就是缓存行是CPU读写缓存的最小单位，一般是64字节。另外当前CPU共有三个级别的缓存，从距离CPU内核的由近及远分为是L1 Cache、L2 Cache、L3 Cache。基于这个背景知识，我今天继续来谈一下和缓存相关的另一大话题：Fasle Sharing！

False Sharing通常称为『伪共享』，也有译作『虚假共享』首先来开宗明义，请注意在『当今』CPU上伪共享是发生在L3 Cache上的。因为L1 Cache和L2 Cache都是片内缓存（每个内核有自己的），L3 Cache在多核之间共享。不过呢，这句话中『当今』一词也很重要，因为在老的CPU上，L2 Cache是多核之间共享的，所以L2 Cache上也会出现伪共享的现象。比如这篇文章：

http://cpp-today.blogspot.com/2008/05/false-sharing-hits-again.htmlcpp-today.blogspot.com

For example consider two threads writing in not overlapping memory locations, they do not need any synchronization so happily you are driven to think that you are able to split your data in order to implement a lock less algorithm. Unfortunately you hold a sparkling "centrino duo" processor in where both cores do share the L2 cache and then the data you partition in memory can be mapped on the same cache line.

这里提到的就是L2 Cache在多核之间共享，不过你可以回头再看一下这篇文章的发表时间：

Saturday, May 31, 2008

已经过去13年啦。所以呢，我们在网上阅读资料的时候需要学会甄别，要意识到技术文章的时效性还是蛮重要的。当然其他部分的讲解大致没什么问题。

另外值得强调的一点是：网上很多讲伪共享的资料都是在O0的优化级别下的默认行为，虽然这样讲伪贡献变得简单了，但其实对于我们实际工作并没有指导意义！因为一开O2很多结论会不一致，所以本文是在开了O2的情况下讨论的。这也是本文的结论显得有些“凌乱”的原因。有些文章是先知道一些结论，然后想办法用代码例子就佐证结论，佐证不出来就再改代码示例……我感觉这同样没有意义，是什么就是什么。

好啦，又是一个偌大的开场白。下面来直奔主题吧。先上一段代码：

#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
const int N = 10000; // vector v 大小
const int M = 2;     // vector sum 大小
void foo(const vector<int>& v, vector<long>& sum, int id) {
    for (int i = 0; i < v.size(); ++i) {
        if (i%M == id) {
            sum[id] += i;
        }
    }
// 在需要开启O2 的时候，一定要对最终结果做一下输出，不然会被当做未使用变量给整段抹掉！
    cout << "sum " << id << " = " << sum[id] << endl;
}
int main () {
    vector<int> v;
    for (int i = 0; i < N; ++i) {
        v.push_back(i);
    }

    {   // 代码块 1
        vector<long> sum(M, 0);
        auto start = chrono::steady_clock::now();
        vector<thread> td;
        for (int i = 0; i < M; ++i) {
            td.emplace_back(foo, std::cref(v), std::ref(sum), i);
        }
        for (int i = 0; i < M; ++i) {
            td[i].join();
        }
        auto end = chrono::steady_clock::now();
        cout<< "block 1 cost:" << chrono::duration_cast<chrono::microseconds>(end - start).count()<<endl;
    }
    cout << "----------" << endl;
    {   // 代码块2
        vector<long> sum(M, 0);
        auto start = chrono::steady_clock::now();
        for (int i = 0; i < M; ++i) {
            foo(v, sum, i);
        }
        auto end = chrono::steady_clock::now();
        cout<< "block 2 cost:" << chrono::duration_cast<chrono::microseconds>(end - start).count()<<endl;
    }
}

有一个初始的vector v，里面存储的是100个从0递增的数字。然后foo()函数实现的就是根据函数的参数来计算这个vector中奇数位元素之和，或者是偶数位函数之和。代码块1 是用多线程并发执行的，代码块2是用普通串行逻辑。

我直接在自己的Macbook上测试吧。虽然不是Linux环境，但是结论基本一致：

clang++ -std=c++11 -pthread -O2 false_sharing.cpp

./a.out

你感觉哪个代码块中逻辑耗时会更少呢？

理论上讲在多核机器上应该是代码块1更快吧。但结果是：

sum 0 = 24995000
sum 1 = 25000000
block 1 cost:318
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:88

多试几次

sum sum 0 = 1 = 24995000
25000000
block 1 cost:286
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:125

（多线程cout，sum0和sum1有时候会打印错乱，但是计算结果都是正确的）

结果大跌眼镜，串行耗时更低。这其中的原因就是False Sharing。如果你读过之前的文章就知道缓存行数CPU操作缓存的最小单位，一个缓存行大小64字节。上面代码中的sum是vector类型，其中存储的是2个连续的long。这两个long是在同一缓存行上的，两个线程分别读写sum[0]、sum[1]的时候，虽然看似是没有使用到同一个变量，但其实互有影响。比如一个线程写入sum[0]的时候，它操作的CPU0中缓存的sum[0]，也会导致CPU1中缓存sum[1]的缓存行失效，从而重新读取，而这是比较耗时的操作。

后来我又尝试改了一下，变成M为8，也就是sum[8]，然后foo函数中进行i%8，最后结果依旧是代码块2耗时更低。

那么要充分利用多核该怎么办呢？针对这个例子，多线程没有操作同一个变量的，只是单个线程内对于同缓存行的变量有大量的读写，这时候可以引入一个局部变量。

新增一个foo2函数：

void foo2(const vector<int>& v, vector<long>& sum, int id) {
    long s = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (i%M == id) {
            s += i;
        }
    }
    sum[id] = s;
    cout << "sum " << id << " = " << sum[id] << endl;
}

main函数中，写一个代码块3：

    {   // 代码块 3
        vector<long> sum(M, 0);
        auto start = chrono::steady_clock::now();
        vector<thread> td;
        for (int i = 0; i < M; ++i) {
            td.emplace_back(foo2, std::cref(v), std::ref(sum), i);
        }
        for (int i = 0; i < M; ++i) {
            td[i].join();
        }
        auto end = chrono::steady_clock::now();
        cout<< "block 3 cost:" << chrono::duration_cast<chrono::microseconds>(end - start).count()<<endl;
    }

最后输出：

sum sum 0 = 1 = 24995000
25000000
block 1 cost:286
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:125
----------
sum 0 = 24995000
sum 1 = 25000000
block 3 cost:121

sum sum 1 = 25000000
0 = 24995000
block 1 cost:402
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:105
----------
sum 0 = 24995000
sum 1 = 25000000
block 3 cost:178

sum sum 1 = 25000000
0 = 24995000
block 1 cost:240
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:95
----------
sum 0 = 24995000
sum 1 = 25000000
block 3 cost:93

sum sum 0 = 24995000
1 = 25000000
block 1 cost:307
----------
sum 0 = 24995000
sum 1 = 25000000
block 2 cost:96
----------
sum 0 = 24995000
sum 1 = 25000000
block 3 cost:117

可以看出代码块3比代码块1已经快了，和代码块2不相伯仲，可能代码块2耗时少的概率更低些，因为代码块3毕竟有线程创建和调度的额外开销在。

我们可以放大数组v的大小，变成1000000（一百万），再执行：

sum 1 = 250000000000
sum 0 = 249999500000
block 1 cost:6318
----------
sum 0 = 249999500000
sum 1 = 250000000000
block 2 cost:9596
----------
sum 0 = 249999500000
sum 1 = 250000000000
block 3 cost:1178

sum 0 = 249999500000
sum 1 = 250000000000
block 1 cost:9474
----------
sum 0 = 249999500000
sum 1 = 250000000000
block 2 cost:9579
----------
sum 0 = 249999500000
sum 1 = 250000000000
block 3 cost:1613

彼时代码块的优势明显，并且有个有趣的现象是，当数组v个数达到一百万的时候，代码块1竟然也比代码块2效率高了……所以关于伪共享，有时候是不能一概而论的，是不是发生了伪共享效率就一定比串行低，不过不论如何第三种方法都是最优解。

前面讲到是基础数据类型，再看一个struct的例子：

#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
const int N = 2;       // vector v 大小
const int T = 1000000;   // 循环的次数
struct Data {
    int a;
    int b;
};
void bar1(Data& d) {
    for (int i = 0; i < T; ++i) {
        d.a++;
    }
    cout<< "d.a:" << d.a << endl;
}
void bar2(Data& d) {
    for (int i = 0; i < T; ++i) {
        d.b++;
    }
    cout<< "d.b:" << d.b << endl;
}

int main () {
    Data d = { 0, 0 };
    auto start = chrono::steady_clock::now();
    thread t1(bar1, std::ref(d));
    thread t2(bar2, std::ref(d));
    t1.join();
    t2.join();
    auto end = chrono::steady_clock::now();
    cout<< "cost:" << chrono::duration_cast<chrono::microseconds>(end - start).count()<<endl;
}

Data类型有两个成员a和b，分别在两个线程内累加1百万次。这次我找了一个有多个核的Linux来编译（这里没有直接开O2 ）：

g++ -std=c++11 -pthread false_sharing2.cpp

运行输出：

d.a:1000000
d.b:1000000
cost:6326

尝试着去掉多线程，改成串行逻辑，结果类似。

下面再介绍一种重发发挥多核CPU优势的方法，如果说第一个例子中使用局部变量，太过局限性，毕竟不是所有线程回调函数的逻辑都能抽象出这么一个局部变量来。那么我们就让两个变量分别处于两个缓存行上！

虽然struct内的字段默认也会有字节对齐，但一般只是和字长对齐，也就是8字节对齐，a和b两个字段还是同一个缓存行中。为此我们要出动gcc扩展语法，让其按照64字节对齐：

__attribute__((aligned(64)))

这是gcc的属性功能。

可以定义一个宏：

#define ALIG __attribute__((aligned(64)))

然后重新定义一个Data：

struct Data {
    int ALIG a;
    int ALIG b;
};

也就是给每个int后面都加上__attribute__((aligned(64))) ，然后a和b就都是64字节了。不信你可以sizeof一下Data，会输出128，当然a和b的sizeof还是4，因为填充的字节不算在字段里面。

顺便再补充一句，如果要做内存对齐的时候，不是每个机器缓存行大小都是64字节。如果你的CPU是三级缓存的，就要看L3缓存行的大小！不是L1 的。没有L3的看L2吧。

好了。我们重新编译执行一下吧。

d.a:1000000
d.b:1000000
cost:3341

耗时已经明显下降，且多次执行比较稳定。之前不加对齐但时候耗时一直会波动，而且比较高。

一般的介绍伪共享的教程在抛出字节对齐之后，基本就结束了，但我还有话要讲。刚才我们没有开O2，开一下

g++ -std=c++11 -pthread -O2 false_sharing2.cpp

不加对齐的代码输出的cost和加了对齐的代码输出的cost不相伯仲，在我用的机器上，两种情况数字都是200多，且没有明显的高低差别。

更神奇的是，如果我去掉多线程的代码，直接串行调用bar1()和bar2()，那么cost是：51！

到这里你明白了吗？所谓的伪共享导致性能变差，真的不是能够一概而论的，在开了O2之后，串行有时候效率最高，这是因为串行代码更容易被编译器和CPU做优化，而多线程代码的被优化能力则没那么强。此时填充字节对齐缓存行大小也不凑效。而在本文第一个代码例子中，展示了v的个数变大时，串行代码会明显变慢。这两个case展示的差异，当然是和具体的执行逻辑有关的。

所以不要把伪共享视作洪水猛兽，也不要把64字节对齐当做灵丹妙药。一切还要要实际测试过才能知道。不要把O0下的结论抛出来，然后奉为圭臬，我认为没有意义

好了，今天就到这了。身为读者的你有没有凌乱呢……