10.5. 局部缓冲区优化实现细节

我们已经探讨了局部缓冲区优化的应用;为了简化说明,我们一直采用其最基础的实现方式。然而,这种简单的实现忽略了一些重要的细节,现在将重点介绍。

首先,完全忽略了缓冲区的对齐问题。我们用于在对象内部预留空间的类型是 char,因此缓冲区按字节对齐。然而,大多数数据类型都有更高的对齐要求:具体要求取决于平台,但大多数内置类型的对齐方式与其自身大小一致(例如,在 x86 这样的 64 位平台上,double 类型需要 8 字节对齐)。某些特定于机器的类型需要更高的对齐,例如用于 AVX 指令的打包整数或浮点数数组。对齐非常重要:根据处理器和编译器生成的代码,访问未按数据类型要求对齐的内存可能导致性能下降,甚至内存访问违规(崩溃)。例如,大多数 AVX 指令要求 16 字节或 32 字节对齐,而这些指令的非对齐版本则明显更慢。另一个例子是原子操作(如互斥锁和其他并发数据结构中使用的操作):如果数据类型没有正确对齐,这些操作也无法正常工作(例如,原子 long 类型必须在 8 字节边界上对齐)。

指定缓冲区的最小对齐并不困难,至少在知道要在缓冲区中存储的类型时是如此。如果有一个用于任意类型 T 的小型vector,可以简单地写成:

template <typename T>
class small_vector {
  alignas(T) char buffer_[buffer_size_];
  ...
};

如果缓冲区用于存储几种类型中某一种类型的对象,就必须使用所有可能类型中最高的对齐要求。最后,如果要存储的对象类型未知 —— 这在类型擦除的实现中是典型情况 —— 必须选择一个“足够高”的对齐要求,并在特定对象于缓冲区中构造的位置添加一个编译时检查。

需要记住的第二个重要细节是缓冲区的定义方式,它是一个经过对齐的字符数组(或 std::byte_t 数组)。在上一节中,使用了一个 int 数组作为小型整数vecrtor。同样,这里也有一个细微之处:将缓冲区声明为正确类型的对象或对象数组,会导致这些对象在包含该缓冲区的对象销毁时自动析构。对于像整数这样可简单析构的类型,析构函数不执行操作。

只有在该位置确实构造了对象时,才能调用其析构函数。对于我们的小型vector而言,可能是空的,或包含的对象数量少于缓冲区的容量。这实际上是迄今为止最常见的情况:通常,如果采用局部缓冲区优化,就无法确定缓冲区中是否已构造了对象。这样,将缓冲区声明为非可简单析构的对象(或对象数组)将是一个错误。然而,如果能确保在特定情况下缓冲区始终包含对象(或对于数组而言是多个对象),将其声明为对应类型,将极大地简化析构函数以及复制/移动操作的实现。

各位读者应该已经注意到,局部缓冲区的典型实现需要大量样板代码。需要很多的 reinterpret_cast 转换,必须记得添加对齐要求,还需要添加一些编译时检查以确保只有合适的类型才能存储在缓冲区中等。将这些细节整合到一个通用的、可复用的实现中是很有益处的。但不幸的是,像许多情况一样,可复用性与复杂性之间存在矛盾,需要接受几种通用的可复用实现方案。

如果将前面学到的关于局部缓冲区的所有知识结合起来,就可以得到类似如下的实现:

// Example 10
template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  constexpr static auto size = S, alignment = A;
  alignas(alignment) char space_[size];
  ...
};

这里,有一个任意大小和对齐要求的缓冲区(两者都是模板参数)。现在有了存储对象的空间,必须确保我们想要擦除的类型能够放入这个空间中。为此,添加一个 constexpr 验证函数会很方便(仅用于编译时的语法检查):

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  template <typename T> static constexpr bool valid_type()
  {
    return sizeof(T) <= S && (A % alignof(T)) == 0;
  }
  ...
};

可以通过调用成员函数 as<T>(),将该缓冲区当作包含类型为 T 的对象来使用:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  template <typename T> requires(valid_type<T>())
    T* as() noexcept {
    return reinterpret_cast<T*>(&space_);
  }
  template <typename T> requires(valid_type<T>())
    const T* as() const noexcept {
    return const_cast<Buffer*>(this)->as<T>();
  }
};

缓冲区可以默认构造(即创建为空),也可以在构造时立即创建对象。前一种情况下,对象可以稍后通过 emplace 方式构造。无论哪种方式,都会验证该类型能够放入缓冲区,并满足对齐要求(如果不可用 C++20 及概念,可以改用 SFINAE)。默认构造函数是简单的,而带 emplace 功能的构造函数和 emplace() 方法则对类型,及构造函数参数有相应的约束:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  Buffer() = default;

  template <typename T, typename... Args>
    requires(valid_type<T>() &&
              std::constructible_from<T, Args...>)
  Buffer(std::in_place_type_t<T>, Args&& ...args)
    noexcept(std::is_nothrow_constructible_v<T, Args...>)
  {
    ::new (static_cast<void*>(as<T>()))
      T(std::forward<Args>(args)...);
  }

  template<typename T, typename... Args>
    requires(valid_type<T>() &&
              std::constructible_from<T, Args...>)
  T* emplace(Args&& ...args)
    noexcept(std::is_nothrow_constructible_v<T, Args...>)
  {
    return ::new (static_cast<void*>(as<T>()))
    T(std::forward<Args>(args)...);
  }
};

