你应该知道的C语言Cache命中率提升法

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;
}

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

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

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

$ ./a
58(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个链结点数组，然后将数组元素构建成了一条单链表。链表节点数与上一段代码中构建的链表节点数是一致的。

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

$ ./b
5(us)

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

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

分析与结论

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

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

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

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

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

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

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