6.4. C++中的类型擦除实现

我们已经了解了 C++ 中类型擦除的表现形式。现在,理解了程序不显式依赖于某个类型意味着什么。但谜团依然存在 —— 程序中完全没有提及该类型,然而却能在恰当的时机,调用一个它“一无所知”的类型上的操作。这究竟是如何实现的?接下来,就来揭开这个谜底。

6.4.1 非常古老的类型擦除

编写不包含显式类型信息的程序这一想法当然不是新的,它远早于面向对象编程和“对象”概念的出现。考虑下面这个 C 语言程序(这里没有 C++)作为例子:

// Example 06
int less(const void* a, const int* b) {
  return *(const int*)a - *(const int*)b;
}

int main() {
  int a[10] = { 1, 10, 2, 9, 3, 8, 4, 7, 5, 0 };
  qsort(a, 10, sizeof(int), less);
}

标准 C 库的 qsort 函数的函数声明:

void qsort(void *base, size_t nmemb, size_t size,
  int (*compare)(const void *, const void *));

尽管使用它来对一个整数数组进行排序,但 qsort 函数本身没有显式类型 —— 使用 void* 来传入待排序的数组。比较函数接收两个 void* 指针,其声明中也没有显式的类型信息。当然,我们需要知道如何比较实际的类型。在 C 程序中,理论上可以指向类型的指针,重新解释为指向整数的指针。这种逆转抽象的操作称为具体化。

在 C 语言中,恢复具体类型完全由开发者负责 —— 我们的 less() 比较函数实际上确实只比较整数,但从接口上无法推断出。同样,也无法在运行时验证程序中是否始终使用了正确的类型,程序当然也不可能在运行时,自动为实际类型选择正确的比较操作。

这个简单的例子让我们看穿了类型擦除的“魔法”:通用代码确实不依赖于擦除的具体类型,但该类型隐藏在通过类型擦除接口调用的函数代码中。在我们的例子中,就是这个比较函数:

int less(const void* a, const int* b) {
  return *(const int*)a - *(const int*)b;
}

调用代码对 int 类型一无所知,但 less() 函数的实现却是基于该类型进行操作的。这个类型“隐藏”在通过类型无关接口调用的函数代码之中。

C 语言方法的主要缺点是,开发者必须完全负责确保类型擦除代码的所有部分保持一致;我们的例子中,就是排序的数据和比较函数必须指向相同的类型。

在 C++ 中,可以做得更好,但其基本思想仍然相同:擦除的类型会通过某个类型特定代码的实现来具体化,而该代码是通过类型无关的接口调用的。关键的区别在于,将强制编译器为生成这部分代码。从根本上讲,有两种技术可以使用。第一种依赖于运行时多态(继承),第二种则使用模板技巧。先从多态实现开始。

6.4.2 使用继承的类型擦除

现在,来看看 std::shared_ptr 如何实现的。我们将通过一个简化版的智能指针示例来说明,该示例特别关注类型擦除的方面,并通过泛型编程和面向对象编程的结合来实现:

// Example 07
template <typename T> class smartptr {
  struct destroy_base {
    virtual void operator()(void*) = 0;
    virtual ~deleter_base() {}
  };

  template <typename Deleter>
  struct destroy : public destroy _base {
    destroy (Deleter d) : d_(d) {}
    void operator()(void* p) override {
      d_(static_cast<T*>(p));
    }
    Deleter d_;
  };

public:
  template <typename Deleter> smartptr(T* p, Deleter d) :
    p_(p), d_(new destroy<Deleter>(d)) {}

  ~smartptr() { (*d_)(p_); delete d_; }
  T* operator->() { return p_; }

  const T* operator->() const { return p_; }

private:
  T* p_;
  destroy _base* d_;
};

该 smartptr 模板只有一个类型参数。由于擦除的类型不是智能指针类型的一部分,必须封装在另一个对象中。在例子中,这个对象是嵌套模板 smartptr<T>::destroy 的一个实例。这个对象由构造函数创建,而构造函数代码中是最后一次显式出现删除器类型的地方。但smartptr 必须通过一个类型不依赖于 destroy 的指针来引用 destroy 实例(对于所有删除器,smartptr 对象的类型都相同)。因此,destroy 模板的实例都继承自同一个基类 destroy_base,而实际的删除器可以通过虚函数调用。构造函数是一个模板,会推导出删除器的类型,但该类型只是隐藏了,它属于该模板特定实例化的实际声明的一部分。智能指针类本身,特别是其析构函数(实际使用删除器的地方),其删除器类型确实擦除了。编译时的类型检测被用来创建一个构造正确的多态对象,该对象将在运行时重新发现删除器类型并执行正确的操作。所以不需要 dynamic_cast,而可以使用 static_cast,这只有在知道真实的派生类型时才有效(我们确实知道)。

