作者DonaldTrunnp (The US President)
看板C_and_CPP
标题[作品] Ｃ语言 型别安全的列表容器 (OpenGC3: linked list)
时间Mon Jan 2 15:15:33 2017
Ｃ语言虽然缺乏语言级别的多型，但是还是能透过巨集的形式来呈现
其中最着名的不外乎是 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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1483341336.A.75F.html
1F：→ uranusjr: We will build a wall and C++ is gonna pay for it01/02 15:52
2F：推 CaptainH: 楼上XDD01/02 15:56
※ DonaldTrunnp:转录至看板 Programming
推 descent: 请问记忆体比较图是怎麽做的? 01/02 22:31
那是用 Gnuplot 画的～
3F：推 descent: 可以分享怎麽测量记忆体使用率的吗?01/02 22:46
Fork child process 搭配 pmap: ./mem-trace COMMAND [ARGS]
https://gist.github.com/kevin-dong-nai-jia/a4aebf788c133f0e042fb4235d2759e6
4F：推 shec1213: Make C Language great again01/02 23:04
C plus plus is fired. ;)
5F：→ final01: 做的比C++还威...？01/03 00:24
在大部分的情况下都有较好的表现 唯一的比较严格的是 iterator invalidation rules
甚至搭配 GCC extension __builtin_prefetch() 能达到 30% 以上 speed up (Xeon E3)
但事实上 LL cache load 的速度完全比不上 iterate 的速度 但还是有机会 cache hit
6F：推 MIKEmike07: wow Cool 蛮厉害的01/03 02:57
7F：推 CodingMan: 推推 01/03 12:33
8F：推 andrenvq57: 川普会写c ＠＠我跪01/03 18:17
欧巴马学会之後教我的 >///<
9F：推 Sidney0503: 只能推了01/03 20:08
10F：推 soso7885: 推推 01/03 21:18
11F：推 descent: 感谢说明记忆体使用率01/03 21:28
12F：→ happierway: 推!! 01/04 02:14
13F：推 Sirctal: E3 1230v2再战10年!!!01/04 23:06
14F：→ DonaldTrunnp: 但是恐怕要再换主板 才能再战十年 XD 01/04 23:57
15F：推 shadowjohn: 太猛啦! 01/05 10:40
16F：→ HolyBugTw: 要朝圣啊～01/05 10:46
17F：推 petingo: 猛01/07 02:50
18F：推 Samuel: 猛!!01/07 15:01
19F：推 bluesoul: 双向还是单向？ 01/11 16:01
20F：→ DonaldTrunnp: 目前仅仅实作的是双向异或列表 普通双向列表努力中 01/11 17:33
21F：→ bluesoul: 这样一来，比较并不公平 01/12 02:48
22F：→ DonaldTrunnp: 确实是有些不公平 但是异或链表有更高的计算复杂度 01/12 09:06
23F：→ DonaldTrunnp: 所以用同样的方法制作双向链表容器速度理论上会略快 01/12 09:06
24F：→ DonaldTrunnp: 而记忆体使用量会略增些 具体的结果要实作完才知道 01/12 09:06
25F：→ bluesoul: 指标的部分至少就是两倍用量，另外有比较iterate的速度 01/12 13:05
26F：→ bluesoul: 差吗？ 01/12 13:05
应该是至多两倍的记忆体用量：(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)
27F：→ bluesoul: 我的意思是指标的部分是两倍，因为用了两个 01/13 02:02
28F：→ bluesoul: 另外xorlinklist 在使用上有很大的限制，如果要比较两 01/13 02:04
29F：→ bluesoul: 个东西，至少要建立在功能是相同的情况 01/13 02:04
30F：→ bluesoul: 另外请问一下，如何造出连续不连续记忆体的例子？ 01/13 02:14
31F：→ DonaldTrunnp: 插入乱数 接着排序 最後再遍历 就可以了 01/13 02:55
32F：→ DonaldTrunnp: 双向链表的部分 我会再努力生出来的 这要一点时间 01/13 02:57
33F：→ bluesoul: 感谢你的回答，很期待新的版本 01/13 19:48
※ 编辑: DonaldTrunnp (122.116.185.23), 04/05/2017 17:24:31