⚡局部性原理概念

程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限于某个内存区域，具体来说，局部性通常有两种形式：时间局部性和空间局部性。

CPU的工作要高速，我们希望 CPU 需要的数据更多的就在 L1 里面，一找就找着。不希望更多的跑到下面内存乃至磁盘里面去找，这样会花更多的时间。所以当CPU用了一个数据，计算机会预见性的存入其他等会儿CPU可能会用到的数据到L123内存，用到的可能性越大，就能存到越接近寄存器的层次。这也才是缓存的真正意义。那么，计算机怎样才能判断一个数据接下来可能被用到？

• 时间局部性：被引用过一次的存储器位置在未来会被多次引用，如果一个数据项正在被访问，那么在近期它很可能还会被再次访问。

• 空间局部性：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。

而且，对于变量之间的距离太远，它的空间局部性会越差，因为 CPU 没有办法在其附近找到变量

其应用就是二维数组分别按行和列遍历输出，前者的时间会短于后者

⚡分支预测

对于统计一个数组中大于0的个数，如果这个数组无序随机，那么它所花费的时间要比有序或者有规律(正序、逆序、按照一定间隔出现等等只要是有某种规律)的数组要长，其中的原因就是分支预测，其实质上就是局部性原理的应用

分支预测就是预先预测会用到某些数据，虽然程序还没有执行这后面的相关指令，但是我们此时有并行计算的能力，完全可以预先计算或者读取一部分数据，然后当程序真正执行到后面的时候，再去看是否确实用到了我们计算好或者提前准备好的数据，如果用到了，那么直接使用，加大 CPU 运行效率；如果没有用到，那么再去加载准备需要的数据

例如程序中的分支，我们不知道程序会进入哪一个分支，此时我们有两种方案：第一，CPU 暂停等待前面的指令执行完成，然后再去沿着正确的分支执行。第二，由于现代 CPU 很复杂，有很长的 pipeline，所以更好的解决办法是首先猜测会进入哪一个分支，如果猜错了，那么会刷新管道，回滚到分支，沿着正确的分支开始；如果猜对了，就继续执行

如果每次猜对了，执行会一直进行；如果经常猜错，就会花时间回滚到分支，重新开始。

而猜测的方式是根据历史数据来的，如果常常选择第一个分支，那么下次就会猜测第一个分支，如果常常是交替选择的，那就交替猜测……

回到最开始的问题，其实就是有规律的数组中的数据可以更好的被提前预测，并且可以先被读取到缓存中，等需要的时候直接调用就好了，速度要比那一时刻再去内存中读取的要快

原出处: stack overflow 上面的一个答案