多线程中伪共享问题

2021-02-20

字数统计: 1.3k字 | 阅读时长≈ 5分

多线程编程中，对共享数据进行读写需要加锁保护，临界区的存在使得多个线程无法并行，性能下降。还有一种性能损害较大的问题就是伪共享问题。

因为根据局部性原理(CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中), 我们知道了存储器都是分层的。从距离 CPU 最近的寄存器到主内存，依次为 CPU 寄存器、 L1 Cache 、 L2 Cache 、 L3 Cache 和主存。从高层往底层走，存储设备变得更慢，容量更大，单位字节也更便宜。最高层是很少量的寄存器，通常可以在 1 个时钟周期内访问它们，而接下来的 L1 Cache 通常可以在 4 个时钟周期内访问到， L2 Cache 通常需要 10 个时钟周期才能访问到，而到了主存，通常需要几百个时钟周
期才能访问得到。
更快更小的存储设备的数据来自更慢更大的低一级存储设备。访问的数据在高速缓存中，被称为缓存命中，这种情况下访问速度比较快。如果访问的数据 d 在 k 级缓存中不存在，就不得不从 k+1 级中取出包含 d 的那个块 (block)。缓存不命中对性能的损失是很大的。
在典型的多核架构中，每个 CPU 都有自己的 Cache 。如果一个内存中的变量在多个 CPU Cache 中都有副本，则需要保证变量的 Cache 的一致性。
CPU Cache 是以缓存行（ Cache line ）为单位进行读写的。通常来说，一条缓存行的大小为 64 字节。换言之，就是访问 1 字节的数据，系统也会将该字节所在的整条缓存行的数据都搬到缓存中。

考虑以下代码：

int sum1;
int sum2;
void thread1(int v[], int v_count) {sum1 = 0;for (int i = 0; i < v_count; i++) sum1 += v[i];
}
void thread2(int v[], int v_count) { sum2 = 0; for (int i = 0; i < v_count; i++) sum2 += v[i];
}

这部分代码定义了两个全局变量 sum1 和 sum2 ，两个线程分别将计算结果放入各自的全局变量中，看起来并行不悖。但是由于这两个全局变量紧挨着定义，编译器给这两个变量分配的内存几乎总是紧挨着的，因此这两个变量很可能在同一条 Cache line 中。
尽管线程 1 所在的 CPU 并不需要 sum2 的值，但是由于 sum2 和 sum1 在同一条 Cache line 中，因此 sum2 的值也随同 sum1 一并被加载到了 thread1 所在 CPU 的 Cache 中了。
当 thread1 修改 sum1 的值时，尽管并未更新 sum2 的值，但影响的是整条 Cache line ，它会将 thread2 所在 CPU 对应的 Cache line 置为 Invalidate 。如果 thread2 尝试更新 sum2 ，会触发缓存不命中。反过来， thread2 修改 sum2 时，也会影响到 sum1 的缓存命中。

来看一段实例：

#include <stdlib.h>
#include <stdio.h>
#include <thread>

#define NR_THREAD 4
static long num_rect = 400000000;

typedef struct sum_struct {
    double sum ;
    // char padding[56];
} sum_struct;
struct sum_struct __sum[NR_THREAD];

void calc_pi(int index)
{
    double mid = 0.0;
    double height = 0.0;
    double width = 1.0/((double)num_rect);
    int cur = index;
    for(; cur < num_rect; cur += NR_THREAD)
    {
        mid = (cur+0.5)*width;
        height = 4.0/(1 + mid*mid);
        __sum[index].sum += height;
    }
    __sum[index].sum *= width;
}

int main()
{
    int i = 0;
    double result = 0.0;
    std::thread tid[NR_THREAD];
    printf("the size of struct sum_struct = %ld\n",sizeof(struct sum_struct));
    for( i = 0 ; i < NR_THREAD; i++)
    {
        __sum[i].sum = 0.0;
        tid[i] = std::thread(calc_pi, i);
    }
    for( i = 0; i < NR_THREAD ; i++)
    {
        tid[i].join();
        result += __sum[i].sum;
    }
    printf("the PI = %.32f\n",result);
    return 0;
}

$$\pi = \int_{0}^{1}\frac{4}{1 + x^2} dx $$
上述例子是用多线程计算pi,采用的方法是上述数值积分法的公式。
因为每个线程都要负责往 __sum 对应的位置更新结果。因此这个数组很容易触发前面提到的伪共享陷阱。当 sum_struct 结构体没有填充字符时，该结构体占据 8 字节，当 8 个线程并发时， __sum 数组很可能在同一个 Cache line 中，这时候性能必然会受到影响。为了避开伪共享这个陷阱，测试程序采用了加填充字节的方法。如果给 sum_struct 结构体加上 56 个填充字节，每个 sum_struct 占据 1 条 Cache line 的大小，则可以确保它们之间不会互相影响。测试时间如下：
| | real time | user time | sys time |
| —— | —— | —— | —— |
| 单线程 | 0m11.006s | 0m11.000s | 0m0.005s |
| 4线程(无padding) | 0m7.055s | 0m26.849s | 0m0.151s |
| 4线程(padding 56B) | 0m3.206s | 0m11.831s | 0m0.181s |

可以看出，如果不加 56 字节的填充，由于伪共享引起的大量缓存不命中， 4 个线程并没有带来 4 倍的效率提升。通过填充字节解决了伪共享的问题之后，效率线性地提升了 4 倍。

参考：
《Linux环境编程：从应用到内核》

本文作者： JiXiaw
本文链接： http://jixiaw.github.io/2021/02/20/false_sharing/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！