C语言因其对内存的精细控制和高执行效率而在业界长盛不衰。但是，同样的语言不同的用法导致写出的代码执行效率可能会有很大差异（数量级上的差异）。

今天码哥给大家演示一种因cache命中率导致的效率差异示例。场景非常简单，就是单链表的遍历。

或许有的人会有疑问，单链表的遍历效率还会和cache命中有关吗？

码哥先不透露，我们先来看一段代码：

代码一/* a.c */#include <stdio.h>#include <stdlib.h>#include <sys/time.h>typedef struct chain_s { struct chain_s *next;} chain_t;int main(void){ int i; chain_t *arr = NULL, *c, *p; struct timeval begin, end; /*build*/ for (i = 0; i < 8192; ++i) { c = (chain_t *)malloc(sizeof(chain_t)); if (c == NULL) exit(-1); if (i % 8 == 0) { if (arr == NULL) { arr = p = c; } else { p->next = c; p = c; } } } /*clean cache*/ for (i = 0; i < 999999; ++i) { c = (chain_t *)malloc(sizeof(chain_t)); if (c == NULL) exit(-1); c->next = NULL; } /*scan*/ gettimeofday(&begin, NULL); for (c = arr; c != NULL; c = c->next) ;/*do nothing*/ gettimeofday(&end, NULL); printf("%lu(us)\n", (end.tv_sec*1000000+end.tv_usec)-(begin.tv_sec*1000000+begin.tv_usec)); return 0;}

代码很简单，一共分为三部分：

构造单链表，我会分配8192个链表节点，但是只有可以被8整除的节点才会加入链表，换言之，有1024个节点加入链表。因为构造链表时必然会存在cache缓存，我们额外分配999999个节点，用来尽可能的洗掉构造时的缓存。遍历链表并统计时长。

那么这段代码在码哥的虚拟机环境中运行的结果如下：

$ ./a58(us)

这个时间是多次执行程序后找出的平均时间。

那么，问题来了，这样的链表遍历效率是否有可能再提升呢？

答案是，有的。我们来看下一段代码：

代码二/* b.c */#include <stdio.h>#include <sys/time.h>#include <stdlib.h>typedef struct chain_s { struct chain_s *next;} chain_t;int main(void){ int i; chain_t arr[1024], *c; struct timeval begin, end; /*build*/ for (i = 0; i < sizeof(arr)/sizeof(chain_t); ++i) { if (i < sizeof(arr)/sizeof(chain_t)-1) arr[i].next = &arr[i+1]; else arr[i].next = NULL; } /*clean cache*/ for (i = 0; i < 999999; ++i) { c = (chain_t *)malloc(sizeof(chain_t)); if (c == NULL) exit(-1); c->next = NULL; } /*scan*/ gettimeofday(&begin, NULL); for (c = arr; c != NULL; c = c->next) ;/*do nothing*/ gettimeofday(&end, NULL); printf("%lu(us)\n", (end.tv_sec*1000000+end.tv_usec)-(begin.tv_sec*1000000+begin.tv_usec)); return 0;}

同样的链表结构，同样的缓存清除和遍历代码。不同之处在于构建部分。这一次，我们是在栈上创建了1024个链结点数组，然后将数组元素构建成了一条单链表。链表节点数与上一段代码中构建的链表节点数是一致的。

那么这段代码中遍历链表的时间又是多少呢？

$ ./b5(us)

同样是执行多次程序的平均时间。

可以看到，两段代码足足差了一个数量级。但是相信大家在看完代码后也明白了差异缘何。

分析与结论

效率的提升源自于链表的构建，确切的说，源自于链表节点地址的连续性。

在第二段代码中，链表节点是从一片连续空间中顺序取出的，因此扫链表与顺序访问数组元素并无区别。当我们访问数据时，如果数据未在缓存中命中，那么是会将该数据及其后一部分（与cache line大小有关，不额外展开了）数据加载进cache中的。因此，访问一个数据会将其后连续的一部分数据访问效率连带提升。

这两段代码在我们实际项目中又有何启发呢？

我们常见的高并发网络中，即便用到链表，但链结点地址通常都是不连续的，因为连接的释放和分配时机相对随机。

那么我们有没有可能尽可能让这些节点保持连续性呢？

当然可以，这就是为什么要构造内存池的一个原因了。让一类需要高效访问的结构走内存池进行统一管理，可以大幅提升程序执行效率。

当然，内存池还有额外的好处就是可以统一释放回收内存，例如Nginx中，经常看到我们ngx_alloc，但不见free的缘由，因为在连接断开时，Nginx做了统一的释放。

欢迎喜欢的朋友关注码哥，也可以在下方给码哥留言评论。谢谢观看！