CPU的局部性原理非常大的影响到了程序的性能，很多性能调优的场景就跟这个相关。比如说：Cacheline，字节对齐，甚至这个原理影响了编程语言的设计。程序员需要掌握这个知识来理解编程语言与CPU的结构。
介绍一些事实
- 用数组在任何情况下的效率都要比用链表高；
- 程序中应该多用循环少用递归
- 二维数组必须先循环行，再循环列；
- Cacheline就是根据这个原理设计的，理解了局部性原理可以理解为啥有“伪共享”以及怎么让变量常驻一个Cacheline中。
原理简单但是推论多
局部性原理分类
-
时间局部性：n时刻cpu访问过的代码与数据在n+1的时刻还会被访问 -
空间局部性：m位置cpu访问过的代码与数据，则[m,m+n]位置的数据也会马上被访问到，简单讲就是一旦访问了一个地址，那么邻居都要准备好被访问。
举个例子：
int i;
int array[N] = {0}
for(i=0;i<N;j++){
array[i] =1;
}
先看看空间局部性
-
数组可以说是编程语言里面比较常用的结构了（hash table就是用数组特性实现的，你想想用得多不多）。根据空间局部性原理，当CPU访问到i=0的元素时，i+n个字节其实已经从内存被加载到CPU缓存了（CPU访问内存的金字塔结构这里默认大家都知道了，不知道看这里 - Numbers Everyone Should Know小节）。接下来访问i=1,i=2,i=3....i=n都不需要再去访问内存了，因为都被
CPU cache了，这就是空间局部性原理的使用。 -
接着上面的，n就是CPU一次cache多大的范围合适呢？现在x64CPU就是64个字节，这个cache也有个专属名字——
cacheline。至于为啥是64个字节，应该是个经验值，这个大小对缓存程序，数据的粒度刚刚好吧，不纠结。还有很多数据都是经验数据，比如OS的页大小4k等等。 -
接着看链表，链表这种数据结构的优点是灵活，可以用O(1)做插入与删除，也就是扩容性能不错，可以应对未知大小的数据需求，但是根据
空间局部性原理，随机访问性能就被拉低了，看看图：
数组VS链表
套用分布式缓存的概念，链表这种数据结构更容易导致CPU的缓存被击穿。所以C++语言的作者都推荐大家在任何情况下都不要使用链表。(出处已经忘记了……)。那么怎么利用数组做出可以灵活添加与删除元素的结构呢？答案是——ringbuffer。
然而链表并没有消失，因为数组的原罪动态扩容没有解决，所以导致两个后果：
3.1.Hashtable在任何语言实现下对于扩容的性能都非常不友好，特别是在多核CPU多线程并发情况下尤其消耗性能，导致在很多读写相当，性能critcal的场景下hashtable不是一个理想的选择。因为会抖动，所以不是一种稳定的数据结构。例子：linux中很少用hashtable对未知大小的数据做检索，转而使用红黑树；redis用跳表做zset的实现。这都用了链表的特性。
3.2. 启示——在工程上有些瓶颈是不要试图去突破的，比如链表与数组，你不要期望可以设计出一种完美的数据结构来解决所有的问题，永远都是去做权衡，而不是盲目自信去做无谓的浪费。有很多例子都是经过数学证明的，不要试图去突破，比如CAP，比如排序算法的效率。 -
一个需要优化的代码例子（当然这里的n与m要足够大，越大越明显）：
int a[n][m];
for(int i=0; i<m;i++){
for(int j=0;j<n;j++){
a[j][i] =1;
}
}
这个例子的意思是先访问列再访问行，访问的步长是n个元素，如果n等于16，就正好跨过了一个缓存行，正好j每++一次就导致一次CPU缓存被击穿，性能就巨差。正确的代码：
int a[n][m];
for(int i=0; i<n;i++){
for(int j=0;j<m;j++){
a[i][j] =1;
}
}
二维数组内存布局
所以，在写代码时，要多想想CPU，多想想操作系统才能写出性能优秀的代码。
时间局部性
- 时间局部性简单说就是访问过的代码、数据还会马上被访问到。为什么有这个结论呢？你如果感兴趣的话，可以看看你家的代码库中，或者开源软件的源代码中，是不是循环语句最多？或者不较真的说，循环代码最重要。为什么呢？
1.1. 因为算法都是要被写成循环或者递归形式的，不能用循环或者递归实现的算法不存在；
1.2. 这叫做程序的可停止性，这是图灵的主要功绩，图灵证明了任何计算都是可以用图灵机在有限步里面完成的。 -
循环代码就是时间局部性原理的基础。因为一个循环如果被CPU cache住了，就不用去内存加载了，从而提高了程序的运行效率。
3、启示——性能好的程序往往会写成循环的代码而不是递归。递归函数调用是高级语言的特性，但是它涉及到代码从一个点反复的跳转到不同的代码段，会导致cpu cache bouncing，程序性能会波动；
循环vs递归
- 启示2——人越容易看懂的代码对机器也越不友好。在算法设计中，递归法是人能看懂的最好编码的形式，但是实际运行的效率不高；相反如果写成循环形式，人虽然理解起来有困难，但是机器十分友好，如：
void preOrder1(BinTree *root) //递归前序遍历
{
if(root!=NULL)
{
cout<<root->data<<"";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
void preOrder2(BinTree *root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<"";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
所以还是那样，自然界的这种跷跷板很多，一个东西有好的方面也肯定有其不足之处，这是很正常的。
认识到事物的边界才算是真正认识到了它。
总结
计算机硬件与软件的性能都会受到局部性原理的限制，而局部性原理又分为空间与时间局部性两个维度，正是这两个约束（枷锁）使得我们的计算机世界长成了现在这个样子；而程序员懂得其中的基本概念，在写代码的时候能够有点印象就已经可以了。
网友评论