Hinnant的short_alloc和对齐保证

Question

我最近接触了Howard Hinnant的short_alloc，这是我见过的最好的自定义分配器示例。

但是，当我花费更多时间研究代码以将其集成到我的个人项目中时，我发现提供基于堆栈的分配的arena类可能不会始终返回适当对齐的内存。实际上，我担心只有第一个分配被保证适当对齐（因为缓冲区本身具有强制对齐），请参见下面相关的代码片段：

template <std::size_t N>
class arena
{
  static const std::size_t alignment = 16;
  alignas(alignment) char buf_[N];
  char* ptr_;
  //...
};

template <std::size_t N>
char*
arena<N>::allocate(std::size_t n)
{
  assert(pointer_in_buffer(ptr_) && "short_alloc has outlived arena");
  if (buf_ + N - ptr_ >= n)
  {
    char* r = ptr_;
    ptr_ += n;
    return r;
  }
  return static_cast<char*>(::operator new(n));
}

我可以想到几种方法来解决这个问题（但会浪费一些内存），最简单的方法是在allocate/deallocate函数中将size四舍五入为alignment的倍数。

但在改变任何东西之前，我希望确保我没有漏掉什么...

- pragmatib

---

寻找 @HowardHinnant 医生。 - sehe

Answer 1

在我未掌握std::max_align_t（现在位于<cstddef>中）之前，我编写了这段代码。现在，我会将其编写为：

static const std::size_t alignment = alignof(std::max_align_t);

在我的系统上，这与当前代码完全相同，但现在更具可移植性。这是new和malloc保证返回的对齐方式。一旦您拥有了这个“最大对齐”缓冲区，您可以在其中放置任何一种类型的数组。但您不能为不同类型（至少对于具有不同对齐要求的不同类型）使用相同的arena。因此，也许最好在第二个size_t上模板化arena，该size_t等于alignof(T)。通过这种方式，您可以防止将相同的arena意外地用于具有不同对齐要求的类型：

arena<N, alignof(T)>& a_;

假设来自arena的每个分配具有相同的对齐要求，并且假设缓冲区最大对齐，则缓冲区中的每个分配都将适当地对齐为T。

例如，在我的系统上，alignof(std::max_align_t) == 16。 具有此对齐方式的缓冲区可以容纳以下数组：

- 具有alignof == 1的类型。 - 具有alignof == 2的类型。 - 具有alignof == 4的类型。 - 具有alignof == 8的类型。 - 具有alignof == 16的类型。

由于某些环境可能支持具有“超级对齐”要求的类型，因此添加（例如在short_alloc内）一个额外的安全预防措施是明智的。

static_assert(alignof(T) <= alignof(std::max_align_t), "");

如果你非常谨慎，你也可以检查alignof(T)是2的幂次方，尽管C++标准本身保证这总是成立的([basic.align]/p4)。

更新

我仔细研究了这个问题，并认为将请求的分配大小舍入到下一个alignment（正如OP建议的那样）是最佳解决方案。我已经在我的网站上更新了"short_alloc"。

template <std::size_t N>
char*
arena<N>::allocate(std::size_t n)
{
    assert(pointer_in_buffer(ptr_) && "short_alloc has outlived arena");
    n = align_up(n);
    if (buf_ + N - ptr_ >= n)
    {
        char* r = ptr_;
        ptr_ += n;
        return r;
    }
    return static_cast<char*>(::operator new(n));
}

对于一些特殊情况，你知道不需要最大限度对齐分配（例如vector<unsigned char>），可以简单地调整alignment。并且可以让short_alloc::allocate将alignof(T)传递给arena::allocate，并且assert(requested_align <= alignment)

template <std::size_t N>
char*
arena<N>::allocate(std::size_t n, std::size_t requested_align)
{
    assert(requested_align <= alignment);
    assert(pointer_in_buffer(ptr_) && "short_alloc has outlived arena");
    n = align_up(n);
    if (buf_ + N - ptr_ >= n)
    {
        char* r = ptr_;
        ptr_ += n;
        return r;
    }
    return static_cast<char*>(::operator new(n));
}