同样的技术可以用来实现 std::function 和其他类型擦除的类型,比如终极的类型擦除类 std::any(在 C++17 及以上版本中)。这是一个类,而不是一个模板,但它可以持有类型的值:

// Example 08
std::any a(5);
int i = std::any_cast<int>(a); // i == 5
std::any_cast<long>(a); // 抛出异常 bad_any_cast

由于不知道具体类型,std::any 无法提供特定于该类型的接口。只能将任意值存入其中,并且只有在知道正确的类型时才能将其取出(或者查询类型,得到一个 std::type_info 对象)。

在我们学习另一种(通常更高效)的类型擦除实现方式之前,必须解决当前设计中一个低效问题:每次创建或删除一个共享指针,或按上述方式实现的 std::function 对象时,都必须为那个隐藏擦除类型的派生对象分配和释放内存。

6.4.3 无需内存分配的类型擦除

然而,有一些方法可以优化类型擦除的指针(以及其他类型擦除的数据结构),从而避免在构造多态的 smartptr::destroy 对象时产生额外的内存分配。可以通过预先为这些对象分配一个内存缓冲区,至少在某些情况下避免这种分配。这种优化的细节及其局限性将在第10章中讨论。以下是该优化的核心思想:

// Example 07
template <typename T> class smartptr {
  ...
public:
  template <typename Deleter> smartptr(T* p, Deleter d) : p_(p) {
    static_assert(sizeof(Deleter) <= sizeof(buf_));
    ::new (static_cast<void*>(buf_)) destroy<Deleter>(d));
  }

  ~smartptr() {
    destroy_base* d = (destroy_base*)buf_;
    (*d)(p_);
    d->~destroy_base();
  }

private:
  T* p_;
  alignas(8) char buf_[16];
};

局部缓冲区优化确实使类型擦除的指针和函数高效得多,将在本章后面看到。当然,它对删除器的大小施加了限制;因此,大多数实际的实现会对足够小的擦除类型使用局部缓冲区,而对无法放入缓冲区的类型则使用动态内存。另一种解决方案 —— 进行断言并强制开发者增大缓冲区 —— 通常在对性能要求极高的应用中采用。

这种优化的使用还带来一些更微妙的后果:删除器(或其他擦除对象)现在作为类的一部分进行存储,必须随类的其他部分一起复制。如何复制一个不知道类型的对象?诸如此类的其他细节,我们将在第10章中再进行讨论。目前,将在后续的示例中使用局部缓冲区优化,既是为了展示其用法,也是为了简化代码。

6.4.4 不使用继承的类型擦除

有一种替代的类型擦除实现方式,不使用内部的类型层次结构来存储擦除的类型。相反,类型捕获在函数的实现中,就像在 C 语言中所做的那样:

void erased_func(void* p) {
  TE* q = static_cast<T*>(p);
  ... 对 TE 类型进行操作 ...
}

在 C++ 中,让该函数成为一个模板,编译器就会需要的每一种类型 TE 进行实例化:

template <typename TE> void erased_func(void* p) {
  TE* q = static_cast<T*>(p);
  ... 对 TE 类型进行操作 ...
}

这是一个有些特殊的模板函数:其类型参数无法从参数中推导出来,必须显式指定。我们已经知道,这将在类型擦除类(例如我们的智能指针)的构造函数中完成,并知道即将擦除的类型。另一个非常重要的点是,前述模板生成的函数都可以通过同一个函数指针来调用:

void(*)(void*) fp = erased_func<int>; // 或其他类型

现在可以看到类型擦除的“魔法”是如何工作的了:有一个函数指针,其类型不依赖于正在擦除的类型 TE。为特定的 TE 生成一个包含该类型具体实现的函数,并将其地址赋给这个指针。当需要使用擦除的类型 TE 时(例如,使用指定的删除器来删除对象),将通过这个函数指针来调用函数;可以在完全不知道 TE 是什么的情况下完成这个调用。只需要将所有这些组合成一个构造正确的实现,以下就是类型擦除的智能指针:

