1. Cache 基础知识
   目前，一般的CPU会有三级内存（L1，L2，L3 ），如下图所示。
   

其中：

• L1 缓存分成两种，一种是指令缓存，另一种是数据缓存。L2 和 L3 缓存不分指令和数据。
• L1 和 L2 缓存在每一个 CPU 核中，L3 则是所有 CPU 核心共享的内存。
• L1、L2、L3 的离CPU越近速度越快，但也越小；离 CPU越 远速度越慢，也越大。

再往后就是内存，内存的后面就是硬盘。
存取速度如下:

• L1 的存取速度：4 个CPU时钟周期
• L2 的存取速度：11 个CPU时钟周期
• L3 的存取速度：39 个CPU时钟周期
• RAM内存的存取速度 ：107 个CPU时钟周期

建立这么多级的缓存，会引入2个比较重要的问题:

• 一是缓存命中率问题
• 二是缓存更新的一致性问题
  尤其是第二个问题，在多核技术下，就很像分布式的系统，要对多个地方进行更新。

例如：Intel Core i7-8700K ，是一个 6 核的 CPU，每核上的 L1 是 64KB（数据和指令各 32KB），L2 是 256K，L3 有 2MB

2. 术语： Cache Line

CPU每次加载一块数据，这就是 cache line.
主流的 CPU 的 Cache Line 是 64 Bytes（也有的CPU用 32 和 128 Bytes），这就是 CPU 从内存中捞数据上来的最小数据单位。

因为Cache Line是最小单位（64Bytes），所以先把 Cache 分布多个 Cache Line，比如：L1 有 32KB，那么，32KB/64B = 512 个 Cache Line。

3. 缓存的一致性 与 False Sharing

如果有一个数据 x 在 CPU 第 0 核的缓存上被更新了，那么其它 CPU 核上对于这个数据 x 的值也要被更新，这就是缓存一致性的问题。（这对上层的代码是透明的）

来看一个程序。在这个程序中，有一个数组，拥有 16M 个元素，每个元素的值都是随机的。我们用这个程序来统计整个数组包含多少个奇数。
程序中总共列了3种方法，并统计了每种方法的执行时间。具体如下：

#include <chrono>
#include <iostream>
#include <thread>
#include <vector>
using namespace std;


const int total_size = 16*1024*1024;
int * test_data = new int [total_size];

const int thread_num = 6; 
int result[thread_num];

void thread_func_for_multi_thread(int id) {
    result[id] = 0;
    int chunk_size = total_size / thread_num + 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) result[id] ++;
    }
}

void thread_func_for_multi_thread_improved(int id) {
    int count = 0;
    int chunk_size = total_size / thread_num + 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) count ++;
    }
    result[id] = count;
}

void thread_func_for_one_thread() {
    int count = 0;
    for (int i=0; i<total_size; i++) {
        if (test_data[i] % 2) count ++;
    }
    cout << "One thread: count = " << count << endl;
}

void test() {
    // init test_data array 
    for (int i=0; i<total_size; i++) test_data[i] = rand();
    for (int i=0; i<thread_num; i++) result[i] = 0;
    
    // 方法-1： 多线程处理
    vector<thread> vec_thr;
    auto beg = std::chrono::system_clock::now();
    
    for (int i=0; i<thread_num; i++) {
        vec_thr.emplace_back(thread_func_for_multi_thread, i);
    }
    for (int i=0; i<thread_num; i++) {
        vec_thr[i].join();
    }
    int sum = 0;
    for (int i=0; i<thread_num; i++) {
        sum += result[i];
    }
    cout << "sum = " << sum << endl;
    
    auto end = std::chrono::system_clock::now();
    auto time_cost = std::chrono::duration_cast<std::chrono::milliseconds>(end - beg).count();
    cout << "Elapsed time: " << time_cost << " ms" << endl;
    
    // 方法-2： 单线程处理
    beg = std::chrono::system_clock::now();
    thread one_thrd(thread_func_for_one_thread);
    one_thrd.join();
    end = std::chrono::system_clock::now();
    time_cost = std::chrono::duration_cast<std::chrono::milliseconds>(end - beg).count();
    cout << "Elapsed time: " << time_cost << " ms" << endl;
    
    // 方法-3： 多线程处理，避开 False Sharing 
    vector<thread> vec_thr_2;
    beg = std::chrono::system_clock::now();
    
    for (int i=0; i<thread_num; i++) {
        vec_thr_2.emplace_back(thread_func_for_multi_thread_improved, i);
    }
    for (int i=0; i<thread_num; i++) {
        vec_thr_2[i].join();
    }
    sum = 0;
    for (int i=0; i<thread_num; i++) {
        sum += result[i];
    }
    cout << "Improved Multi Thread: sum = " << sum << endl;
    
    end = std::chrono::system_clock::now();
    time_cost = std::chrono::duration_cast<std::chrono::milliseconds>(end - beg).count();
    cout << "Elapsed time: " << time_cost << " ms" << endl;
}


int main()
{
    test();
    
    return 0;
}

运行结果如下：

$g++ 2.cpp -lpthread -O3

$./a.out
sum = 8387609
Elapsed time: 27 ms
One thread: count = 8387609
Elapsed time: 6 ms
Improved Multi Thread: sum = 8387609
Elapsed time: 1 ms

由上可见：
方法-1是多线程的方法，耗时30ms；
方法-2是单线程，耗时11ms；
方法-3还是多线程，耗时仅 2ms；

为什么方法-1的多线程比方法-2的单线程还慢呢?
因为 result[] 这个数组中的数据存在同一个 Cache Line 中，而所有的线程都会对这个 Cache Line 进行写操作，从而导致所有的线程都在不断地重新同步 result[] 所在的 Cache Line，因此 12 个线程还跑不过一个线程。这叫 False Sharing

那么方法-3相比方法-1，做的改进是什么呢？
就是用一个本地变量来记录count值，最后结束的时候再赋给 result[i]. 这样，就避免了所有线程不断更新同一个cache line了。
这个程序对于多线程编程中的 Performance 提升还是有相当借鉴意义的。值得记录下来。

参考文献：
CPU Cache

（完）