文章目录局部性原理对程序数据引用的局部性取指令的局部性局部性原理程序倾向于引用邻近于其他最近引用过的数据项的数据项或者最近引用过的数据项本身这种倾向性称为局部性原理。:::info局部性分为两种不同的形式时间局部性被引用过一次的内存位置很可能在不远的将来再被多次引用。空间局部性一个内存位置被引用了一次那么程序很可能在不远的将来引用附近的一个内存位置。:::对程序数据引用的局部性intsumvec(intv[N]){inti,sum0;for(inti0;iN;i)sumv[i];returnsum;}在这个程序中变量sum在短时间内多次被引用具有**良好的时间局部性空间局部性较差向量v的元素内存位置被连续访问具有良好的空间局部性**但每个元素只访问一次时间局部性较差。这个程序要么有好的时间局部性要么有良好的空间局部性所以可以说这个程序有良好的局部性。像sumvec这样顺序访问一个向量每个元素的函数具有步长为 1 的引用模式又称顺序引用模式。而一个连续向量中每隔 k 个元素进行访问就称为**步长为 k 的引用模式**。一般而言随着步长的增加空间局部性下降。intsumarrayrows(inta[M][N]){inti,j,sum0;for(i0;iM;i){for(j0;jN;j){suma[i][j];}}returnsum;}intsumarraycols(inta[M][N]){inti,j,sum0;for(i0;iN;i){for(j0;jM;j){suma[i][j];}}returnsum;}考虑这两个函数的步长步长为 1 的引用模式的空间局部性优于步长为 N 的引用模式。取指令的局部性程序指令是存放在内存中的CPU 必须取出读出这些指令所以程序中也有关于取指令的局部性。例如循环体中的指令是按照连续的内存顺序执行的因此循环有**良好的空间局部性。因为循环体会被执行很多次所以也有良好的时间局部性**。⚠️**代码区别于程序数据的一个重要属性是在运行时他是不能被修改的。当程序正在执行时CPU 只从内存中读出它的指令。CPU 很少会重写或修改这些指令**。