统一的侵入式链表

「完全拒绝UB是缺乏工程实践的表现」 ——TypeCombinator

前言

去年，我在写下了在purecpp上的第一篇文章——《统一的侵入式链表》，文章里最初的原型是几年前是使用C语言实现的，一直躺在我的私人仓库里吃灰。直到去年我在做调度器优化的相关工作的时候我才回想起来，于是将其拿出来用C++改写，并做了一些尝试和探索（见GitHub仓库uit），通过这次分享和提问，我得到了ykiko迅速且精准的回答，也意识到了这个idea和C++标准之间的矛盾，遂弃坑了一段时间，但是，终极问题的种子一直深埋脑海——如何让这个idea能够work呢？

在后续的日常开发中，我又有了新的思路，实践之后，先前无法通过的测试均能在三大编译器上通过，当然其中过程也并非一帆风顺，哄了Clang和GCC好几小时，这两位才让我构造的测试通过，至于MSVC嘛，向来情绪稳定，毫无意外地通过了测试。需要说明的是新方案不仅在用法上更灵活，也没有引入任何额外分支或其他消耗，且不需要加任何额外的编译选项或是在源码中加一些属性，在最高优化等级下，三大编译器均可通过所有测试！

不过，新方案的代码暂时没有公开，原因之一是它仍不完美，总体上，UB只是减少了，而不是完全消失，未来随着测试项新增或编译器更新仍有可能出现测试不通过的情况。不得不说，对于新的方案，我还是很有信心的，即使真的出现问题，我想我还是有能力修复的。

GitHub没法在公开的仓库上建立私有分支，新方案的代码最初躺在专门用于做各种实验的私人仓库中，但这个仓库不方便公开，在知乎上更新自答时，我建了一个私人仓库uit_ng，待到时机合适再公开吧，如果有足够的人感兴趣话，这也是我的考量之一。

回顾

统一的侵入式链表使用了一种名为mock_head的技巧，通过该技巧可以将4中不同的链表统一起来，不过随着后来我在仓库中加入的侵入式平衡二叉树——SBT和WBT，现在，我有点后悔取mock_head这个名了，改名为mock_sentinel会契合得多！不过这不是重点，purecpp上的文章由于没放图片，可能不易于理解，这里再结合图片重新介绍一下。

先用一句话解释mock_head，即复用头节点空间去模拟哨兵节点，统一头节点和数据节点的访问。为说明这一技巧，我将以最容易的单链表开始，示意图如下：

如上图所示，head减去数据节点中right字段的偏移即可得到mock_head，这样mock_head与数据节点能以相同的方式访问right字段，我们获得了统一访问的能力！毫无疑问，这种操作是UB，且会引入多种违反，但是我想说的是完全拒绝UB是缺乏工程实践的表现，为了极致性能必须要有所权衡，没有一种模型能够应对所有情形，C/C++的某些极致性能其实是用UB换来的！

字段减偏移的操作不就是linux内核源码中赫赫有名的container_of吗？没错！不同的是linux内核源码是将container_of作用于数据节点，而本文提到的mock_head则是将container_of作用于头节点，为了简化讨论，我将用C语言单链表来描述，代码（完整的放在compiler explorer上）如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <stdint.h>
#include <stdio.h>
#include <stddef.h>
struct node {
    int sn;
    struct node *next;
};
static struct node *head = NULL;

void push_front(struct node *n) {
    n->next = head;
    head = n;
}

#define container_of(_field_, _type_, _member_)   
    ((_type_ *) ((size_t) (_field_) -offsetof(_type_, _member_)))

#define MOCK_HEAD(_field_, _type_, _member_) container_of(_field_, _type_, _member_)

struct node *remove_with_mock_head(struct node *n) {
    struct node *prev = MOCK_HEAD(&head, struct node, next);
    for (struct node *cur = prev->next; cur != NULL;) {
        if (cur == n) {
            prev->next = cur->next;
            return cur;
        }
        prev = cur;
        cur = prev->next;
    }
    return NULL;
}

以上代码可以看出，mock_head能直接使用container_of实现，以上节点删除代码与linux内核源码中使用二级指针删除节点的代码在形式上是一致的，这里再列出使用二级指针删除节点的代码作为对比，帮助理解，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct node *remove_with_in_linux(struct node *n) {
    struct node **prev = &head;
    for (struct node *cur = *prev; cur != NULL;) {
        if (cur == n) {
            *prev = cur->next;
            return cur;
        }
        prev = &cur->next;
        cur = *prev;
    }
    return NULL;
}

可以看到，使用二级指针也能将头和数据节点的访问统一起来，对于单链表，使用mock_head相对于二级指针没有代码复杂度和性能上的优势，但是，如果将mock_head应用到其他形式的链表，并将语言切换到C++呢？像stdexec的这种方式实现intrusive_queue由于头节点和数据节点访问不统一，需要对边界情形做额外判断，摘取其push_back代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void push_back(_Item* __item) noexcept {
    STDEXEC_ASSERT(__item != nullptr);
    __item->*_Next = nullptr;
    if (__tail_ == nullptr) {
        __head_ = __item;
    } else {
        __tail_->*_Next = __item;
    }
    __tail_ = __item;
}

如果以上代码改用mock_head实现呢？摘取与之等价的uit的idslist的push_back实现如下：

