利用局部性原理提高程序性能

具有良好局部性的程序，倾向于访问相同的数据，或者访问邻近的数据。

因为第一次访问后，被访问的数据及其邻近的数据（在同一个块里）被缓存了，下次继续访问可以命中缓存

具有良好局部性的程序，倾向于从更高层次的存储结构访问数据。

高层次的存储结构是低层次的存储结构的缓存，层次越高，访问速度越快

image.png image.png

局部性有2种不同的形式

• 时间局部性: 在一个具有良好时间局部性的程序中，如果一个存储位置被引用了，很可能在不久的将来被再次引用
• 空间局部性: 在一个具有良好空间局部性的程序中，如果一个存储位置被引用了，很可能在不久的将来引用其附近的存储位置

以二维数组的求和为例，看一下局部性原理对程序性能的影响有多大。
定义一个M*N的二维数组，用两种不同的顺序遍历数组进行求和。

public class TestLocality {

    private static final int M = 2000;

    private static final int N = 3000;

    public static void main(String[] args) {
        int[][] arr = new int[M][N];
        init(arr);

        int testTimes = 10;
        int totalTime1 = 0, totalTime2 = 0;

        for (int i = 0; i < testTimes; i++) {
            long time1 = test1(arr);
            long time2 = test2(arr);
            totalTime1 += time1;
            totalTime2 += time2;
        }

        System.out.println("average time1: " + totalTime1 / testTimes + "ms");
        System.out.println("average time2: " + totalTime2 / testTimes + "ms");
    }

    private static void init(int[][] arr) {
        int num = 0;
        for (int i = 0; i < M; i ++) {
            for (int j = 0; j < N; j++) {
                arr[i][j] = num++;
            }
        }
    }

    /**
     * 按照行顺序扫描
     */
    private static long test1(int[][] arr) {
        long sum = 0;
        long start = System.currentTimeMillis();
        for (int i = 0; i < M; i ++) {
            for (int j = 0; j < N; j++) {
                sum += arr[i][j];
            }
        }
        return System.currentTimeMillis() - start;
    }
    
    /**
     * 按照列顺序扫描
     */
    private static long test2(int[][] arr) {
        long sum = 0;
        long start = System.currentTimeMillis();
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < M; j++) {
                sum += arr[j][i];
            }
        }
        return System.currentTimeMillis() - start;
    }
}

打印结果

average time1: 4ms
average time2: 47ms

test1方法，按照数组存储顺序进行访问，具有良好的空间局部性，10次运行平均耗时4ms

image.png

test2方法，没有按照数组存储顺序进行访问，不具备良好的空间局部性，10次运行平均耗时47ms

image.png