这将使您有信心，如果您将alignment向下调整，您没有将其调整得太低。

再次更新！

我已经根据这个优秀的问题更新了description和code这个分配器的内容（我忽略了这段代码多年）。

之前更新中提到的对齐检查现在是在编译时完成的（编译时错误总是优于运行时错误，即使是断言）。

现在，arena和short_alloc都以模板形式提供对齐方式，因此您可以轻松地自定义预期的对齐要求（如果您猜测得太低，则会在编译时捕获）。此模板参数默认为alignof(std::max_align_t)。

arena::allocate函数现在如下所示：

template <std::size_t N, std::size_t alignment>
template <std::size_t ReqAlign>
char*
arena<N, alignment>::allocate(std::size_t n)
{
    static_assert(ReqAlign <= alignment, "alignment is too small for this arena");
    assert(pointer_in_buffer(ptr_) && "short_alloc has outlived arena");
    auto const aligned_n = align_up(n);
    if (buf_ + N - ptr_ >= aligned_n)
    {
        char* r = ptr_;
        ptr_ += aligned_n;
        return r;
    }
    return static_cast<char*>(::operator new(n));
}

感谢别名模板(alias templates)，这个分配器比以往更易于使用。例如：

// Create a vector<T> template with a small buffer of 200 bytes.
//   Note for vector it is possible to reduce the alignment requirements
//   down to alignof(T) because vector doesn't allocate anything but T's.
//   And if we're wrong about that guess, it is a comple-time error, not
//   a run time error.
template <class T, std::size_t BufSize = 200>
using SmallVector = std::vector<T, short_alloc<T, BufSize, alignof(T)>>;

// Create the stack-based arena from which to allocate
SmallVector<int>::allocator_type::arena_type a;
// Create the vector which uses that arena.
SmallVector<int> v{a};

这并不一定是这些分配器的最终解决方案。但是希望这可以成为您构建自定义分配器的坚实基础。

- Howard Hinnant

---

@HowardHinnant 请在您的代码中添加许可信息，以便可以安全地使用它。大多数项目禁止使用未经许可的代码，即使是开源项目也是如此。 - Eloff

疯狂的想法：是否可以使用SFINAE和类似https://dev59.com/Z6nka4cB1Zd3GeqPPH8X的东西，使模板实现自动选择正确的对齐方式（即最小的2的幂，以确保正常工作）？也就是说：尝试alignment = 1，然后如果THIS_CODE_DOES_NOT_COMPILE（...创建容器并插入项的一些示例代码...），则通过模板递归尝试alignment = alignment * 2等等。递归基本情况设置为aligment = alignof（std :: max_align_t）。 - Don Hatch

为了使“这个分配器比以往更易于使用”的部分变得更加容易，建议如下：template struct HasA { WhatIHas what_i_has; }; template struct ShortContainer : private HasA, public Container { ShortContainer(): Container(this->what_i_has) {} }; template using ShortVector = ShortContainer>>; 然后可以简单地使用ShortVector<int> v;或ShortVector<int, 1000> v;。 - Don Hatch

另外值得注意的是：当使用此分配器与std::vector时，应立即调用reserve(BufSizeBytes/sizeof(T))，以避免意外的静默溢出到堆上。如果我们使用short_alloc的简化变体而不是溢出到堆上，则会变得明显。SmallVector类型的构造函数可能应该自动执行这样的reserve()（但不幸的是，这可能会使本答案的阐述有点混乱，因此最好在最后简要提及一下）。 - Don Hatch

对于SmallVector示例，我有一个建议：当我看到SmallVector<int, 1000>时，我立刻认为它是指1000个整数；我（也许还有其他人？）会惊讶地发现它实际上是指1000/ sizeof(int)个整数。如果模板参数改成MaxItems而不是BufSizeBytes，可能会减少这种惊讶的情况。 - Don Hatch