高效的多态数据结构 - Boost C++ 函数库

一种高效的多态数据结构

假设我们有一个名为 base 的抽象类，其派生实现有 derived1、derived2 和 derived3。 std::vector<base*>（或类似结构，如 std::vector<std::unique_ptr<base>> 或 boost::ptr_vector<base>）的内存布局如下：

向量中相邻的元素不一定在内存中是连续的，如果向量在中间进行了插入和删除操作，这种不连续性会更加明显。典型的处理操作

std::vector<base*> v;
...
for(base* b: v){
  ... // access base's virtual interface
}

会受到两个因素的负面影响。

元素在内存中的分散会降低 CPU 缓存效率，而 CPU 缓存通常更偏好对连续内存区域的规律访问循环。
分支预测试图通过根据历史记录推测性地执行某个分支来最小化运行条件代码（如 if-else 语句或调用 base 虚函数）的效果。当 derived1、derived2 和 derived3 的元素毫无规律地穿插在序列中时，这种机制就会变得几乎无用。

这些限制是动态多态本身的性质所 imposed 的：由于通过 base 接口访问的元素的具体类型是未知的，因此需要通过 base* 进行间接引用（这是一种特殊的 类型擦除）。然而有一个关键的观察：即使在遍历 std::vector<base*> 时派生类型是未知的，这些信息通常在插入到向量的点 在编译时 是可用的。

std::vector<base*> v;
...
v.insert(new derived2{...}); // the type derived2 is "forgotten" by v

一个设计得当的容器可以利用这些信息，根据元素的具体类型将它们连续地排列起来，从而形成一个内部数据结构（实际上是一个指向指针的映射，指针指向 std::type_info 对象），该映射指向与派生类数量相同的多个向量或段。

遍历这样的结构就简化为逐个遍历所有段：这在缓存和分支预测方面都非常高效。然而，在这个过程中，我们已经失去了 std::vector<base*> 的自由排序能力（自由排序只能在段级别保留），但如果这对用户应用程序不重要，那么切换到这种结构可能会带来巨大的性能提升。

我们的讨论集中在基类/派生类编程，也称为面向对象（OOP），但它也适用于其他形式的动态多态。

std::function 在给定相同签名的可调用实体下，通过一个公共接口进行抽象。内部使用指针间接引用和类似虚函数的方式调用。尽管如此，由于实现通常采用所谓的 小缓冲区优化 来避免在某些情况下进行堆分配，因此内存碎片预计会比 OOP 低。
std::function 的情况可以看作是一种更通用的多态形式，称为 鸭子类型 的一个特例。在这种形式下，如果无关的类型符合相同的给定接口（一组指定的成员函数和/或操作），它们就会被统一对待。鸭子类型提供了面向对象的强大功能，同时允许更大的灵活性，因为多态类型不需要从预先存在的基类派生，也不必在一般情况下为了任何特定接口而设计——事实上，同一个对象可以被鸭子类型化为不同的接口。在众多库中，Boost.TypeErasure 为 C++ 提供了鸭子类型。在底层，鸭子类型需要指针间接引用和类似 OOP 的虚函数调用实现技术，因此存在与我们描述的相同的、用于高效容器数据结构的机遇。
封闭多态 是指在编译时指定可接受的类型。 std::variant 和 Boost.Variant2 是封闭多态的突出例子，其底层类型（称为 替代项）通过访问来访问。封闭多态的典型实现不涉及动态分配（替代项以 union 风格存储在共享存储中），但将相同类型的对象分组在一起仍然能提供性能和空间优势。

Boost.PolyCollection 提供了四种不同的容器类模板，分别处理 OOP、类似于 std::function 的多态、Boost.TypeErasure 实现的鸭子类型，以及 std::variant 风格的封闭多态。

boost::base_collection
boost::function_collection
boost::any_collection
boost::variant_collection

这些容器的接口大多相同，并遵循标准库容器的常规约定。

Boost C++ 库

一种高效的多态数据结构