- 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
- 术语： 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。
- 缓存的一致性 与 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
（完）