// Example 07
template <typename T>
class smartptr_te_static {
  T* p_;
  using destroy_t = void(*)(T*, void*);

  destroy_t destroy_;

  alignas(8) char buf_[8];

  template<typename Deleter>
  static void invoke_destroy(T* p, void* d) {
    (*static_cast<Deleter*>(d))(p);
  }

public:
  template <typename Deleter>
  smartptr_te_static(T* p, Deleter d)
    : p_(p), destroy_(invoke_destroy<Deleter>)
  {
    static_assert(sizeof(Deleter) <= sizeof(buf_));
    ::new (static_cast<void*>(buf_)) Deleter(d);
  }

  ~smartptr_te_static() {
    this->destroy_(p_, buf_);
  }

  T* operator->() { return p_; }

  const T* operator->() const { return p_; }
};

将用户提供的删除器存储在一个小型的局部缓冲区中;在此示例中,没有展示对于更大的删除器(需要动态内存分配)的替代实现。用于保留擦除类型信息的函数模板是 invoke_destroy()。它是一个静态函数;静态函数可以通过普通的函数指针调用,而不是更复杂的成员函数指针。

在 smartptr 类的构造函数中,实例化了 invoke_destroy<Deleter> 并将其赋值给 destroy_ 函数指针。还需要一份删除器对象的副本,因为删除器可能包含状态(例如,指向为智能指针所拥有的对象提供内存的分配器的指针)。我们将这个删除器构造在局部缓冲区 buf_ 提供的空间中。此时,原始的 Deleter 类型已经擦除:我们所拥有的只是一个不依赖于 Deleter 类型的函数指针和一个字符数组。

当需要销毁智能指针所拥有的对象时,需要调用删除器。取而代之的是,通过 destroy_ 指针调用函数,并将要销毁的对象和存放删除器的缓冲区传递给它。擦除的 Deleter 类型隐藏在 invoke_destroy() 的特定实现内部,指向缓冲区的指针重新转换回实际存储在缓冲区中的类型(Deleter),然后调用删除器。

这个例子或许是对 C++ 中类型擦除机制最简洁的演示。但它并不完全等同于上一节中使用继承的例子。当对智能指针所拥有的 T 类型对象调用删除器时,并未对删除器对象本身做处理,特别是存储在局部缓冲区中的那份副本。局部缓冲区在这里不是问题:即使改为动态分配内存,仍然会通过像 char* 或 void* 这样的通用指针来访问,而不知道如何正确地删除。为此,需要另一个能够重新具体化原始类型的函数。简单可析构的删除器(以及一般而言,简单可析构的可调用对象)非常常见。所有函数指针、成员函数指针、无状态对象,以及不按值捕获非简单对象的 Lambda,都是简单可析构的。因此,可以在构造函数中简单地添加一个 static_assert,将我们的智能指针限制为,只接受简单可析构的删除器,这在大多数情况下都能很好地工作。但我也想向你展示一个更通用的解决方案。

我们当然可以使用另一个指向静态函数的指针,该函数用于销毁删除器,并在构造函数中用正确的类型进行实例化。但析构并不是全部:通常,还需要复制和移动删除器,甚至可能需要比较它们。这会需要大量的函数指针,使得 smartptr 类变得臃肿。相比之下,基于继承的实现仅用一个指向 destroy 对象的指针(存储为指向基类 destroy_base 的指针)就完成了所有这些操作。我们有一种方法可以做到同样的事情。对于这个例子,没有一个好的方式可以逐步揭示其“魔法”,所以必须直接深入,并进行逐行解释:

// Example 07
template <typename T>
class smartptr_te_vtable {
  T* p_;

  struct vtable_t {
    using destroy_t = void(*)(T*, void*);
    using destructor_t = void(*)(void*);
    destroy_t destroy_;
    destructor_t destructor_;
  }

  const vtable_t* vtable_ = nullptr;

  template <typename Deleter>
  constexpr static vtable_t vtable = {
    smartptr_te_vtable::template destroy<Deleter>,
    smartptr_te_vtable::template destructor<Deleter>
  }

