计算机组成 -- 高速缓存

缓存行

$ 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

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

高速缓存

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

类比

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

Direct Mapped Cache

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

迭代性能对比

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

常见误解
- 把volatile当成一种锁机制，等同于sychronized，不同线程访问特定变量都会去加锁
- 把volatile当成一个原子化的操作机制，认为加了volatile之后，对于一个变量的自增操作就会变成原子性的
volatile关键字最核心的知识点，要关系到Java内存模型上
- Java内存模型（JMM）是Java虚拟机这个进程级虚拟机里的一个内存模型
- JMM和计算机组成里的CPU、高速缓存和主内存组合在一起的硬件体系非常相似

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;
            }
        }
    }
}

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;

# ChangeListener不再工作，在ChangeListener眼里，觉得COUNTER的值一直为0
Incrementing COUNTER to : 1
Incrementing COUNTER to : 2
Incrementing COUNTER to : 3
Incrementing COUNTER to : 4
Incrementing COUNTER to : 5

// 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();
            }
        }
    }
}

# "恢复正常"
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

volatile关键字的含义：确保对于volatile变量的读取和写入，都一定会同步到主内存里，而不是从Cache里面读取
样例1
- 使用volatile关键字，所有数据的读和写都是来自主内存，ChangeMaker和ChangeListener看到的COUNTER是一样的
样例2
- 去掉volatile关键字，ChangeListener一直忙等待循环
- 尝试不停地获取COUNTER的值，这样就会从当前线程的『Cache』里面获取
- 于是，这个线程没有时间从主内存里同步更新后的COUNTER值，一直卡死在COUNTER=0的死循环上
样例3
- Thread.sleep(5)给了这个线程喘息的机会，就有机会把最新的数据从主内存同步到自己的高速缓存中

CPU vs JMM

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

写入策略

写直达 – Write-Through

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

写回 – Write-Back

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