C語言因其對內存的精細控制和高執行效率而在業界長盛不衰。但是，同樣的語言不同的用法導致寫出的代碼執行效率可能會有很大差異（數量級上的差異）。

今天碼哥給大家演示一種因cache命中率導致的效率差異示例。場景非常簡單，就是單鏈表的遍歷。

或許有的人會有疑問，單鏈表的遍歷效率還會和cache命中有關嗎？

碼哥先不透露，我們先來看一段代碼：

代碼一

<code>/* a.c */
#include <stdio.h>
#include <stdlib.h>
#include 

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;
}/<stdlib.h>/<stdio.h>/<code>

代碼很簡單，一共分為三部分：

1. 構造單鏈表，我會分配8192個鏈表節點，但是隻有可以被8整除的節點才會加入鏈表，換言之，有1024個節點加入鏈表。
2. 因為構造鏈表時必然會存在cache緩存，我們額外分配999999個節點，用來儘可能的洗掉構造時的緩存。
3. 遍歷鏈表並統計時長。

那麼這段代碼在碼哥

<code>$ ./a
58(us)/<code>

這個時間是多次執行程序後找出的平均時間。

那麼，問題來了，這樣的鏈表遍歷效率是否有可能再提升呢？

答案是，有的。我們來看下一段代碼：

代碼二

<code>/* b.c */
#include <stdio.h>
#include 
#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;
}/<stdlib.h>/<stdio.h>/<code>

同樣的鏈表結構，同樣的緩存清除和遍歷代碼。不同之處在於構建部分。這一次，我們是在棧上創建了1024個鏈結點數組，然後將數組元素構建成了一條單鏈表。鏈表節點數與上一段代碼中構建的鏈表節點數是一致的。

那麼這段代碼中遍歷鏈表的時間又是多少呢？

<code>$ ./b
5(us)/<code>

同樣是執行多次程序的平均時間。

可以看到，兩段代碼足足差了一個數量級。但是相信大家在看完代碼後也明白了差異緣何。

分析與結論

效率的提升源自於鏈表的構建，確切的說，源自於鏈表節點地址的連續性。

在第二段代碼中，鏈表節點是從一片連續空間中順序取出的，因此掃鏈表與順序訪問數組元素並無區別。

這兩段代碼在我們實際項目中又有何啟發呢？

我們常見的高併發網絡中，即便用到鏈表，但鏈結點地址通常都是不連續的，因為連接的釋放和分配時機相對隨機。

那麼我們有沒有可能儘可能讓這些節點保持連續性呢？

當然可以，這就是為什麼要構造內存池的一個原因了。讓一類需要高效訪問的結構走內存池進行統一管理，可以大幅提升程序執行效率。

當然，內存池還有額外的好處就是可以統一釋放回收內存，例如Nginx中，經常看到我們ngx_alloc，但不見free的緣由，因為在連接斷開時，Nginx做了統一的釋放。

歡迎喜歡的朋友關注

閱讀更多 碼哥比特 的文章

關鍵字: 虛擬機 C語言 效率