什么是缓存的局部性原理？
存储结构
了解计算机的存储结构，对我们编写优秀的程序很有帮助，虽然计算机的内部对我们来说是透明的，但是如果我们能多了解一些计算机的运行机制，对我们编写高效的程序大有好处。
我们来看一下计算机的存储结构
越接近cup的存储器速度越快容量越小，越远离cup的存储器速度越慢容量越大。
最高层的L0寄存器，cpu可以在1个时钟周期内访问它们
访问L1高速缓存，cup大约需需要4个时钟周期
访问L2高速缓存，cup大约需需要10个时钟周期
访问L3高速缓存，cup大约需需要50个时钟周期
访问主存，cup大约需要200个时钟周期
访问硬盘，cup大约需要1千万个时钟周期
高速缓存比主存大约快10倍，主存比硬盘大约快5万倍，所以cup取数据尽量要在高一层的存储设备中取，尽量避免在低一层的存储设备中取，这是缓存设计的基本思想。
缓存
缓存是一个更小更快的设备，它作为更大更慢设备的缓冲区。存储层次结构中的高层存储设备都作为其低一层的存储设备的缓存，比如L0是L1的缓存，L1是L2的缓存，L2是L3的缓存，L3是主存的缓存等等。
为方便操作，一组组连续的数据对象被分成一个个数据块，不同层次之间的数据块大小是不一样的。比如L0和L1之间传送的是一个字节大小的块，L2和L1之间（以及L3和L2，L4和L3）传送的是几十字节大小的块，而L5和L4（硬盘和主存）之间传送的是几百或几千字节的块。
高一层的存储设备总是存着低一层存储设备的部分数据块，由于高一层的存储设备容量比第一层的存储设备小，所以缓存的数据只能是下一层设备数据的一小部分。
缓存命中
如果cpu要读取数据块1，cpu先在高速缓存中查找数据块1，如果找到就直接返回，这就叫“缓存命中”，因为缓存的速度比主存的速度要快很多，缓存命中大大提高了效率。
缓存不命中
如果cpu要读取数据块5，数据块5不在缓存中，那么叫做“缓存不命中”。那么cpu就要去主存中取到数据块5，然后把数据块5放到高速缓存中，如果缓存中的数据存满了，就要覆盖现存的一个数据块。
这里有个问题，如果缓存的数据已经放满了，那么数据块5应该替换哪一个数据块呢？这就涉及到放置策略了，最简单的就是随机放置策略，随机找一个数据库替换掉，这个策略虽然简单粗暴，但是代价较高，cpu想定位到某个数据块比较麻烦。
还有一种限制性的放置策略，比如主存中第 i 块数据，必须放到 i%4 位置的高速缓存中，例如，主存中第0，4，8，12号数据库会放到高速缓存的第1个块中，主存中的第1，5，9，13号数据块会放到高速缓存的第2个数据块中。上图就是用了这种放置策略。
局部性
一个优秀的程序通常具有良好的局部性，它们通常会重复使用已用过的数据，或者使用已用过数据的邻近数据，也就是说，程序常常会使用集中在一起的局部数据。
局部性分为：时间局部性和空间局部性。如果一个内存位置被重复的引用，那就是有了时间局部性，如果一个内存位置被引用了，很快这个位置的附近位置也被引用了，这就有了空间局部性。
由于缓存中的数据是一个个数据块，每个数据块包含几十到几千字节不等，如果某个程序要访问数组a，第一次缓存没命中，cpu会从主存中取出包含数组a的一个数据块，复制到缓存中来，下次访问a[1],a[2],a[3]的数据时每次都缓存命中，极大的提高了效率，实现了空间的局部性。
写个程序来验证下：
循环累加int[10000][10000] 的二维数组，按i，j 的顺序访问利用了缓存的空间局部性，效率提高了200倍。
在程序中注意利用缓存的局部性原理，能大大提高程序的运行效率哦。
文章被以下专栏收录
