具有良好局部性的程序，倾向于访问相同的数据，或者访问邻近的数据。
因为第一次访问后，被访问的数据及其邻近的数据（在同一个块里）被缓存了，下次继续访问可以命中缓存
具有良好局部性的程序，倾向于从更高层次的存储结构访问数据。
高层次的存储结构是低层次的存储结构的缓存，层次越高，访问速度越快
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
