与程序员相关的CPU缓存知识( 四 ) _CPU缓存

示例三接下来，我们再来看个示例。下面是一个二维数组的两种遍历方式，一个逐行遍历，一个是逐列遍历，这两种方式在理论上来说，寻址和计算量都是一样的，执行时间应该也是一样的。
const int row = 1024;const int col = 512int matrix[row][col];//逐行遍历int sum_row=0;for(int r=0; r<row; r++) {for(int c=0; c<col; c++){sum_row += matrix[r];}}//逐列遍历int sum_col=0;for(int c=0; c<col; c++) {for(int r=0; r<row; r++){sum_col += matrix[r];}}然而，并不是，在我的机器上，得到下面的结果。

逐行遍历：0.081ms
逐列遍历：1.069ms

执行时间有十几倍的差距。其中的原因，就是逐列遍历对于CPU Cache 的运作方式并不友好，所以，付出巨大的代价。
示例四接下来，我们来看一下多核下的性能问题，参看如下的代码。两个线程在操作一个数组的两个不同的元素（无需加锁），线程循环1000万次，做加法操作。在下面的代码中，我高亮了一行，就是 p2 指针，要么是 p[1] ，或是 p[18] ，理论上来说，无论访问哪两个数组元素，都应该是一样的执行时间。

void fn (int* data) {for(int i = 0; i < 10*1024*1024; ++i)*data += rand();}int p[32];int *p1 = &p[0];int *p2 = &p[1]; // int *p2 = &p[30];thread t1(fn, p1);thread t2(fn, p2);

然而，并不是，在我的机器上执行下来的结果是：

对于 p[0] 和 p[1] ：560ms
对于 p[0] 和 p[30] ：104ms

这是因为 p[0] 和 p[1] 在同一条 Cache Line 上，而 p[0] 和 p[30] 则不可能在同一条Cache Line 上，CPU的缓冲最小的更新单位是Cache Line，所以，这导致虽然两个线程在写不同的数据，但是因为这两个数据在同一条Cache Line上，就会导致缓存需要不断进在两个CPU的L1/L2中进行同步，从而导致了5倍的时间差异。
示例五接下来，我们再来看一下另外一段代码：我们想统计一下一个数组中的奇数个数，但是这个数组太大了，我们希望可以用多线程来完成，这个统计。下面的代码中，我们为每一个线程传入一个 id ，然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。

int total_size = 16 * 1024 * 1024; //数组长度int* test_data = https://www.isolves.com/it/cxkf/bk/2020-05-05/new test_data[total_size]; //数组int nthread = 6; //线程数（因为我的机器是6核的）int result[nthread]; //收集结果的数组void thread_func (int id) {result[id] = 0;int chunk_size = total_size / nthread + 1;int start = id * chunk_size;int end = min(start + chunk_size, total_size);for ( int i = start; i < end; ++i ) {if (test_data[i] % 2 != 0 ) ++result[id];}}

然而，在执行过程中，你会发现，6个线程居然跑不过1个线程。因为根据上面的例子你知道 result[] 这个数组中的数据在一个Cache Line中，所以，所有的线程都会对这个 Cache Line 进行写操作，导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line，所以，导致 6 个线程还跑不过一个线程的结果。这叫 False Sharing 。
优化也很简单，使用一个线程内的变量。

void thread_func (int id) {result[id] = 0;int chunk_size = total_size / nthread + 1;int start = id * chunk_size;int end = min(start + chunk_size, total_size);int c = 0; //使用临时变量，没有cache line的同步了for ( int i = start; i < end; ++i ) {if (test_data[i] % 2 != 0 ) ++c;}result[id] = c;}

我们把两个程序分别在 1 到 32 个线程上跑一下，得出的结果画一张图如下所示：

文章插图

上图中，我们可以看到，灰色的曲线就是第一种方法，橙色的就是第二种（用局部变量的）方法。当只有一个线程的时候，两个方法相当，而且第二种方法还略差一点，但是在线程数增加的时候的时候，你会发现，第二种方法的性能提高的非常快。直到到达6个线程的时候，开始变得稳定（前面说过，我的CPU是6核的）。而第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是CPU Cache 友好的。

【与程序员相关的CPU缓存知识】