[作品] Ｃ語言 型別安全的列表容器 (OpenGC3: linked list)

[DonaldTrunnp (The US President)]

Ｃ語言雖然缺乏語言級別的多型，但是還是能透過巨集的形式來呈現
其中最著名的不外乎是 Linux Kernel 中的 offsetof() 跟 container_of()
由於Ｃ語言一直缺乏一個高階抽象且型別安全的高效能容器
於是我決定開始著手重造一個比現有的輪子更好的輪子（咦？

概念上是這樣的：
所有的巨集都在編譯時期展開，因此編譯器中的優化器能更好地安排暫存器的使用
內部的實作都沒有不安全的型態轉換，所以既是型別安全的也是多型的 (polymorphic)

以下是與現有的 C 容器以及 C++ STL 實作的比較
在記憶體使用上插入 32 位元整型只要其他的一半：http://imgur.com/a/jKp7q
甚至在速度方面也比之中最快的 STL 還要快上 15% (Clang/LLVM) ~ 25% (GCC)

當然擁有直覺的界面的也是很重要的，以下是一個簡單的範例說明如何用它排序 struct：

#include "ccc/ccxll.h"
#define COMPAR_STR(a, b) (strcmp(DREF(a)->name, DREF(b)->name) <= 0)

struct ptt_board  {
    char *name;  int year_est;
}   rec[] = { {"Gossiping", 1999}, {"C_and_CPP", 2000}, {"WomenTalk", 2003} };

ccxll(struct ptt_board *) list;                // 宣告一個的指向結構指標的列表
ccxll_init(list);                              // 對剛剛宣告的列表初始化

for (int cnt = 0; cnt < 3; cnt++)
    ccxll_push_back(list, rec + cnt);          // 將指針們依序插入至列表的後方

ccxll_sort_extd(list, COMPAR_STR);             // 根據比較器來排序結構中的字串

CCXLL_INCR_AUTO(prec, list)                    // 正向遍歷列表並印出所有的元素
    printf("%s: EST. %d\n", (*prec)->name, (*prec)->year_est);

ccxll_free(list);                              // 別忘了手動銷毀剛剛建立的列表

如果好奇有關實作細節的 或是 覺得很有趣也很實用的話 please click a star! 以下是
「OpenGC3 的 GitHub Repository: https://github.com/kevin-dong-nai-jia/OpenGC3」

無論如何，期待大家的回覆，我很樂於傾聽大家的建議噢～（燦笑

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.51.165
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1483341336.A.75F.html
→ uranusjr: We will build a wall and C++ is gonna pay for it
推 CaptainH: 樓上XDD
※ DonaldTrunnp:轉錄至看板 Programming
推 descent: 請問記憶體比較圖是怎麼做的?                            01/02 22:31
那是用 Gnuplot 畫的～
推 descent: 可以分享怎麼測量記憶體使用率的嗎?
Fork child process 搭配 pmap: ./mem-trace COMMAND [ARGS]
https://gist.github.com/kevin-dong-nai-jia/a4aebf788c133f0e042fb4235d2759e6
推 shec1213: Make C Language great again
C plus plus is fired. ;)
→ final01: 做的比C++還威...？
在大部分的情況下都有較好的表現 唯一的比較嚴格的是 iterator invalidation rules
甚至搭配 GCC extension __builtin_prefetch() 能達到 30% 以上 speed up (Xeon E3)
但事實上 LL cache load 的速度完全比不上 iterate 的速度 但還是有機會 cache hit
推 MIKEmike07: wow Cool 蠻厲害的
推 CodingMan: 推推
推 andrenvq57: 川普會寫c ＠＠我跪
歐巴馬學會之後教我的 >///<
推 Sidney0503: 只能推了
推 soso7885: 推推
推 descent: 感謝說明記憶體使用率
→ happierway: 推!!
推 Sirctal: E3 1230v2再戰10年!!!
→ DonaldTrunnp: 但是恐怕要再換主板 才能再戰十年 XD
推 shadowjohn: 太猛啦!
→ HolyBugTw: 要朝聖啊～
推 petingo: 猛
推 Samuel: 猛!!
推 bluesoul: 雙向還是單向？
→ DonaldTrunnp: 目前僅僅實作的是雙向異或列表 普通雙向列表努力中
→ bluesoul: 這樣一來，比較並不公平
→ DonaldTrunnp: 確實是有些不公平 但是異或鍊表有更高的計算複雜度
→ DonaldTrunnp: 所以用同樣的方法製作雙向鍊表容器速度理論上會略快
→ DonaldTrunnp:  而記憶體使用量會略增些 具體的結果要實作完才知道
→ bluesoul: 指標的部分至少就是兩倍用量，另外有比較iterate的速度
→ bluesoul: 差嗎？
應該是至多兩倍的記憶體用量：(2 * ptr + val) / (1 * ptr + val) < 2

測量的結果如下：
　　　　　　  　　　　 　libCCC     C++ STL
遍歷  連續  記憶體空間  ~ 0.10 s   ~ 0.05 s   (幾乎不會有 cache miss)
遍歷 不連續 記憶體空間  ~ 1.51 s   ~ 1.49 s   (多出來的是 cache miss penalty)

確實需要多一點點的計算才能完成迭代器的遍歷，但是！！！
那個因計算多出來的量 (5e-26 s/elem) 遠遠不及快取未中的的懲罰 (1.5e-24 s/elem)
→ bluesoul: 我的意思是指標的部分是兩倍，因為用了兩個
→ bluesoul: 另外xorlinklist 在使用上有很大的限制，如果要比較兩
→ bluesoul: 個東西，至少要建立在功能是相同的情況
→ bluesoul: 另外請問一下，如何造出連續不連續記憶體的例子？
→ DonaldTrunnp: 插入亂數 接著排序 最後再遍歷 就可以了
→ DonaldTrunnp: 雙向鏈表的部分 我會再努力生出來的 這要一點時間
→ bluesoul: 感謝你的回答，很期待新的版本
※ 編輯: DonaldTrunnp (122.116.185.23), 04/05/2017 17:24:31