C++ 侵入式链表总结

发表于 2022-06-05 更新于 2024-06-09 分类于 Data Structure

总结侵入式链表的主要优缺点和在 C++ 语言参考实现

最近突然想要看一看性能相关的优化，正好看到了侵入式链表这部分，在此做一个简单的总结。

这里简单的说一下什么是侵入式链表，方便读者快速决定是否需要继续读下去。一个常见的非侵入式链表是这样的：

template <typename T>
struct ListNode {
  ListNode* prev;
  ListNode* next;
  T value;
};

可以说，非侵入式链表的实现方式是，链表节点中包含数据。侵入式链表的实现方式与之相反，是业务数据结构中包含链表节点结构：

template <typename T>
struct IntrusiveListNode {
  IntrusiveListNode* prev;
  IntrusiveListNode* next;
  T* owner;
};

struct UserData {
  // ...
  InstruiveListNode list;
};

侵入式链表的常见使用场景是对比 std::list<T*> 这样的使用方法的，其他场景一般不适用于侵入式链表。例如在实现 LRU 时，需要把 entry 同时加入 HashMap 和 List 中，使用前者提供 $O(1)$ 复杂度的查询，使用后者维持 Recency 序关系。由于一个值对象不能同时属于两个非侵入式容器，所以其中一个容器必然保存的是指针或者迭代器。此时，拿到一个 Entry 的时候就可以操作这个 Entry 所在的链表，非常方便，而且效率也比较高。

侵入式的好处

关于侵入式和非侵入式的对比，见 https://www.boost.org/doc/libs/1_79_0/doc/html/intrusive/intrusive_vs_nontrusive.html

一般来说，大家都会优先选择使用非侵入式的实现。因为侵入式实现需要将一些逻辑耦合到业务代码中，因此为人所不喜。但是在背景介绍中提到的场景下，侵入式实现有显著的好处，从而使得侵入式实现被广泛的使用。我们在此不再强调侵入式与非侵入式的区别，主要考虑一下侵入式链表的优势有哪些。

更好的 Data Locality

std::list<T*> 在遍历的过程中还需要对 T* 进行解引用才能访问 T 内部的数据。但是侵入式链表的 next 和 T 内部的数据是放在一起的，因此无需额外的解引用。而且由于内存 layout 就是在一起的，所以也会获得更好的 Data Locality。

更友好的 API

对于侵入式链表，我们拿到数据就可以将这个节点从链表中摘除，而无需再去定位其 iterator，然后再去找到对应的容器 erase 这个 iterator。

脱离容器进行生命周期管理

最主要的应用场景是同一份对象需要在多个容器中共享，例如在背景介绍中提到的实现 LRU 的场景，又例如需要将同一份数据加入多个链表中。因此侵入式链表需要用户自己管理数据节点生命周期的特性在这里就成为了一个优点。

一些实现方式分析

Linux

https://github.com/torvalds/linux/blob/v5.18/include/linux/list.h

如其注释所说，其实现了一个双向循环链表。

circular doubly linked list

侵入式链表结构的定义见 https://github.com/torvalds/linux/blob/v5.18/include/linux/types.h

struct list_head {
  struct list_head *next, *prev;
};

使用上的相关方法见 https://github.com/torvalds/linux/blob/v5.18/include/linux/list.h

在使用时，以调度模块为例：

// https://github.com/torvalds/linux/blob/v5.18/kernel/sched/sched.h#L376
struct task_group {
  // 省略一些业务逻辑
  struct list_head list;
};

// https://github.com/torvalds/linux/blob/v5.18/kernel/sched/core.c

/*
 * Default task group.
 * Every task in system belongs to this group at bootup.
 */
struct task_group root_task_group;
LIST_HEAD(task_groups);

list_add(&root_task_group.list, &task_groups);

这里的问题在于 struct list_head 中的指针也都是 struct list_head 类型的，怎么拿到用户类型的数据？考虑到 C 语言中所有结构体内部数据都是按照约定好的 layout 排布的。我们可以通过 offsetof 计算偏移量来找到用户结构体的起始位置了，再进行一下类型强制转换就可以了。

