局部性原理

腾讯ieg一面

面试官问出这个问题时，我不知道怎么回答，所以现在整理一下

这其实涉及到概率问题，计算机中在短时间内存在重复访问某些数据或者某些内存位置的情况，而访问其他数据或者内存的次数较少，那对于常访问的数据访问概率就高，其他数据概率就低。对于概率高的数据可以集中在一片区域，并且访问的速度很快，而其他的数据就集中在速度较慢的区域。很常见的应用就是存储金字塔，越往上速度越快，存储的数据越少

image

局部性分类

局部性有两种基本的分类， 时间局部性 和 空间局部性 ，按Wikipedia的资料，可以分为以下五类，其实有些就是时间局部性和空间局部性的特殊情况。

时间局部性(Temporal locality):

　　如果某个信息这次被访问，那它有可能在不久的未来被多次访问。时间局部性是空间局部性访问地址一样时的一种特殊情况。这种情况下，可以把常用的数据加cache来优化访存。

空间局部性(Spatial locality):

　　如果某个位置的信息被访问，那和它相邻的信息也很有可能被访问到。 这个也很好理解，我们大部分情况下代码都是顺序执行，数据也是顺序访问的。

内存局部性(Memory locality):

访问内存时，大概率会访问连续的块，而不是单一的内存地址，其实就是空间局部性在内存上的体现。目前计算机设计中，都是以块/页为单位管理调度存储，其实就是在利用空间局部性来优化性能。

分支局部性(Branch locality)

　　这个又被称为顺序局部性，计算机中大部分指令是顺序执行，顺序执行和非顺序执行的比例大致是5:1，即便有if这种选择分支，其实大多数情况下某个分支都是被大概率选中的，于是就有了CPU的分支预测优化。

等距局部性(Equidistant locality)

　　等距局部性是指如果某个位置被访问，那和它相邻等距离的连续地址极有可能会被访问到，它位于空间局部性和分支局部性之间。 举个例子，比如多个相同格式的数据数组，你只取其中每个数据的一部分字段，那么他们可能在内存中地址距离是等距的，这个可以通过简单的线性预测就预测是未来访问的位置。

实际应用

计算机缓存

缓存数据库redis等

CDN

CopyOnWrite写时复制