众所周知, cpu是计算机的大脑, 它负责执行程序的指令; 内存负责存数据, 包括程序自身数据. 同样大家都知道, 内存比cpu慢很多. 其实在30年前, cpu的频率和内存总线的频率在同一个级别, 访问内存只比访问cpu寄存器慢一点儿. 由于内存的发展都到技术及成本的限制,
现在获取内存中的一条数据大概需要200多个cpu周期(cpu cycles), 而cpu寄存器一般情况下1个cpu周期就够了.
cpu缓存
网页浏览器为了加快速度,会在本机存缓存以前浏览过的数据; 传统数据库或nosql数据库为了加速查询, 常在内存设置一个缓存, 减少对磁盘(慢)的io. 同样内存与cpu的速度相差太远, 于是cpu设计者们就给cpu加上了缓存(cpu cache). 如果你需要对同一批数据操作很多次,
那么把数据放至离cpu更近的缓存, 会给程序带来很大的速度提升. 例如, 做一个循环计数, 把计数变量放到缓存里,就不用每次循环都往内存存取数据了. 下面是cpu cache的简单示意图.
随着多核的发展, cpu cache分成了三个级别: l1, l2, l3. 级别越小越接近cpu, 所以速度也更快, 同时也代表着容量越小. l1是最接近cpu的, 它容量最小, 例如32k, 速度最快,每个核上都有一个l1 cache(准确地说每个核上有两个l1 cache,
一个存数据 l1d cache, 一个存指令 l1i cache). l2 cache 更大一些,例如256k, 速度要慢一些, 一般情况下每个核上都有一个独立的l2 cache; l3 cache是三级缓存中最大的一级,例如12mb,同时也是最慢的一级, 在同一个cpu插槽之间的核共享一个l3 cache.
从cpu到
大约需要的cpu周期
大约需要的时间(单位ns)
寄存器
1 cycle
l1 cache
~3-4 cycles
~0.5-1 ns
l2 cache
~10-20 cycles
~3-7 ns
l3 cache
~40-45 cycles
~15 ns
跨槽传输
~20 ns
内存
~120-240 cycles
~60-120ns
感兴趣的同学可以在linux下面用cat /proc/cpuinfo, 或ubuntu下lscpu看看自己机器的缓存情况, 更细的可以通过以下命令看看:
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32k
$ cat /sys/devices/system/cpu/cpu0/cache/index0/type
data
$ cat /sys/devices/system/cpu/cpu0/cache/index0/level
1
$ cat /sys/devices/system/cpu/cpu3/cache/index3/level
3
就像数据库cache一样, 获取数据时首先会在最快的cache中找数据, 如果没有命中(cache miss) 则往下一级找, 直到三层cache都找不到,那只要向内存要数据了. 一次次地未命中,代表取数据消耗的时间越长.
缓存行(cache line)
为了高效地存取缓存, 不是简单随意地将单条数据写入缓存的. 缓存是由缓存行组成的, 典型的一行是64字节. 读者可以通过下面的shell命令,查看cherency_line_size就知道知道机器的缓存行是多大.
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
cpu存取缓存都是按行为最小单位操作的. 在这儿我将不提及缓存的associativity问题, 将问题简化一些. 一个java long型占8字节, 所以从一条缓存行上你可以获取到8个long型变量. 所以如果你访问一个long型数组, 当有一个long被加载到cache中,
你将无消耗地加载了另外7个. 所以你可以非常快地遍历数组.
实验及分析
我们在java编程时, 如果不注意cpu cache, 那么将导致程序效率低下. 例如以下程序, 有一个二维long型数组, 在我的32位笔记本上运行时的内存分布如图:
加上62个long型一行long数据一共占512字节. 所以这个二维数据是顺序排列的.
public class l1cachemiss {
private static final int runs = 10;
private static final int dimension_1 = 1024 * 1024;
private static final int dimension_2 = 62;
private static long[][] longs;
public static void main(string[] args) throws exception {
thread.sleep(10000);
longs = new long[dimension_1][];
for (int i = 0; i < dimension_1; i++) {
longs[i] = new long[dimension_2];
for (int j = 0; j < dimension_2; j++) {
longs[i][j] = 0l;
}
}
system.out.println("starting....");
final long start = system.nanotime();
long sum = 0l;
for (int r = 0; r < runs; r++) {
// for (int j = 0; j < dimension_2; j++) {
// for (int i = 0; i < dimension_1; i++) {
// sum += longs[i][j];
// }
// }
for (int i = 0; i < dimension_1; i++) {
for (int j = 0; j < dimension_2; j++) {
sum += longs[i][j];
}
system.out.println("duration = " + (system.nanotime() - start));
}
}
编译后运行,结果如下
$ java l1cachemiss
starting....
duration = 1460583903
然后我们将22-26行的注释取消, 将28-32行注释, 编译后再次运行,结果是不是比我们预想得还糟?
duration = 22332686898
前面只花了1.4秒的程序, 只做一行的对调要运行22秒. 从上节我们可以知道在加载longs[i][j]时, longs[i][j+1]很可能也会被加载至cache中, 所以立即访问longs[i][j+1]将会命中l1 cache, 而如果你访问longs[i+1][j]情况就不一样了,
这时候很可能会产生 cache miss导致效率低下.
下面我们用perf来验证一下,先将快的程序跑一下.
$ perf stat -e l1-dcache-load-misses java l1cachemiss
duration = 1463011588
performance counter stats for 'java l1cachemiss':
164,625,965 l1-dcache-load-misses
13.273572184 seconds time elapsed
一共164,625,965次l1 cache miss, 再看看慢的程序
duration = 21095062165
1,421,402,322 l1-dcache-load-misses
32.894789436 seconds time elapsed
这回产生了1,421,402,322次 l1-dcache-load-misses, 所以慢多了.
以上我只是示例了在l1 cache满了之后才会发生的cache miss. 其实cache miss的原因有下面三种:
1. 第一次访问数据, 在cache中根本不存在这条数据, 所以cache miss, 可以通过prefetch解决.
2. cache冲突, 需要通过补齐来解决.
3. 就是我示例的这种, cache满, 一般情况下我们需要减少操作的数据大小, 尽量按数据的物理顺序访问数据.