计算机组成 -- 高速缓存

缓存行

1
2
3
4
5
6
7
$ sysctl -a | grep -E 'cacheline|cachesize'
hw.cachesize: 17179869184 32768 262144 6291456 0 0 0 0 0 0
hw.cachelinesize: 64 # 64 Bytes
hw.l1icachesize: 32768 # 32 KB
hw.l1dcachesize: 32768 # 32 KB
hw.l2cachesize: 262144 # 256 KB
hw.l3cachesize: 6291456 # 6 MB
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
public static void f1() {
int[] arr = new int[64 * 1024 * 1024];

long start = System.currentTimeMillis();
for (int i = 0; i < arr.length; i++) {
arr[i] *= 3;
}
long end = System.currentTimeMillis();

System.out.println("f1 : " + (end - start));
}

public static void f2() {
int[] arr = new int[64 * 1024 * 1024];

long start = System.currentTimeMillis();
for (int i = 0; i < arr.length; i += 16) {
arr[i] *= 3;
}
long end = System.currentTimeMillis();
System.out.println("f2 : " + (end - start));
}

// f1 : 36
// f2 : 42
// f2/f1 : 1.17

高速缓存

  1. 按照摩尔定律CPU寄存器)的访问速度每18个月会翻一翻,相当于每年增长60%
  2. 虽然内存的访问速度也在不断增长,但远没有那么快,每年只增长7%左右
  3. 两个增长速度的差异,使得CPU访问性能和内存访问性能的差异不断拉大,至今,大概是120倍的差异
  4. 为了弥补两者之间的性能差异,在现代CPU中引入了高速缓存(L1 Cache、L2 Cache、L3 Cache)
    • 内存中的指令数据会被加载到L1~L3 Cache中,而不是直接由CPU访问内存去读取
    • 95%的情况下,CPU都只需要访问L1~L3 Cache,从里面读取指令和数据,而无需访问内存
    • CPU Cache指的是由SRAM组成的物理芯片
  5. 运行程序的时间主要花在了将对应的数据从内存中读取出来,加载到CPU Cache里,该过程是按照Cache Line来读取的
    • 日常使用的Intel服务器或者PC,Cache Line的大小通常是64字节
    • f2()每隔16个整型数计算一次,16个整型数正好是64个字节
      • f1()f2()需要把同样数量的Cache Line数据从内存中读取到CPU Cache中,最终两个程序花费的时间差不多

类比

  1. 现代CPU进行数据读取的时候,无论数据是否已经存储在Cache中,CPU始终会首先访问Cache
  2. 只有当CPU在Cache中找不到数据的时候,才会去访问内存,并将读取到的数据写入Cache
  3. 在各类基准测试实际应用场景中,CPU Cache的命中率通常能到达95%以上

Direct Mapped Cache

  1. 直接映射Cache策略:确保任何一个内存块的地址,始终映射(mod)到一个固定CPU Cache Line地址
  2. 假设主内存被分成32块(0~31),一共有8个缓存块,要访问第21号内存块,如果21号内存块在缓存块中,一定在5号缓存块
  3. 在实际计算中,通常会把缓存块的数量设置成2的N次方,在计算取模的时候,可以直接取内存地址的低N位
  4. 对应的缓存块中,会存储一个组标记(Tag),缓存块本身的地址表示访问内存地址的低N位,对应的组标记记录剩余的高位即可
  5. 缓存块中还有两个数据,一个是从主内存中加载来的实际存放的数据(Data Block),另一个是有效位(Valid Bit)
    • 有效位用来标记对应的缓存块中的数据是否有效
    • 如果有效位为0,无论其中的组标记和Cache Line里的数据内容是什么,CPU都会直接访问内存重新加载数据
  6. CPU在读取数据的时候,并不是要读取一整个Data Block,而是读取一个所需要的数据片段(叫作CPU里面的一个(Word))
    • 具体是哪个字,由这个字在整个Data Block里面的位置来决定,该位置称为偏移量(Offset)
  7. 一个内存的访问地址,最终包括
    • Tag高位代表的组标记
    • Index低位代表的索引
    • Offset:在对应的Data Block中定位对应位置偏移量
  8. 如果内存中的数据已经在CPU Cache中,那对一个内存地址的访问,会经历下面4个步骤
    1. 根据内存地址的低位,计算在Cache中的索引
    2. 判断有效位,确认Cache中的数据是否有效
    3. 对比内存地址的高位Cache中的组标记
      • 确认Cache中的数据就是要访问的内存数据,从Cache Line中读取对应的Data Block
    4. 根据内存地址的Offset位,从Data Block中,读取希望取到的
  9. 如果2、3步骤失效,CPU会访问内存,并把对应的Block Data更新到Cache Line中,同时更新对应的有效位组标记的数据

