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

看板C_and_CPP作者DonaldTrunnp (The US President)時間7年前 (2017/01/02 15:15)推噓14(14推 0噓 19→)

留言33則, 18人參與討論串1/1

Ｃ語言雖然缺乏語言級別的多型，但是還是能透過巨集的形式來呈現其中最著名的不外乎是 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

01/02 15:52, , 1^F

01/02 15:52, 1^F

推

CaptainH

01/02 15:56, , 2^F

01/02 15:56, 2^F

※ DonaldTrunnp:轉錄至看板 Programming 推 descent: 請問記憶體比較圖是怎麼做的? 01/02 22:31 那是用 Gnuplot 畫的～

推

descent

01/02 22:46, , 3^F

01/02 22:46, 3^F

Fork child process 搭配 pmap: ./mem-trace COMMAND [ARGS] https://gist.github.com/kevin-dong-nai-jia/a4aebf788c133f0e042fb4235d2759e6

推

shec1213

01/02 23:04, , 4^F

01/02 23:04, 4^F

C plus plus is fired. ;)

→

final01

01/03 00:24, , 5^F

01/03 00:24, 5^F

在大部分的情況下都有較好的表現唯一的比較嚴格的是 iterator invalidation rules 甚至搭配 GCC extension __builtin_prefetch() 能達到 30% 以上 speed up (Xeon E3) 但事實上 LL cache load 的速度完全比不上 iterate 的速度但還是有機會 cache hit

推

MIKEmike07

01/03 02:57, , 6^F

01/03 02:57, 6^F

推

CodingMan

01/03 12:33, , 7^F

01/03 12:33, 7^F

推

andrenvq57

01/03 18:17, , 8^F

01/03 18:17, 8^F

歐巴馬學會之後教我的 >///<

推

Sidney0503

01/03 20:08, , 9^F

01/03 20:08, 9^F

推

soso7885

01/03 21:18, , 10^F

01/03 21:18, 10^F

推

descent

01/03 21:28, , 11^F

01/03 21:28, 11^F

→

happierway

01/04 02:14, , 12^F

01/04 02:14, 12^F

推

Sirctal

01/04 23:06, , 13^F

01/04 23:06, 13^F

→

DonaldTrunnp

01/04 23:57, , 14^F

01/04 23:57, 14^F

推

shadowjohn

01/05 10:40, , 15^F

01/05 10:40, 15^F

→

HolyBugTw

01/05 10:46, , 16^F

01/05 10:46, 16^F

推

petingo

01/07 02:50, , 17^F

01/07 02:50, 17^F

推

Samuel

01/07 15:01, , 18^F

01/07 15:01, 18^F

推

bluesoul

01/11 16:01, , 19^F

01/11 16:01, 19^F

→

DonaldTrunnp

01/11 17:33, , 20^F

01/11 17:33, 20^F

→

bluesoul

01/12 02:48, , 21^F

01/12 02:48, 21^F

→

DonaldTrunnp

01/12 09:06, , 22^F

01/12 09:06, 22^F

→

DonaldTrunnp

01/12 09:06, , 23^F

01/12 09:06, 23^F

→

DonaldTrunnp

01/12 09:06, , 24^F

01/12 09:06, 24^F

→

bluesoul

01/12 13:05, , 25^F

01/12 13:05, 25^F

→

bluesoul

01/12 13:05, , 26^F

01/12 13:05, 26^F

應該是至多兩倍的記憶體用量：(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

01/13 02:02, , 27^F

01/13 02:02, 27^F

→

bluesoul

01/13 02:04, , 28^F

01/13 02:04, 28^F

→

bluesoul

01/13 02:04, , 29^F

01/13 02:04, 29^F