// https://github.com/torvalds/linux/blob/v5.18/include/linux/list.h#L519

/**
 * list_entry - get the struct for this entry
 * @ptr:        the &struct list_head pointer.
 * @type:       the type of the struct this is embedded in.
 * @member:     the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
        container_of(ptr, type, member)

// https://github.com/torvalds/linux/blob/v5.18/include/linux/container_of.h#L17

/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:          the pointer to the member.
 * @type:         the type of the container struct this is embedded in.
 * @member:       the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({                            \
        void *__mptr = (void *)(ptr);                                 \
        static_assert(__same_type(*(ptr), ((type *)0)->member) ||     \
                      __same_type(*(ptr), void),                      \
                      "pointer type mismatch in container_of()");     \
        ((type *)(__mptr - offsetof(type, member))); })

注意，offsetof 只能对 Standard Layout 的类型起作用。例如 virtual inheritance 的场景就不适用。所以在 C++ 中使用这个技巧要十分谨慎。

https://stackoverflow.com/questions/1129894/why-cant-you-use-offsetof-on-non-pod-structures-in-c

Doom3

https://github.com/Edgarins29/Doom3/blob/d80c4d8341a35a8d9bc71324dcfc2be583295c03/neo/idlib/containers/LinkList.h

上面已经介绍了 Linux 是如何实现一个侵入式链表的，并且提出了这种方法对于 C++ 语言来说有一些限制，不能用于 non-standard layout 的数据结构。大部分情况下我们都不会遇到这样的限制，但是一旦真的遇到了该怎么解决呢？Doom 代码中也有一个类似的实现，其通过添加一个额外的 owner 成员来解决这一问题。

template< class type >
class idLinkList {
 public:
  // 省略

 private:
  idLinkList* head;
  idLinkList* next;
  idLinkList* prev;
  type*       owner;
};

使用的时候类似于这样：

class idEntity {
  idLinkList<idEntity> spawnNode;  // for being linked into spawnedEntities list
};

idEntity::idEntity() {
  spawnNode.SetOwner( this );
}

/*
================
idLinkList<type>::InsertBefore

Places the node before the existing node in the list.  If the existing node is the head,
then the new node is placed at the end of the list.
================
*/
template< class type >
void idLinkList<type>::InsertBefore(idLinkList &node) {
  Remove();

  next       = &node;
  prev       = node.prev;
  node.prev  = this;
  prev->next = this;
  head       = node.head;
}

/*
================
idLinkList<type>::AddToEnd

Adds node at the end of the list
================
*/
template< class type >
void idLinkList<type>::AddToEnd(idLinkList &node) {
  InsertBefore(*node.head);
}

ent->spawnNode.AddToEnd(spawnedEntities);

Boost Intrusive

https://www.boost.org/doc/libs/1_79_0/doc/html/intrusive/list.html

Boost 的侵入式容器为通用性做了很多考虑，搞得代码特别复杂。如果你的场景比较简单，个人建议还是谨慎考虑是否直接使用 Boost 的侵入式容器。如何需要混合使用多种类型的非侵入式容器（链表，哈希表，b树等等），再考虑一下要不要使用 Boost。

Boost 提供了两种制造侵入式容器的方法，一种和上面提到的做法差不多，就是使用 member hook，缺点就是不能处理虚继承关系；另一种则是使用 base hook，通过继承关系来注入侵入式容器的相关变量，然后通过继承时配置不同的 tag 来区分不同的侵入式容器。

总体来说，感觉 Boost 的做法要比上面强行加一个 owner 字段的方式要干净一些。因为用户在使用的时候，肯定就得为 Standard Layout 的对象使用 member hook，而对非 Standard Layout 的对象使用 base hook。而 base hook 是可以拿到 this 指针的，所以也就不需要 owner 字段存储 this 了。

Google QUICHE

https://github.com/google/quiche/blob/977f5bf82a47fb833ab8e5a5cea2c8a593fb6add/quiche/spdy/core/spdy_intrusive_list.h

这个实现和 Boost 的 base hook 差不多，但是因为不用考虑那么多 case，实现上要”干净”不少，而且目测和 STL 的兼容程度更高一些。