c的很多开源项目为何重度使用链表?

我是一个c小白,我过去学习过cpp。这个寒假开始阅读一些纯c语言的开源项目,发现都重度使用链表。 例如,libhv里面的timer,是最小堆,是使用链表实现的。

在c++中,对于顺序容器,是鼓励使用vector的,因为大多数场景vector具有更好的性能。但是c的项目,很少去实现一个vector,更多是使用链表,不怕这样会影响性能吗?

这就是砖石与房屋的关系了.

便于实现, 内存空间紧凑, 不是很多数据的情况下 O(n) 访问没什么感觉

你想用 vector 的话可以用这个 https://troydhanson.github.io/uthash/ 里面的 utarray

1 个赞

主要原因是 C 的标准库东西比较少,里面没有 std::vector 这种东西,所以大家都自己实现了。

但是多数 C 项目里实现的链表并不是类似 std::vector 的容器(无泛型),而是 intrusive 的。通过 container_of 很容易由 next 指针转换得到对应结构体的指针,依托于这点,其实现的链表相关 API, 如 list_add_element 之类的也可以很通用。如果对 intrusive list 感兴趣,可以看一下 linux 里的实现。

4 个赞

例如,libhv 里面的 timer,是最小堆,是使用链表实现的。

首先这里需要纠正一下。libhv 用最小堆来管理 timer 不假,但它并不是使用“链表”实现的。

通过阅读相关源码,可以看到,这个最小堆也是一个基于二叉树的实现,只不过这个二叉树是用指针来记录节点之间的关系,而不是用数组。

为什么采用这种方式来实现呢?这里可以给出一个 educated guess:

  1. 无需为最小堆额外进行内存管理(包括初始化、扩容、释放),实现成本低。因为二叉树结点的内存空间是和 timer 对象的其他成员一同分配的,使用时赋值即可。
  2. 和最小堆的数组实现相比,时间复杂度是相同的,不存在显著的性能缺陷。虽然由于 spatial locality 等原因,实际性能会差一些,但相对于其他影响性能的昂贵操作(比如频繁的系统调用,拷贝 buffer 等),往往可以忽略不计。毕竟我们编写网络应用时,一般不会存在大量 timer 同时 pending 的场景。

那我们可不可以用数组实现的最小堆来管理 timer?当然可以。比如 swoole 的 heap 实现,就是用的数组。如果有兴趣,可以去看一下其他的网络 I/O 库,比如 libev、libuv、Boost.Asio 等,都是如何管理 timer 的。

另外,作为 libhv 的贡献者之一,这里不得不吐槽一句:libhv 的代码风格和组织形式不是很优雅。当初我尝试改它代码的时候,内心是崩溃的。。如果作为初学者,不建议阅读,容易对自己的代码风格起到负面影响。建议先从我上面提到的那几个库读起。

很少去实现一个 vector,更多是使用链表,不怕这样会影响性能吗?

上面也说过,当高性能不是首要目标时,出于一些其他的考虑,会选用一些性能不是那么好的实现。

再举几个例子吧。

众所周知,Bash 的数组[1]的底层实现是链表,而不是“内存连续的线性表”。这大概是因为 Bash 从语言层面,并不需要预先指定数组大小,也不要求数组元素是连续的。

所以如果有人这样写:

declare -a arr
arr[65535]='holy'
arr[2147483647]='shit'

如果 Bash 是采用传统的内存连续的数组实现,对于这种“稀疏”的数组,就不得不浪费大量内存,很容易就会 OOM。

所以,作为实现者,我们需要考虑下面几个问题:

  1. 要不要为这种“不负责任”的写法优化?
    • 当然要!shell 就是要做到能“一把梭”,让不怎么懂编程的普通人也能轻松使用。随便定义了几个数组就 OOM 了怎么成?
  2. 采用其他数据结构,所导致的数组随机访问的性能下降,是否是可以接受的?
    • 没问题!没人会在 shell 里面进行计算密集的操作,这些工作应该交给其他编程语言去做,然后提供 cli 供 Bash 调用。因此,时间复杂度为 O(n) 的数组随机访问也是可以接受的。

这下,该怎么实现就很明了了。

有的同学看到这里可能会反驳,如果用哈希表实现不是更好么?用下标做 key,就可以做到 average O(1) 了。

没错,而且很多语言的解释器就是这样实现数组的。

比如,PHP[2] 的 associative array 在元素下标均为不小于 0 的整数且连续时(用一个值为 HT_IS_PACKED 的 flag 标识),则会连续地储存。如果某次插入导致数组下标不连续,就会转化为哈希表实现。

还有 Tcl 的数组,底层完全是哈希表实现,不管 key 是不是整数。值得一提的是,这里用到的哈希函数是特别为 digit string 优化的,对于纯数字字符串的 key 占多数的场景下,分布比常用的 FNV 等哈希函数要好一些。当然,Tcl 中也有内存连续的数组:list[3]

这些解释器选择了较低效的数组实现,究其原因,无非是要放宽数组在空间上存在的物理限制,从而使得它的使用更加灵活。

引申开来,我们在进行软件开发时的其他场景下,也经常要在性能和便利之间找到一个平衡点。这是需要具体问题具体分析的。


  • [1] 这里指的是 Bash 的 indexed array。字符串下标的 associative array 的底层实现是哈希表。
  • [2] 这里特指 PHP 7.x,因为其他版本的 PHP 源码我没读过,不知道有没有发生过改变。
  • [3] 只在 8.x 版本的现代 Tcl 中,list 才是这样实现的。7.x 版本的 Tcl 的 list 实现非常朴素,每次使用需要现 parse,而且并不会将 parse 结果作为 internal rep 缓存起来。因此 lindex lset 之类的函数是非常低效的。在 Guile 被提上日程的前夕,RMS 曾经锐评 Tcl,其中一点,就是 Tcl 没有内存连续的数组。
27 个赞

因为大部分情况下不会收到 O(n) 访问速度的限制。

不能这么说,举个例子:Emacs 内置有 vector,却还用 cons 来实现计时器。

swoole的heap数组竟然就是一个二级指针,然后实现std::vector的二倍扩容。我之前一直想着用c语言怎么去封装一个动态数组,原来可以这么暴力实现 :joy:

说实话,我不敢这样做。。

也有像golang这种resize之后用户还得把返回的新数组重新赋值给原变量的

适用场景多,可扩展性好