具有良好局部性的程序，傾向于訪問相同的數(shù)據(jù)，或者訪問鄰近的數(shù)據(jù)。

因?yàn)榈谝淮卧L問后，被訪問的數(shù)據(jù)及其鄰近的數(shù)據(jù)（在同一個(gè)塊里）被緩存了，下次繼續(xù)訪問可以命中緩存

具有良好局部性的程序，傾向于從更高層次的存儲(chǔ)結(jié)構(gòu)訪問數(shù)據(jù)。

高層次的存儲(chǔ)結(jié)構(gòu)是低層次的存儲(chǔ)結(jié)構(gòu)的緩存，層次越高，訪問速度越快

image.png

image.png

局部性有2種不同的形式

• 時(shí)間局部性: 在一個(gè)具有良好時(shí)間局部性的程序中，如果一個(gè)存儲(chǔ)位置被引用了，很可能在不久的將來被再次引用
• 空間局部性: 在一個(gè)具有良好空間局部性的程序中，如果一個(gè)存儲(chǔ)位置被引用了，很可能在不久的將來引用其附近的存儲(chǔ)位置

以二維數(shù)組的求和為例，看一下局部性原理對(duì)程序性能的影響有多大。
定義一個(gè)M*N的二維數(shù)組，用兩種不同的順序遍歷數(shù)組進(jì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;
    }
}

打印結(jié)果

average time1: 4ms
average time2: 47ms

test1方法，按照數(shù)組存儲(chǔ)順序進(jìn)行訪問，具有良好的空間局部性，10次運(yùn)行平均耗時(shí)4ms

image.png

test2方法，沒有按照數(shù)組存儲(chǔ)順序進(jìn)行訪問，不具備良好的空間局部性，10次運(yùn)行平均耗時(shí)47ms

image.png