Is Stephen Lavavej's Mallocator the same in C++11?

Question

8 years ago, Stephen Lavavej published this blog post containing a simple allocator implementation, named the "Mallocator". Since then we've transitioned to the era of C++11 (and soon C++17) ... does the new language features and rules affect the Mallocator at all, or is it still relevant as is?

Purgative

It's much much simpler now. – Tannatannage

@KerrekSB: Link ? Explanation? – Purgative

Maybe look at the allocator example half-way down this guide and replace all mentions of "arena" with malloc/free... – Tannatannage

@KerrekSB: So, no more construct()? – Purgative

No, construct has a default implementation now as part of the allocator traits. You can specify it if you need it to do something non-default (e.g. like scoped_allocator does). – Tannatannage

Answer 1

STL himself has an answer to this question in his STL Features and Implementation techniques talk at CppCon 2014 (Starting at 26'30).

The slides are on github.

I merged the content of slides 28 and 29 below:

#include <stdlib.h> // size_t, malloc, free
#include <new> // bad_alloc, bad_array_new_length
template <class T> struct Mallocator {
  typedef T value_type;
  Mallocator() noexcept { } // default ctor not required
  template <class U> Mallocator(const Mallocator<U>&) noexcept { }
  template <class U> bool operator==(
    const Mallocator<U>&) const noexcept { return true; }
  template <class U> bool operator!=(
    const Mallocator<U>&) const noexcept { return false; }

  T * allocate(const size_t n) const {
      if (n == 0) { return nullptr; }
      if (n > static_cast<size_t>(-1) / sizeof(T)) {
          throw std::bad_array_new_length();
      }
      void * const pv = malloc(n * sizeof(T));
      if (!pv) { throw std::bad_alloc(); }
      return static_cast<T *>(pv);
  }
  void deallocate(T * const p, size_t) const noexcept {
      free(p);
  }
};

Note that it handles correctly the possible overflow in allocate.

Jodee

should it be std::numeric_limits<size_t>::max() rather than static_cast<size_t>(-1) though? – Purgative

@Purgative It is guaranteed by the standard to be the same: size_t have to respect mod 2^N arithmetic where N is the number of bits of size_t. – Jodee

It's still bad coding IMHO to use the latter rather than the former. – Purgative

@Purgative I Agree. – Jodee

@Purgative I think std::list requires other methods of an allocator to be defined like rebind. – Openmouthed

Answer 2

As @kerrek suggested, here is a Mallocator that is based off the linked arena allocator with the arena part deleted.

template<class T>
struct Mallocator11 {
  using value_type = T;
  using pointer = T*;
  using propagate_on_container_copy_assignment = std::true_type;
  using propagate_on_container_move_assignment = std::true_type;
  using propagate_on_container_swap = std::true_type;

  Mallocator11(Mallocator11 const&) = default;
  Mallocator11& operator=(Mallocator11 const&) = default;
  Mallocator11()=default;
  template<class U>
  Mallocator11(Mallocator11<U> const&) noexcept {}
  template<class U>
  Mallocator11& operator=(Mallocator11<U> const&) noexcept {return *this}


  pointer allocate(std::size_t n) {
    if (std::size_t(-1) / sizeof(T) < n)
      throw std::bad_array_new_length(); // or something else
    if (!n) return nullptr; // zero means null, not throw
    if(auto*r= static_cast<pointer>(malloc(n * sizeof(T))))
      return r;
    throw std::bad_alloc();
  }
  void deallocate(pointer p, std::size_t n) {
    free(p);
  }
  template<class U>
  bool operator==(Mallocator11<U> const& rhs) const {
    return true;
  }
  template<class U>
  bool operator!=(Mallocator11<U> const& rhs) const {
    return false;
  }
};

Lots less code. Some traits for propogation.

Extravascular

Can you elaborate a bit about the overflow detection and when it may or may not be needed? – Purgative

allocate need to throw on error; it can't return null. – Wooded

The friend declaration and cross-type assignment are extraneous. It would be a good idea to if (std::size_t(-1) / sizeof(T) < n) throw bad_alloc(); in allocate to avoid buffer overflows. And what @Wooded said. – Loydloydie

By the way, there's a new is_always_equal member predicate now that can perhaps substitute for the POC* traits. – Tannatannage

@KerrekSB Not yet. Some container requirements are still stated in terms of POCMA. Meanwhile, is_always_equal is already true for empty allocators. – Wooded

@casey there is something different I should throw rather than bad alloc, no? Going to concert, next edit in hours. – Extravascular

I think a bad_array_new_length is the correct exception to throw. see my answer and the code from STL himself. – Jodee

@Jodee There really is no required behavior in this case: It's a precondition that n <= std::allocator_traits<Mallocator11<T>>::max_size(), which defaults to std::allocator_traits<Mallocator11<T>>::size_type(-1) / sizeof(T). That said, I think both assert and throw are better ways to handle the precondition violation than allocating a small buffer that may be overflowed. bad_array_new_length is a good choice of exception to throw since it's derived from bad_alloc; callers that care can distinguish them, callers that don't can ignore the difference. – Loydloydie

@Loydloydie I don't think there is a precondition violation. According to N4527 C++17 draft, There is no precondition to allocate in 17.6.3.5: "Memory is allocated for n objects of type T but objects are not constructed. allocate may raise an appropriate exception.181[ Note: If n == 0, the return value is unspecified. —end note ]" – Jodee

@Jodee The allocator requirements table (table 28 in N4582) says that a.max_size() is "The largest value that can be meaningfully passed to X::allocate()." – Loydloydie

And ewww "appropriate exception." Could that phrase be any more vague? – Loydloydie

@Loydloydie max_size just indicates the value after which you will get an exception. – Jodee

@Jodee "The largest value that can be meaningfully passed to allocate" is not the same thing as "The largest value that can be passed to allocate without causing an exception." The requirements literally say that allocate(max_size() + 2) has no meaning. – Loydloydie

@Loydloydie to be fair, if max_size() is a size_t, and max_size()+2 happens to equals1, then it has a meaning (size_t is mod-2^n for some n). Not a useful meaning, but because max_size()+2<max_size() it has a meaning. Wait, this isn't fair: this is stupidly pedantic. I knew it was one of the two. So hard to tell sometimes. ;) – Extravascular

It looks like std::size_t(-1) is being used to get the max value for size_t, but if that's what you want, wouldn't std::numeric_limits<std::size_t>::max be a better fit, and more portable? – Azide

@Azide No; size_t is guaranteed unsigned, and unsigned is guaranteed to be math mod 2^n for some n. Thus unsigned_type(-1) is always the max value of any unsigned type. As a slight bonus, it does not require including the standard header file that has numeric_limits in it. – Extravascular

@Yakk Sorry, I should have said "When sizeof(T) > 1, the requirements literally say that allocate(max_size() + 2) has no meaning" ;) – Loydloydie