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));
}

我可以想出几种方法来解决这个问题(以一些内存浪费为代价),最简单的方法是size将allocate/deallocate函数四舍五入到多个alignment.

但在改变任何事情之前,我想确保我在这里没有遗漏一些东西......

Answer 1

这段代码是std::max_align_t在我的工具箱(现在存在<cstddef>)之前编写的.我现在写这个:

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

在我的系统上,它与当前代码完全相同,但现在更具可移植性.这是对齐,new并malloc保证返回.一旦你有了这个"最大对齐"缓冲区,就可以在其中放入任何一种类型的数组.但是你不能arena对不同的类型使用相同的类型(至少没有不同的类型具有不同的对齐要求).出于这个原因,也许最好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向下调整,你没有向下调整太远.

再次更新!

我已经更新了这个分配器的描述和代码,因为这个优秀的问题(我多年来一直忽略了这个代码).

上一次更新中提到的对齐检查现在在编译时完成(编译时错误总是优于运行时错误,甚至是断言).

无论是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));
}

多亏了别名模板,这个分配器比以往更容易使用.例如:

// 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};

这不一定是这种分配器中的最后一个词.但希望这是一个可以构建自定义分配器的坚实基础.