我们确实会检查所请求的类型能否存储在缓冲区中,但在运行时不会检查缓冲区是否真的包含此类对象。这种检查可以添加,但需要付出额外的存储空间和运行时计算的代价,作为调试工具可能是有意义的。对于缓冲区的复制、移动或销毁,我们没有进行特殊处理。就目前而言,此实现适用于简单复制和简单析构的对象。在这种情况下,我们希望在缓冲区中构造对象时(无论是在构造函数还是 emplace() 方法中)断言这些限制:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
template <typename T>
  Buffer(std::in_place_type_t<T>, Args&& ...args) … {
    static_assert(std::is_trivially_destructible_v<T>, "");
    static_assert(std::is_trivially_copyable_v<T>, "");
    ...
  }
};

这种情况下,为类添加一个 swap() 方法也有意义:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  void swap(Buffer& that) noexcept {
    alignas(alignment) char tmp[size];
    ::memcpy(tmp, this->space_, size);
    ::memcpy(this->space_, that.space_, size);
    ::memcpy(that.space_, tmp, size);
  }
};

另一方面,如果将此缓冲区用于存储单一已知类型,且该类型不是可简单析构的,就需要频繁地编写类似如下的代码:

buffer_.as<T>()->~T();

可以通过添加另一个通用且可用的方法,来简化使用端代码:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  template <typename T> void destroy() {
    this->as<T>()->~T();
  }
};

可以添加类似的方法来复制和移动缓冲区中存储的对象,或者将这些操作留给使用端处理。这个通用的局部缓冲区实现,适用于所有可简单复制和可简单析构的类型,也适用于类型已知、且使用端代码自行处理,缓冲区中对象复制与析构的所有情况。

但还有一种特殊情况,当局部缓冲区用于类型擦除类中时,所存储(擦除)类型可能需要非简单的复制或析构操作,而使用端无法执行这些操作 —— 类型擦除的核心是:在对象放入缓冲区后,使用端代码不再知晓其具体类型。在这种特殊情况下,需要在对象存储时捕获其类型,并生成相应的复制、移动和析构操作。换句话说,必须将局部缓冲区与之前在第6章中学到的技术结合起来。此时最合适的类型擦除变体是虚函数表 —— 一种通过模板生成的函数指针表。该 vtable 本身是一个聚合体,包含执行删除、复制或移动操作的函数指针:

// Example 11
template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  struct vtable_t {
    using deleter_t = void(Buffer*);
    using copy_construct_t = void(Buffer*, const Buffer*);
    using move_construct_t = void(Buffer*, Buffer*);
    deleter_t* deleter_;
    copy_construct_t* copy_construct_;
    move_construct_t* move_construct_;
  };
  const vtable_t* vtable_ = nullptr;
};

我们需要一个类成员 vtable_ 来存储指向 vtable 的指针,其所指向的对象必须由构造函数或 emplace() 方法创建 —— 只有此时才知道对象的真实类型,以及如何删除或复制。但不会为此进行动态内存分配,但会创建一个静态模板变量,并用指向静态成员函数(同样是模板)的指针来初始化它。编译器会为每一个存储在缓冲区中的类型生成该静态变量的一个实例。当然,还需要静态模板函数(静态成员函数的指针与普通函数指针相同,而不是成员函数指针)。这些函数由编译器实例化,其类型 T 与存储在缓冲区中的对象类型一致:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  template <typename U, typename T>
  constexpr static vtable_t vtable = {
    U::template deleter<T>,
    U::template copy_construct<T>,
    U::template move_construct<T>
  };

  template <typename T>
    requires(valid_type<T>() &&
    std::is_nothrow_destructible_v<T>)
  static void deleter(Buffer* space) {
    space->as<T>()->~T();
  }

  template <typename T>
    requires(valid_type<T>())
    static void copy_construct(Buffer* to,
                               const Buffer* from)
    noexcept(std::is_nothrow_copy_constructible_v<T>)
  {
    ::new (static_cast<void*>(to->as<T>()))
      T(*from->as<T>());
    to->vtable_ = from->vtable_;
  }

  template <typename T>
    requires(valid_type<T>())
    static void move_construct(Buffer* to, Buffer* from)
    noexcept(std::is_nothrow_move_constructible_v<T>)
  {
    ::new (static_cast<void*>(to->as<T>()))
      T(std::move(*from->as<T>()));
    to->vtable_ = from->vtable_;
  }
};