  template <typename Deleter>
  static void destroy(T* p, void* d) {
    (*static_cast<Deleter*>(d))(p);
  }

  template <typename Deleter>
  static void destructor(void* d) {
    static_cast<Deleter*>(d)->~Deleter();
  }

  alignas(8) char buf_[8];

public:
  template <typename Deleter>
  smartptr_te_vtable(T* p, Deleter d)
    : p_(p), vtable_(&vtable<Deleter>)
  {
    static_assert(sizeof(Deleter) <= sizeof(buf_));
    ::new (static_cast<void*>(buf_)) Deleter(d);
  }

  ~smartptr_te_vtable() {
    this->vtable_->destroy_(p_, buf_);
    this->vtable_->destructor_(buf_);
  }

  T* operator->() { return p_; }
  const T* operator->() const { return p_; }
};

解释一下这段代码的工作原理。首先,声明了一个结构体 vtable_t,其中包含了指向需要在擦除的 Deleter 类型上实现的每个操作的函数指针。例子中,只有两个操作:调用 deleter 来销毁一个对象,以及销毁 deleter 本身。通常情况下,还需要包含复制和移动操作(可以在第10章中找到这样的实现)。接下来是 vtable_ 指针。对象构造完成后,将指向一个 vtable_t 类型的对象。虽然这可能暗示着即将进行动态内存分配,但将会做得更好。接下来是一个变量模板 vtable;对一个具体的 Deleter 类型实例化,将创建一个 vtable_t 类型的静态变量实例。当类有一个静态数据成员时,它只是一个变量,可以通过名称访问。但这里的情况不同:名称 vtable 可以指代多个对象,都具有相同的类型 vtable_t。这些对象并非显式创建的:不会为它们分配内存,也不会调用 operator new 来构造。编译器会使用的每一种 Deleter 类型创建一个这样的对象。对于每一个 smartptr 对象,其想要使用的特定 vtable 对象的地址会存储在 vtable_ 指针中。

vtable_t 类型的对象包含指向静态函数的指针。我们的 vtable 也必须如此,将 vtable 中的函数指针初始化为指向 smartptr 类的静态成员函数的实例化。这些实例化与 vtable 自身实例化的 Deleter 类型相同。

名称 vtable 并非随意选择:实际上已经实现了一个虚函数表;编译器为每个包含多态的类型层次结构构建一个非常相似的、包含函数指针的结构,并且每个虚类都有一个虚函数指针,指向其原始类型(即构造时的类型)对应的表。

在 vtable 之后,有两个静态函数模板。这正是擦除的类型真正被隐藏,以及之后具体化的地方。正如之前所见,这些函数的签名不依赖于 Deleter 类型,但其实现却依赖。最后,有一个用于在本地存储 deleter 对象的缓冲区。和之前一样,构造函数将所有这些内容联系在一起,因为构造函数是这段代码中唯一明确知道 Deleter 类型的地方。构造函数在此做了三件事:首先,像其他智能指针一样存储指向对象的指针。其次,将 vtable_ 指针指向对应 Deleter 类型的静态 vtable 变量实例。最后,在本地缓冲区中构造一个 deleter 的副本。此时,Deleter 类型已擦除:smartptr 对象中的内容都不再显式依赖于它。

当调用智能指针的析构函数,需要销毁所拥有的对象和 deleter 本身时,deleter 及其真实类型再次发挥作用。这些操作中的每一项都通过间接函数调用来完成。要调用的函数存储在 *vtable_ 对象中(就像多态类中,正确的虚函数重写通过虚函数表中的函数指针找到一样)。deleter 通过缓冲区的地址传递给这些函数 —— 这里没有类型信息。但由于这些函数是为特定的 Deleter 类型生成的,因此会将 void* 缓冲区地址转换为正确的类型,并使用存储在缓冲区中的删除器。

这种实现方式允许我们在对象本身中仅存储一个 vtable_ 指针的情况下,支持多个类型擦除的操作。

我们还可以结合这两种方法:通过虚函数表调用某些操作,而为其他操作使用专用的函数指针。为什么?通过虚函数表调用函数可能会稍微慢一些。这需要针对具体的应用程序进行测试。

