局部性

一个编写良好的计算机程序常常具有良好的局部性。他们都倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理，是一个持久的概念，对于硬件和软件系统的设计和性能都有极大的影响。

• 局部性：
  • 空间局部性：他们都倾向于引用邻近于其他最近引用过的数据项的数据项
    • 在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近一个内存位置
  • 时间局部性：倾向于引用引用过的数据项本身
    • 在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来被多次引用

      一般而言，有良好局部性的程序比局部性差的程序运行得更快。

关于局部性在硬件与软件中的设计 - 硬件层 - 局部性原理允许计算机设计者通过引入[[高速缓冲存储器]]的小而快速的存储器来保存最近被引用的指令和数据，从而提高了对主存的访问速度 - 操作系统级 - 局部性原理允许系统使用主存作为虚拟地址空间最近被引用快的高速缓存 - 类似的，操作系统用主存来缓存磁盘文件系统中最近被使用的磁盘块 - 应用程序级 - Web浏览器将最近被请求的文档放在本地磁盘上 - 大容量的Web服务器将最近被请求的文档放在前端磁盘高速缓存中

对程序数据引用的局部性

对于一个简单的二维数组求和函数，在行上遍历和在列上进行遍历的速度是不一样的，即使最后的结果一致，可能代码量也一致，但是运行速度天差地别，原因就在于读取数据的时候，会将内存中相邻的数据提取到Cache中，加速下一次的访问，如果在行上进行遍历，就可以很好的利用到Cache（命中），如果在列上进行遍历，则每一次都是不命中，需要重新从内存中读取数据，导致速度的下降，而Cache的设计就是局部性原理的产物

取指令的局部性

对于取指令也是类似的，因为程序一般是顺序执行的，提前取出指令存放在Cache中，能够提高取指的速度（因此反复跳转的程序，具有较差的局部性）