【编程】程序的局部性原理对代码效率的影响

局部性原理分为了时间局部性和空间局部性。
时间局部性：一条指令和下次执行，一个数据的访问和下一次访问都集中在一个较短时期内。
空间局部性：当前指令和邻近几条指令、当前访问和邻近的几个数据都集中在一个较小区域内。
分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置
访问速度快、空间大、使用方便（不需要程序猿过多构思数据结构）
例子：

这个整数数组的空间大小是1024x1024,int型每一个是4byte，也就说这一个数组整体会占4M的内存空间。但是物理内存只有4K。此时，
程序1：A【0】【0】~ A【1023】【0】==>A【1023】【1023】

程序2：A【0】【0】~ A【0】【1023】==>A【1023】【1023】

区别：实际上A【1】【0】和A【0】【0】从空间上来看，中间差了1024个数据也就说是4K的数据大小，但是A【1】【0】和A【1】【1】之间的距离只有一个数据也就说4byte。
那么对于程序2而言，在数据A【0】【x】占据了一个页。当他第一次访问时，数组的数据还在硬盘上时，会产生缺页异常，此时OS会把仅有的4K空间使用上，并把A【0】【x】数组放入内存空间 ，然后就可以对A【0】【x】数组进行正常访问了。根据循环，第二次访问A【0】【1】时，因为已经有了对应的页，就不会发生页异常。内循环执行完后，进入下一个内循环，此时访问A【1】【0】发生一次中断，然后接下来的1023次访问不会再发生中断。具备很好的空间局部性和时间局部性。也就意味着一共发生了1024次缺页中断
对于程序1而言，在数据A【0】【x】占据了一个页。当他第一次访问时，数组的数据还在硬盘上时，会产生缺页异常，此时OS会把仅有的4K空间使用上，并把A【0】【x】数组放入内存空间 ，然后就可以对A【0】【x】数组进行正常访问了。根据循环，第二次访问时，会访问A【1】【0】，此时会再次产生缺页异常，因为对应A【1】【x】的页仍然不在内存，在硬盘中，需要再次把4K的物理内存用到A【1】【x】数组上，此后导入A【1】【x】的页。同理，在一个内循环中，每一次都会跳4K空间去访问一个数据，每一次访问都会发生缺页异常。也就意味着一共发生了1024x1024次缺页中断
可以看出程序的不同写法对开销的影响是相当大的。