迭代性能对比

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
public static void iterateByRow(int rows, int cols) {
int[][] arr = new int[rows][cols];

long start = System.currentTimeMillis();
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
arr[row][col] *= 3;
}
}
System.out.println("iterateByRow : " + (System.currentTimeMillis() - start));
}

public static void iterateByCol(int rows, int cols) {
int[][] arr = new int[rows][cols];

long start = System.currentTimeMillis();
for (int col = 0; col < cols; col++) {
for (int row = 0; row < rows; row++) {
arr[row][col] *= 3;
}
}
System.out.println("iterateByCol : " + (System.currentTimeMillis() - start));
}

public static void main(String[] args) {
int rows = 4 * 1024;
int cols = 4 * 1024;
iterateByRow(rows, cols);
iterateByCol(rows, cols);
}
1
2
iterateByRow : 30
iterateByCol : 172

volatile

  1. 常见误解
    • volatile当成一种机制,等同于sychronized,不同线程访问特定变量都会去加锁
    • volatile当成一个原子化的操作机制,认为加了volatile之后,对于一个变量的自增操作就会变成原子性
  2. volatile关键字最核心的知识点,要关系到Java内存模型
    • Java内存模型(JMM)是Java虚拟机这个进程级虚拟机里的一个内存模型
    • JMM和计算机组成里的CPU、高速缓存和主内存组合在一起的硬件体系非常相似
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
31
32
33
34
35
36
37
38
public class VolatileTest {

private static volatile int COUNTER = 0;

public static void main(String[] args) {
new ChangeListener().start();
new ChangeMaker().start();
}

static class ChangeListener extends Thread {
@Override
public void run() {
int threadValue = COUNTER;
while (threadValue < 5) {
if (threadValue != COUNTER) {
System.out.println("Got Change for COUNTER : " + COUNTER + "");
threadValue = COUNTER;
}
}
}
}

static class ChangeMaker extends Thread {
@Override
public void run() {
int threadValue = COUNTER;
while (COUNTER < 5) {
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Incrementing COUNTER to : " + (threadValue + 1) + "");
COUNTER = ++threadValue;
}
}
}
}
1
2
3
4
5
6
7
8
9
10
Incrementing COUNTER to : 1
Got Change for COUNTER : 1
Incrementing COUNTER to : 2
Got Change for COUNTER : 2
Incrementing COUNTER to : 3
Got Change for COUNTER : 3
Incrementing COUNTER to : 4
Got Change for COUNTER : 4
Incrementing COUNTER to : 5
Got Change for COUNTER : 5
1
2
// 去掉volatile关键字
private static int COUNTER = 0;
1
2
3
4
5
6
# ChangeListener不再工作,在ChangeListener眼里,觉得COUNTER的值一直为0
Incrementing COUNTER to : 1
Incrementing COUNTER to : 2
Incrementing COUNTER to : 3
Incrementing COUNTER to : 4
Incrementing COUNTER to : 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// ChangeListener不再忙等待,稍微sleep 5ms
// 此时COUNTER依然没有volatile关键字修饰
static class ChangeListener extends Thread {
@Override
public void run() {
int threadValue = COUNTER;
while (threadValue < 5) {
if (threadValue != COUNTER) {
System.out.println("Got Change for COUNTER : " + COUNTER + "");
threadValue = COUNTER;
}
try {
Thread.sleep(5);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
# "恢复正常"
Incrementing COUNTER to : 1
Got Change for COUNTER : 1
Incrementing COUNTER to : 2
Got Change for COUNTER : 2
Incrementing COUNTER to : 3
Got Change for COUNTER : 3
Incrementing COUNTER to : 4
Got Change for COUNTER : 4
Incrementing COUNTER to : 5
Got Change for COUNTER : 5
  1. volatile关键字的含义:确保对于volatile变量的读取写入,都一定会同步到主内存里,而不是从Cache里面读取
  2. 样例1
    • 使用volatile关键字,所有数据的都是来自主内存,ChangeMaker和ChangeListener看到的COUNTER是一样
  3. 样例2
    • 去掉volatile关键字,ChangeListener一直忙等待循环
    • 尝试不停地获取COUNTER的值,这样就会从当前线程的『Cache』里面获取
    • 于是,这个线程没有时间从主内存里同步更新后的COUNTER值,一直卡死在COUNTER=0的死循环
  4. 样例3
    • Thread.sleep(5)给了这个线程喘息的机会,就有机会把最新的数据从主内存同步到自己的高速缓存中

CPU vs JMM

  1. 现在的Intel CPU,通常都是多核的,每个CPU核里面,都有独立的L1、L2 Cache,然后有多个CPU核共用的L3 Cache、主内存
  2. 在Java内存模型里面,每个线程都有独立的线程栈
    • 线程在读取COUNTER的数据的时候,其实是从本地的线程栈的Cache副本里面读取数据,而不是从主内存里面读取数据

写入策略

写直达 – Write-Through

  1. 每一次数据都要写入到主内存里,写入前,会先判断数据是否已经在Cache里
    • 如果是,先把数据写入更新到Cache里,再写入到主内存里
    • 如果否,只更新主内存
  2. 缺点:很慢
    • 无论数据是不是在Cache里面,都需要把数据写到主内存里面,类似于volatile关键字

写回 – Write-Back

  1. 不再是每次都把数据写入到主内存,而是只写到CPU Cache里面
    • 只有当CPU Cache里面的数据要被『替换』的时候,才把数据写入到主内存里面
  2. 如果发现要写入的数据,就在CPU Cache里,那么就只更新CPU Cache里的数据
    • 并且标记CPU Cache里的这个Block是(Dirty)的
    • 脏:CPU Cache里面的Block的数据和主内存是不一致
  3. 如果要写入的数据所对应的Cache Block里,放的是别的内存地址的数据,判断那个Cache Block里面的数据是否被标记为脏
    • 如果是的,就先把这个Cache Block里面的数据,写入到主内存里面
      • 然后在把当前要写入的数据,写入到Cache里,同时把Cache Block标记成脏的
    • 如果不是脏的,直接把数据写入到Cache里,然后再把Cache Block标记成脏的
  4. 加载内存数据到Cache里面的时候,也要多出一步同步脏Cache的动作
    • 如果加载内存里的数据到Cache的时候,发现Cache Block里面有标记
    • 需要先把Cache Block里面的数据写回到主内存,才能加载数据覆盖掉Cache
  5. 优点:大量的操作,都能命中缓存,在大部分时间里,都不需要读写主内存,性能比写直达要好很多

缓存一致性问题

  1. 无论是写直达还是写回,都没有解决多个线程或者多个CPU核心缓存一致性问题
  2. 解决方案:MESI协议
    • 应用场景:不仅可以在CPU Cache之间,也可以广泛用于各种需要使用缓存,同时缓存之间需要同步的场景
0%