企业官网建设流程全解析

局部性原理

程序倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身，这种倾向性称为局部性原理。

:::info
局部性分为两种不同的形式：

• 时间局部性：被引用过一次的内存位置很可能在不远的将来再被多次引用。
• 空间局部性：一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。

:::

对程序数据引用的局部性

intsumvec(intv[N]){inti,sum=0;for(inti=0;i<N;i++)sum+=v[i];returnsum;}

在这个程序中，变量sum在短时间内多次被引用，具有**良好的时间局部性，空间局部性较差，向量v的元素（内存位置）被连续访问，具有良好的空间局部性**，但每个元素只访问一次，时间局部性较差。这个程序要么有好的时间局部性，要么有良好的空间局部性，所以可以说这个程序有良好的局部性。

像sumvec这样顺序访问一个向量每个元素的函数，具有步长为 1 的引用模式，又称顺序引用模式。而一个连续向量中，每隔 k 个元素进行访问，就称为**步长为 k 的引用模式**。一般而言，随着步长的增加，空间局部性下降。

intsumarrayrows(inta[M][N]){inti,j,sum=0;for(i=0;i<M;i++){for(j=0;j<N;j++){sum+=a[i][j];}}returnsum;}

intsumarraycols(inta[M][N]){inti,j,sum=0;for(i=0;i<N;i++){for(j=0;j<M;j++){sum+=a[i][j];}}returnsum;}

考虑这两个函数的步长，步长为 1 的引用模式的空间局部性优于步长为 N 的引用模式。

取指令的局部性

程序指令是存放在内存中的，CPU 必须（取出）读出这些指令，所以程序中也有关于取指令的局部性。例如循环体中的指令是按照连续的内存顺序执行的，因此循环有**良好的空间局部性。因为循环体会被执行很多次，所以也有良好的时间局部性**。

⚠️**代码区别于程序数据的一个重要属性是在运行时他是不能被修改的。当程序正在执行时，CPU 只从内存中读出它的指令。CPU 很少会重写或修改这些指令**。