Hinnant's short_alloc and alignment guarantees

Question

I have recently come across Howard Hinnant's short_alloc and this is the single best example of custom allocators I have seen.

But as I spent more time studying the code to integrate it in my personal project, it occurred to me that the arena class, providing the stack-based allocations, might not always return properly aligned memory. In fact, I fear that only the first allocation is guaranteed to be suitably aligned (as the buffer itself has a forced alignment), see below relevant code fragments:

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

I can think of a few ways to fix this (at the cost of some memory wastage), the easiest being to round the size in the allocate/deallocate function to a multiple of alignment.

But before changing anything, I would like to make sure that I am not missing something here...

Answer 1

This code was written before I had std::max_align_t in my toolbox (which now lives in <cstddef>). I would now write this as:

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

which on my system is exactly equivalent to the current code, but now more portable. This is the alignment which new and malloc are guaranteed to return. And once you have this "maximally aligned" buffer, you can put an array of any one type in it. But you can't use the same arena for different types (at least not different types that have different alignment requirements). And for that reason, perhaps it would be best to template arena on a second size_t, which is equal to the the alignof(T). In that way you can prevent the same arena from being accidentally used by types with differing alignment requirements:

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

Assuming each allocation from arena has the same alignment requirements, and assuming the buffer is maximally aligned, then every allocation from the buffer will be suitably aligned for T.

E.g. on my system alignof(std::max_align_t) == 16. A buffer with this alignment can hold arrays of:

• Types with alignof == 1.
• Types with alignof == 2.
• Types with alignof == 4.
• Types with alignof == 8.
• Types with alignof == 16.

As some environment may support types that have "super alignment" requirements, an added safety precaution would be to add (say within short_alloc):

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

If you are super paranoid you could also check that alignof(T) is a power of 2, though the C++ standard itself guarantees that this will always be true ([basic.align]/p4).

Update

I have taken a closer look at this problem and believe that rounding the requested allocation size up to the next alignment (as the OP suggested) is the best solution. I have updated "short_alloc" to do that on my website.

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

For special situations where you know that you don't need maximally aligned allocations (e.g. vector<unsigned char>), one can simply tweak alignment appropriately. And one could also have short_alloc::allocate pass alignof(T) to arena::allocate and 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));
}

This would give you confidence that if you adjusted alignment downward, you didn't adjust it too far downward.

Update Again!

I've updated the description and code of this allocator quite a bit because of this excellent question (I had neglected this code for years).

The alignment check mentioned in the previous update is now done at compile-time (compile-time errors are always superior to run-time errors, even asserts).

Both the arena and short_alloc is now templated on alignment so that you can easily customize the alignment requirements you anticipate (and if you guess too low it is caught at compile-time). This template parameter is defaulted to alignof(std::max_align_t).

The arena::allocate function now looks like:

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

Thanks to alias templates, this allocator is easier to use than ever. For example:

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

This isn't necessarily the final word in such allocators. But hopefully this is a solid foundation upon which you can build your custom allocators.