基础数据结构——数组（动态数组，二维数组，缓存与局部性原理）-4.缓存与局部性原理

时间：2024-10-19 08:06:22

这里只讨论空间局部性

  • cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了
  • 缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算啊，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性
定义两个求和方法
public static void sum1(int[][] arr, int rows, int columns) {
    long sum = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            sum += arr[i][j];
        }
    }
    System.out.println("sum1:" + sum);
}

public static void sum2(int[][] arr, int rows, int columns) {
    long sum = 0;
    for (int j = 0; j < columns; j++) {
        for (int i = 0; i < rows; i++) {
            sum += arr[i][j];
        }
    }
    System.out.println("sum2:" + sum);
}

比较下面 s u m 1 sum1 sum1 和 s u m 2 sum2 sum2 两个方法的执行效率

int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];

StopWatch sw = new StopWatch();

sw.start("sum1");
sum1(a, rows, columns);
sw.stop();

sw.start("sum2");
sum2(a, rows, columns);
sw.stop();

System.out.println(sw.prettyPrint());

执行结果
在这里插入图片描述
可以看到 s u m 1 sum1 sum1 的效率比 s u m 2 sum2 sum2 快很多，为什么呢？

  • 缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖
  • 如果不能充分利用缓存的数据，就会造成效率低下

相关文章