人必有所执，方能有所成

0%

cpu cache

发表于 更新于 分类于 阅读次数：
本文字数： 3k 阅读时长 ≈ 5 分钟

1 cpu cache的介绍

cpu cache(高速缓存)分为三类：L1 cache、L2 cache和L3 cache。

其中：

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

以下是《深入理解计算机系统》书中的部分截图：

计算机系统各种不同类型的缓存：

Intel Core i7处理器的cache的层次结构：

Corei7高速缓存层次的特性

2 cpu cache对程序性能的影响

2.1 存储器山

程序从存储系统中读数据的速率为读吞吐量（read throughput），或者读带宽（read bandwidth）。

x轴为参数size，控制时间局部性的程度；size的值越小，得到工作集越小，因此时间局部性越好。
y轴为参数stride，控制空间局部性的程度；strde的越小，得到的空间局部性越好。

有以下几个结论：

  • 时间局部性

stride固定时，size越小，工作集越小，固定时间内访问工作集的次数越多，就越能体现出时间局部性；

  • 空间局部性

size固定，即固定工作集大小时，读吞吐量随着步长的增大而平缓下降，因为空间局部性变差；

  • 硬件预取(prefetching)

注意到步长为1时，读吞吐量随工作集大小变化非常缓慢。 这是因为cpu cache的硬件预取机制。这是一项很聪明的机制，也是对于撰写具有良好局部性程序的程序员的一种奖赏。

2.2 Cache line

先解释一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方，对于CPU来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，对于这样的一块一块的数据单位，术语叫“Cache Line”，
一般来说，一个主流的CPU的Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），64Bytes也就是16个32位的整型，这就是CPU从内存中捞数据上来的最小数据单位。

1
2
3
4
$ getconf LEVEL1_DCACHE_LINESIZE
64
$ getconf LEVEL2_CACHE_LINESIZE
64

以下代码，测试间隔SIZE个元素，顺序遍历数组中的元素，测试所用的时间

1
2
3
4
5
6
7
8
9
10
11
#define SIZE 67108864  // 64 * 1024 * 1024.  The array will be 512 MiB.

int main() {
   int64_t* array = (int64_t*)calloc(SIZE, sizeof(int64_t));
   clock_t t0 = clock();
   for (size_t i = 0; i < SIZE; i += STEP) {
      array[i] &= 1;  // Do something.  Anything; 这部分时间忽略
   }
   clock_t t1 = clock();
   printf("%d %f\n", STEP, 1000 * (t1 - t0) / CLOCKS_PER_SEC);
}

C 库函数 clock_t clock(void) 返回程序执行起（一般为程序的开头），处理器时钟所使用的时间。为了获取 CPU 所使用的秒数，您需要除以 CLOCKS_PER_SEC。

分析：

  • Step Size为1~8时，处理时间基本一致，因为每个64Bytes的数据都有加载，即使不是每个数据都处理；但处理时间相比加载数据的时间太短，可以忽略。
  • Step Size为16时，间隔128Bytes去修改，所以从内存中读取了一半的数据，时间为1/2；
  • Step Size为32时，从内存中读取了1/4的数据, 所以时间为1/4;

2.2 局部性（locality）

编写良好的计算机程序往往具有很好的局部性,也就是他们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性被称为局部性原理;

时间局部性（Temporal locality）

在一个具有良好的时间局部性的程序中,被引用过一次的内存位置很可能在不远的将来再多次被引用;

空间局部性（Spatial locality）

在一个具有良好的空间局部性的程序中,如果一个内存位置被引用了,那么程序很可能在不远的将来引用附近的一个内存位置;

  1. 对于每个访问的内存位置，附近的位置也在短时间内被使用。
  2. 内存是顺序访问的。

缓存再设计上也遵循以上2个规则：

  • 数据以块的形式加载；对已加载缓存行中位置的后续访问基本上是免费的。
  • 来自顺序访问模式的缓存行被硬件预取(prefetching)

以下是比较std::vector和std::list进行顺序访问的一个例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <list>
#include <string>
#include <vector>

const int N = 5000;

int main() {
  // std::vector<int> vs[N];
  std::list<int> vs[N];
  std::srand(std::time(0));
  // Append an average of 5000 random values to each container.
  for (int i = 0; i < N * 5000; ++i) {
    vs[std::rand() % N].push_back(std::rand());
  }

  int sum = 0;
  std::clock_t t0 = std::clock();
  for (int m = 0; m < N; ++m) {
    for (int num : vs[m]) {
      sum += num;
    }
  }
  std::clock_t t1 = std::clock();

  // Also print the sum so the loop doesn't get optimized out.
  std::cout << sum << '\n' << (t1 - t0) << '\n';
}

测试结果发现，顺序遍历时，std::vector是std::list的运行时间约1/14, 有更好的空间局部性。

参考链接