2

在阅读 FreeBSD 中的内核数据结构时，我偶然发现了MBuf. MBuf包含指向MBuf链中下一个的指针MBuf，实现了一个链表。每个MBuf本身还包含特定于链接列表中该节点的数据。

我更熟悉将容器类型与值类型（考虑std::list，或System.Collections.Generic.LinkedList）分离的设计。我正在努力理解将容器语义嵌入数据类型的价值主张——获得了哪些效率？真的是为了消除节点实例指针存储吗？

4

4 回答 4

3

假设您有一个指向列表中节点的迭代器/指针。为了获取数据，您必须：

  • 从节点读取指向数据的指针
  • 取消引用您刚刚读取的指针并读取实际数据

另一方面，如果列表概念“嵌入”在您的数据结构中，您可以在单个内存操作中读取您的对象，就像它与节点本身一样。

分离列表节点及其数据的另一个问题是列表节点本身很小（通常只有 2 或 3 个指针）。因此，在内存中保留如此小的结构的内存开销可能很重要。你知道——诸如new或malloc实际上消耗的内存比分配的更多的内存——系统使用它们自己的树结构来跟踪内存在哪里是空闲的，哪里是空闲的。

在这种情况下，将事物分组到单个分配操作中是有益的。您可以尝试将多个列表节点保存在小包中，或者您可以尝试将每个节点与其分配的数据连接起来。

类似的策略可以在侵入式指针（相对于共享指针）中看到，或者std::make_shared将对象和智能指针数据打包在一起。

zett42 做出与节点数据std::list<T>保持一致的注释。T这实现了我上面解释的单个内存块，但有一个不同的问题：T不能是多态的。如果你有一个类A和它的导数B，那么node<B>就不是 的导数node<A>。如果您努力插入B，std::list<A>您的对象将：

  • 在最好的情况下，导致编译错误（没有构造函数A::A(const B&)）
  • 在最坏的情况下，静默切片 B，仅将表示的部分复制A到节点中。

如果您想在单个列表中保存多态对象，一个典型的解决方案是实际拥有std::list<A*>而不是std::list<A>. 但是你最终得到了我上面解释的额外间接。

另一种方法是制作一个侵入式列表（例如boost::intrusive::list），其中节点信息实际上是A对象的一部分。然后每个节点都可以是A没有问题的导数。

于 2017-03-04T17:57:12.250 回答
2

侵入式链表的一大优点是您可以创建一个预先存在的对象列表，而无需任何新的分配。要使用 std::list 指针执行此操作将需要内存分配。

Boost 有一个具有使用理由的侵入式列表实现。http://www.boost.org/doc/libs/1_63_0/doc/html/intrusive.html

于 2017-03-04T19:18:14.567 回答
0

获得了哪些效率？真的是为了消除节点实例指针存储吗？

我会说更少的缓存未命中，然后更好的整体性能（即使链表通常不是缓存友好的数据结构）。
这样一来，您就不必再遵循一个指针来在内存中的某个位置找到您的数据，并将它们带到您的处理器附近以供每个节点使用。
此外，如果您在内存的连续区域中构建节点并使用几个指针管理它们（让我们称它们为空闲列表和使用中的列表，听起来很熟悉吗？），您可以在以下方面得到提升性能（至少只要列表不包含很多项目，否则风险是在内存中来回跳转）。在这种情况下，插入和删除具有恒定的时间（当然，除非您必须先搜索列表中的节点才能插入特定位置），这是另一个优点。

于 2017-03-04T17:41:22.033 回答
0

侵入式列表的主要优点之一是您可以廉价地让单个节点属于多个列表。

例如，您可以拥有以 3 种不同方式排序的项目集合，对应于 3 个不同列表中的条目。例如，这将非常笨拙std::list。

正如@doron 所提到的，我认为的另一大优势是，一旦您自己创建了对象，列表管理就需要 0 次分配。

Boost 对侵入式与非侵入式数据结构进行了一些体面的讨论，各有利弊。

于 2021-10-11T23:57:03.543 回答