浅谈侵入式容器

鉴于C++标准库并没有提供侵入式容器供我们使用,这里只简单梳理一下侵入式容器的特性

最简单的侵入式容器

先看一个最简单的示例:list_head

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

这是Linux提供的内核链表,一个最简化的侵入式容器

可以与非侵入式STL风格的实现对比一下

template <typename Tp>
struct ListNode {
    ListNode *prev, *next;
    Tp value;
    // ...
};

相比于STL风格的区别,可以看出list_head不维护value

使用的话是这种画风

struct Foo {
    int value;
    list_head link; // 指向另外两个Foo类的的list_head link
};

// 区别于
ListNode<int> bar; // 可以指向另外的&ListNode<int>

这就是侵入式容器的全部区别了吗?我们再琢磨一下

泛型支持

非侵入式的ListNode对于不同类型的value,需要提供真正意义上不一样的类型ListNode<T>

但是list_head并不需要维护多余的泛型typenamelist_head就是任意类型兼容的容器

ListNode<FoOO> n1;
ListNode<Foooo> n2;

也许对于C++并没什么,但是对于不支持泛型的语言来说这种设计绝对是个优势

另外从生成的实例类型来说,也可带来编译成本的减小

PS. 并不是说所有侵入式容器就会抛弃泛型,像boost::intrusive套餐就还是得带上typename

空间分配

STL的容器都是搭上allocator来维护内部element的分配/销毁,由于allocator是放在template上的(不考虑std::pmr),所以造成了allocator注定是无状态的(什么是无状态,简单点说就是用了等于白用),大部分情况来说,它就是一个new+ctor的解耦与抽象,问题就是new,不管怎样,它只有一种选择,看下面例子

template <typename Tp, typename Allocator>
struct List {
    ListNode<Tp> *mData; // 由Allocator分配
    // ...
};

大部分情况下,不管List是放在堆还是栈,mData分配的基本只能是在堆上,你没有选择的余地,因为allocator不能运行时更改,它的策略已经是编译时决定好了

相比之下,list_head是如何分配的,完全取决(绑定)于调用方FOooOoO,可以直接在栈上分配,也可以一并new FOooOoO放到堆上

struct FOooOoO {
    std::string name;
    int uid;
    list_head link;
};
auto pf1 = new FOooOoO(/*...*/);
FOooOoO f2(/*...*/);

分离的地址

前面提到new分配的问题,非侵入式容器也有缺点,它们可能会至少new两次

考虑new List过程

auto pList = new List<int>(/*size*/1, /*value*/ 100);

由于内部mData是额外分配的,因此&pListpList.mData指向是分离的

有什么问题?cache警察表示这样不好,因为这样不容易利用cache line,再抠门一点可认为多了一次(可能有系统调用的)函数调用开销

至于list_head是不需要考虑这些问题,空间本身是与调用方连续的

补充:并非如此

难道这个缺点,非侵入永远没法克服吗?

不是的,可以看下智能指针std::make_shared过程如何处理这种分离的分配问题,它可以做到Tp和引用计数块绑定在一起连续分配,当然这很需要技巧性

引用计数老问题

前面提到智能指针,那就顺便提一个非侵入式智能指针的经典错误

auto pValue = new F00(/*...*/);
std::shared_ptr<F00> p1(pValue);
std::shared_ptr<F00> p2(pValue); // oops

原因在于引用计数块是在std::shared_ptr容器内部的,与pValue完全独立,因此会有两个引用计数块来处理同一个值引起错误的RAII

那么侵入式的智能指针会有这个问题吗?

boost::intrusive_ptr使用是这样的,它把引用计数与内部实现绑定在一起

struct FoOo: public boost::intrusive_ptr_base<FoOo> { // 含有引用计数ref_count
    int age;
    std::string name;
};

auto pValue = new FoOo();
boost::intrusive_ptr<FoOo> p1(pValue);
boost::intrusive_ptr<FoOo> p2(pValue); // 由同一个来自pValue的refcount来维护

容易看出,侵入式智能指针是通过绑定到FoOo内部的refcount来实现正确的引用计数

抽象与复用

侵入式容器在抽象与复用的层面上是有显然的不足的,

考虑一下,如何用list_head表示出list of list of list的数据结构,

非侵入式只需要list<list<list<Tp>>>就足够了

对于复用,这是最突出的问题,每个实现都要写一份才像样,侵入式容器最多能做到这种程度

class Type: public IntrusiveContainer {
    // ...
};

能不能给力点,也许mixin可以吧(用魔法打败魔法,滑稽.jpg)

template <typename ...Ts>
class Mixin: public Ts... {};
// Mixin<Type, IntrusiveContainer> fOoooo;

总结

合适的时机使用合适的容器,多一种选择是件好事。

简单来说,侵入式容器的独特设计可以带来以下特性

  1. 数据结构拥有更加紧凑的内存空间,且灵活的分配与更加受控的生命周期都更易于提高性能
  2. 虽然在类型表达能力与非侵入相比有所不足,但是可以与具体类型解耦
  3. 更易于实现本身依赖于具体类型的特性

发表评论

邮箱地址不会被公开。 必填项已用*标注