如第6章中所述,首先使用模板静态函数为所需的类型 T 生成复制、移动和删除操作。将指向这些函数的指针存储在一个静态模板变量 vtable 的实例中,并将指向该实例的指针存入一个(非静态)数据成员 vtable_ 中。从空间开销的角度来看,vtable_ 是唯一的代价(其余部分是静态变量和函数,编译器为缓冲区中存储的每种类型仅生成一次)。

由于这是最后一次明确知道所存储对象类型的时候,因此必须在对象放入缓冲区时初始化这个 vtable_:

// Example 11
template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  template <typename T, typename... Args>
    requires(valid_type<T>() &&
    std::constructible_from<T, Args...>)
  Buffer(std::in_place_type_t<T>, Args&& ...args)
    noexcept(std::is_nothrow_constructible_v<T, Args...>)
    : vtable_(&vtable<Buffer, T>)
  {
    ::new (static_cast<void*>(as<T>()))
      T(std::forward<Args>(args)...);
  }

  template<typename T, typename... Args>
    requires(valid_type<T>() &&
    std::constructible_from<T, Args...>)
  T* emplace(Args&& ...args)
    noexcept(std::is_nothrow_constructible_v<T, Args...>)
  {
    if (this->vtable_) this->vtable_->deleter_(this);
    this->vtable_ = &vtable<Buffer, T>;
    return ::new (static_cast<void*>(as<T>()))
      T(std::forward<Args>(args)...);
  }
  ...
};

请注意构造函数中对 vtable_ 成员的初始化。在 emplace() 方法中,如果缓冲区中已存在先前构造的对象,还必须将其删除。

有了类型擦除机制后,终于可以实现析构函数以及复制/移动操作了。它们都采用相似的方法 —— 调用 vtable 中对应的函数。以下是复制操作的实现:

// Example 11
template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ..
  Buffer(const Buffer& that) {
    if (that.vtable_)
      that.vtable_->copy_construct_(this, &that);
  }

  Buffer& operator=(const Buffer& that) {
    if (this == &that) return *this;
    if (this->vtable_) this->vtable_->deleter_(this);
    if (that.vtable_)
      that.vtable_->copy_construct_(this, &that);
    else this->vtable_ = nullptr;

    return *this;
  }
};

移动操作与此类似,只是它们使用了 move_construct_ 函数:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  Buffer(Buffer&& that) {
    if (that.vtable_)
      that.vtable_->move_construct_(this, &that);
  }

  Buffer& operator=(Buffer&& that) {
    if (this == &that) return *this;
    if (this->vtable_) this->vtable_->deleter_(this);
    if (that.vtable_)
    that.vtable_->move_construct_(this, &that);
    else this->vtable_ = nullptr;

    return *this;
  }
};

移动赋值运算符并不强制要求检查自赋值,但进行这样的检查也并无错误。我们非常希望移动操作是 noexcept 的,但在编译时无法知道擦除类型,因此无法保证。可以做一个设计上的选择,无论如何都将它们声明为 noexcept。如果这样做,还可以在编译时断言存储在缓冲区中的对象是 noexcept 可移动的。

最后,来实现析构操作。由于我们允许调用者在不销毁缓冲区本身的情况下,销毁其中包含的对象(通过调用 destroy() 方法),因此必须确保对象仅销毁一次:

template<size_t S, size_t A = alignof(void*)>
struct Buffer {
  ...
  ~Buffer() noexcept {
    if (this->vtable_) this->vtable_->deleter_(this);
  }

  // Destroy the object stored in the aligned space.
  void destroy() noexcept {
    if (this->vtable_) this->vtable_->deleter_(this);
    this->vtable_ = nullptr;
  }
};

拥有类型擦除的 vtable 能够在运行时,重建存储在缓冲区中的类型(该类型内嵌于为 copy_construct() 等静态函数生成的代码中)。

当然,这样做是有代价的;已经提到了其他的数据成员 vtable_,由于间接函数调用,还会产生一定的运行时开销。可以通过使用两种局部缓冲区实现(带类型擦除和不带类型擦除),来存储和复制一个可简单复制的对象(例如,一个捕获了引用的 Lambda 表达式)来估算这种开销:

Benchmark                    Time
BM_lambda_copy_trivial       5.45 ns
BM_lambda_copy_typeerased    4.02 ns

(良好实现的)类型擦除的开销虽然不可忽略,但仍然适中。

一个优势是,还可以在运行时验证对 as<T>() 的调用是否指向一个有效的类型,以及对象是否确实已被构造。与非常轻量的无检查方法相比,这会增加显著的开销,可能仅在调试版本中启用。

已经看到了局部缓冲区优化,为许多不同的数据结构和类带来的显著(有时甚至是巨大的)性能提升。凭借刚刚学习的这些易于使用的通用实现,为什么不随时随地使用这种优化呢?与设计模式一样,在结束探讨之前,必须权衡这种优化的优缺点。