目前为止,我们使用类型擦除为非常具体的行为提供了抽象接口。已经知道,类型擦除并不需要如此受限 —— 已经了解了 std::function 的例子。本节的最后一个例子将是我们自己的通用类型擦除函数。

6.4.5 高效的类型擦除

上一节的示例和解释之后,实现一个类型擦除的函数将不会太困难。但在此展示它仍然有价值。我们将演示一种非常高效的类型擦除实现(本书中的实现灵感来自 Arthur O'Dwyer 和 Eduardo Magrid 的工作)。

一个泛型函数的模板如下所示:

template<typename Signature> class Function;

这里的 Signature 类似于 int(std::string),表示一个接受字符串并返回整数的函数。只要某个可调用类型的对象,能够以指定的签名作为函数被调用,就可以用该类型构造出这样的函数对象。

再次使用局部缓冲区,但这次不会将其硬编码到类中,而是添加模板参数来控制缓冲区的大小和对齐方式:

template<typename Signature, size_t Size = 16,
         size_t Alignment = 8> struct Function;

为了编码方便,将函数签名拆解为参数类型 Args... 和返回类型 Res 是很便利的。最简单的方法是使用类模板特化:

// Example 09
template<typename Signature, size_t Size = 16,
         size_t Alignment = 8> struct Function;
template<size_t Size, size_t Alignment,
         typename Res, typename... Args>
struct Function<Res(Args...), Size, Alignment> {...};

现在剩下的就是具体的实现了,需要一个缓冲区来存储 Callable 对象:

// Example 09
alignas(Alignment) char space_[Size];

其次,需要一个函数指针 executor_,用于存储从带有 Callable 对象类型的模板生成的静态函数 executor 的地址:

// Example 09
using executor_t = Res(*)(Args..., void*);
executor_t executor_;
template<typename Callable>
static Res executor(Args... args, void* this_function) {
  return (*reinterpret_cast<Callable*>(
    static_cast<Function*>(this_function)->space_))
  (std::forward<Args>(args)...);
}

接下来,在构造函数中,必须初始化 executor 并将 Callable 对象存储到缓冲区中:

// Example 09
template <typename CallableArg,
          typename Callable = std::decay_t<CallableArg>>
  requires(!std::same_as<Function, Callable>)
Function(CallableArg&& callable) :
  executor_(executor<Callable>)
{
  ::new (static_cast<void*>(space_))
    Callable(std::forward<CallableArg>(callable));
}

这个构造函数有两个微妙的细节。第一个是关于可调用对象类型的处理:将其推导为 CallableArg,但随后使用的是 Callable。这是因为 CallableArg 可能是可调用类型(例如函数指针)的引用类型,但并不希望构造一个引用的副本。第二个是概念限制:Function 本身是一个具有相同签名的可调用对象,但不希望在此情况下使用该构造函数 —— 这种情况应由复制构造函数处理。如果不使用 C++20,就必须使用 SFINAE 来实现相同的效果(详见第7章)。如果你喜欢概念的风格,可以在一定程度上进行模拟:

#define REQUIRES(...) \
  std::enable_if_t<__VA_ARGS__, int> = 0

template <typename CallableArg,
          typename Callable = std::decay_t<CallableArg>,
          REQUIRES(!std::is_same_v<Function, Callable>)>)
Function(CallableArg&& callable) …

说到复制,当前的 Function 类只对可简单复制和可简单析构的 Callable 类型是正确的,我们并未提供机制来销毁或复制存储在缓冲区中的 Callable 对象。尽管这已经覆盖了大量使用场景,但也可以使用虚表(vtable)的方法来处理非简单的 Callable 对象(可以在第10章中找到示例)。

还有一处细节,需要现在处理:std::function 可以在没有可调用对象的情况下默认构造;调用这样一个“空”函数会抛出一个 std::bad_function_call 异常。也可以实现这一行为,只需将 executor 初始化为一个预先定义的函数,该函数除了抛出此异常外什么都不做:

// Example 09
static constexpr Res default_executor(Args..., void*) {
  throw std::bad_function_call();
}

constexpr static executor_t default_executor_ = default_executor;
executor_t executor_ = default_executor_;

现在有了一个与 std::function 非常相似的通用函数(如果再添加对成员函数调用、复制与移动语义以及少数缺失的成员函数的支持,就完全等同了)。其运作方式也基本相同:

Function<int(int, int, int, int)> f =
  [](int a, int b, int c, int d) { return a + b + c + d; };
int res = f(1, 2, 3, 4);

那么,这种便利性让我们付出了怎样的代价呢?所有性能问题都应通过实际测量来评估,但我们也可以通过检查编译器在调用类型擦除函数时,生成的机器代码来获得一些直观认识。以下是调用一个与我们刚刚使用的签名相同的 std::function 所需的步骤:

// Example 09
using Signature = int(int, int, int, int);
using SF = std::function<Signature>;
auto invoke_sf(int a, int b, int c, int d, const SF& f) {
  return f(a, b, c, d);
}

编译器(GCC-11,开启O3优化)将上述代码转换为:

endbr64
sub $0x28,%rsp
mov %r8,%rax
mov %fs:0x28,%r8
mov %r8,0x18(%rsp)
xor %r8d,%r8d
cmpq $0x0,0x10(%rax)
mov %edi,0x8(%rsp)
mov %esi,0xc(%rsp)
mov %edx,0x10(%rsp)
mov %ecx,0x14(%rsp)
je 62 <_Z9invoke_sfiiiiRKSt8functionIFiiiiiEE+0x62>
lea 0xc(%rsp),%rdx
lea 0x10(%rsp),%rcx
mov %rax,%rdi
lea 0x8(%rsp),%rsi
lea 0x14(%rsp),%r8
callq *0x18(%rax)
mov 0x18(%rsp),%rdx
sub %fs:0x28,%rdx
jne 67 <_Z9invoke_sfiiiiRKSt8functionIFiiiiiEE+0x67>
add $0x28,%rsp
retq
callq 67 <_Z9invoke_sfiiiiRKSt8functionIFiiiiiEE+0x67>
callq 6c <_Z9invoke_sfiiiiRKSt8functionIFiiiiiEE+0x6c>

现在来看我们的函数:

// Example 09
using F = Function<Signature>;
auto invoke_f(int a, int b, int c, int d, const F& f) {
  return f(a, b, c, d);
}

这一次,编译器可以做得更好得多:

endbr64
jmpq *0x10(%r8)

这里看到的是所谓的尾部调用:编译器直接将执行流重定向到,需要调用的实际可调用对象上。

有读者可能会问,难道不一直都是这样吗?通常不是这样的:大多数函数调用是通过 call 和 ret 指令实现的。要调用一个函数,必须先将参数存储在预定义的位置,然后将返回地址压入栈中,再通过 call 指令将执行转移到函数入口点。ret 指令则从栈中取出地址,并将执行转移到该位置。

尾部调用的巧妙之处在于:虽然最终希望对 Function 的调用能够调用到原始的可调用对象,但并不需要执行流返回到 Function 对象本身。如果 Function 的 executor 在调用完可调用对象后没有其他事情要做,只是将控制权返回给调用者,那么完全可以保留原始的返回地址不变,让可调用对象直接将控制权返回到正确的位置,从而避免了一次间接跳转。当然,这假设了 executor 在调用之后没有后续操作。

我们的代码中有两个关键优化促成了这种紧凑的实现:

处理空函数的方式:大多数 std::function 的实现会将 executor 初始化为 nullptr,并在每次调用时进行空指针比较。我们没有进行这样的比较;总是直接调用 executor。但 executor 永远不会是空的:除非显式初始化,总是指向默认的 executor(即抛出异常的那个函数)。

更微妙的优化:可能已经注意到,executor 比可调用对象本身多一个参数。例如,要调用一个签名为 int(int, int) 的函数,executor 需要两个原始函数参数(当然)以及指向可调用对象的指针(该对象存储在局部缓冲区中)。因此,executor 的签名是 int(int, int, void*)。为什么不把对象指针作为第一个参数传递呢?这正是 std::function 所做的(至少刚才看到的汇编代码是如此)。问题在于,原始函数的参数也位于栈上。在栈的末尾添加一个参数很容易。但要在开头插入一个新的第一个参数,就必须将所有已有的参数在栈上移动一位(这就是为什么 std::function 生成的代码会随着参数增多而变得更长)。

尽管这些关于性能的推测听起来很有说服力,但未经测量的性能猜测,都不值得耗费精力记录下来。性能问题必须通过实际测量来验证,这也是我们在本章剩下的最后一项任务。