1
2
3
4
5

void push_back(T *node) noexcept {
    (node->*M).right = nullptr;
    (head.left->*M).right = node;
    head.left = node;
}

可以看到，使用mock_head之后，以上代码没有任何分支！为什么可以这样呢？核心原因在于链表为空的处理不一样，示意图如下：

链表为空时，left并没有指向空，而是指向了mock_head，这样，在链表为空时也能通过left字段去访问到right字段，所以，空和非空idslist的push_back处理被统一了，对于非空的idslist示意图如下：

需要说明的是stdexec的intrusive_queue的pop_front方法调用是需要在外部判空的，而uit的是在内部判空的，这里不要混淆！ idlist（双链表）也采用了类似的技巧，示意图如下：

链表为空时，right和left都指向了mock_head，通过这种技巧，idlist能获得和linux内核链表形式相同的处理代码，比如insert和remove方法，代码实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

static void insert(T *node, T *left, T *right) noexcept {
    (node->*M).right = right;
    (node->*M).left = left;

    (left->*M).right = node;
    (right->*M).left = node;
}

static void remove(T *left, T *right) noexcept {
    (left->*M).right = right;
    (right->*M).left = left;
}

同样的，不需要使用任何分支！更为关键的是，由于这些维护链接关系的指针是直接指向节点的，用户不再需要像linux内核链表那样用container_of去还原数据节点，这消除了对用户代码的侵入！

C++侵入式链表的各种实现已经很多了，广为人知的boost的intrusive不必多说，nodejs也用到了侵入式链表，位于src/util.h文件中，不过里面只实现了一个双链表，其实现思路与linux的内核链表是一致的，所以也使用了会在C++中引入UB的container_of。那么，要在C++中实现linux那种形式的侵入式链表，用继承和static_cast代替container_of是否可行呢？当然可行！但问题是，继承真的很不好用！虽然C++的很多技法都和继承绑定了，但实践开发中，我的看法是能不用继承就不要用！如果抛弃以上方案，改用stdexec的方式实现呢？虽然不会引入UB，但实现起来需要做额外的边界条件判断，这必然引入额外开销！

最后，还剩下一个isdlist没有介绍，这等价于linux中的hlist，该链表主要用于实现哈希表，当持有节点需要删除时，如果使用单链表，则需要遍历拿到前驱才能删除，但如果改用双链表，则头节点需要两个指针的空间，而使用isdlist则只需要占用一个指针的空间，isdlist 的示意图如下：

linux中的hlist的数据节点的前驱是一个二级指针，指向的是前驱的后继指针，特殊的首数据节点，则其前驱指针则指向了链表的头节点；isdlist由于使用了 mock_head，二级指针不再被需要，前驱指针直接指向前驱节点，特殊的首数据节点，则其前驱指针指向了mock_head。

至此，4种侵入式链表(islist，idslist，idlist和isdlist)已回顾完毕！其优缺点总结如下：

• 优点

  • 简单易懂的代码
  • 更少的分支和更好的性能，比如，idslit的push_back方法没有任何分支
  • 二级指针不再被需要，isdlist也不例外
  • 真正的零成本抽象
  • 没有使用宏

• 缺点

  • 会引入UB，且有多种违反
  • isdlist，idslist和 idlist是自引用类型， isdlist和 idlist 是move-only的（这不是大问题，可以用额外的模板参数控制是否启用mock_head，以避免自引用和move-only带来的不便）

总结

当前公开的仓库uit只是一个展示mock_head这一技巧的实验代码，非-O0优化等级下，单元测试不能完全通过，不具备实用条件，而可实用的仓库uit_ng现在还没有公开，虽然暂时未公开，但是传达出mock_head是可以行得通的技巧这一信息，我想在现阶段已经足够！

使用mock_head是可以带来性能提升的，虽然不多，且会引入UB，但权衡之下，我认为这是值得的，毕竟，有得必有失！从我研读过的诸多C++开源项目来看，追求性能而有意引入UB项目也并不少，正如我前面所说，完全拒绝UB是缺乏工程实践的表现，C++的模型是有边界，有极限的，总有一些情形是照顾不到的，部分情形可能随着C++语言版本更新被所纳入的新特性所覆盖，但有些情形则是永远不会被C++标准委员会所采纳的，对于这种情况，如果收益值得，只要有足够的测试覆盖，是不需要有过多担心的。

前段时间，我还尝试过使用Zig语言上使用mock_head的原始方案，经过实践，Zig语言也表现出只能在Debug模式下通过测试，其他模式则测试失败的现象，Zig语言看起来没有C++的生命周期和严格别名的这样的限制，但是对于是否有对象的边界检查以及指针的其他限制，我不是太清楚，毕竟我只学了一天！从结果来看，也是违反了Zig语言的某些规则，有人推测是因为Release模式使用了LLVM后端的缘故，当前Zig开发的后端只用在了Debug模式，等Zig彻底去除了LLVM后端再测试吧！不过，LLVM后端累积那么多年的PASS，支持那么多平台，想要替代，也许得等到猴年马月了！

当前，C++已经能实现并满足我的一切所想，虽然特性复杂，偶尔让人在一些细节上耗费时间和精力，但每次都是能带来收获的，这也是C++的魅力所在，我再也无需纠结C++侵入式链表的性能问题了！