2
\$\begingroup\$

Edit 1 after first review: I changed to use malloc / free since apparently it's also easier to optimize than new[] / delete[] : https://godbolt.org/g/CZy28o ; of course this adds an additional requirement on the alignment.

template <class T>
struct pod_allocator
{
    static_assert(std::is_pod_v<T>, "can only be used with POD types");
    static_assert(alignof(T) <= alignof(std::max_align_t), "type must not have specific alignment requirements");
    using value_type = T;
    auto allocate(std::size_t num)  { return (T*) malloc(sizeof(T) * num); }
    void deallocate(T* p, std::size_t)   { free(p); }
};

The incentive here is to allow some compilers (clang as of clang-6.0 for instance) to remove allocations in some cases, by observing that they are able to optimize out new/delete pairs but not ::operator new/::operator delete pairs : see the following in https://godbolt.org/g/jumtCU

#include <algorithm>
#include <numeric>
#include <cinttypes>
int foo(int* src)
{
   constexpr int n = 10;    
   auto x = new int[n];
   for(int i = 0; i < n; i++)
   {
       if(i%2 == 0)
         x[i] = src[n - i - 1] * 2;
       else
         x[i] = src[i] * src[i];
   }
   int z = 0;
   if(x[1] < 1) z = 10; 
   else z = x[2] + x[4] - x[1] - x[3];

   delete[] x;

   return z;
}

While the vector version... well... produces "suboptimal" assembly: https://godbolt.org/g/cZvSRb .

#include <algorithm>
#include <numeric>
#include <cinttypes>
#include <vector>
int foo(int* src)
{
   constexpr int n = 10;    
   std::vector<int> x(n);
   for(int i = 0; i < n; i++)
   {
       if(i%2 == 0)
         x[i] = src[n - i - 1] * 2;
       else
         x[i] = src[i] * src[i];
   }
   int z = 0;
   if(x[1] < 1) z = 10; 
   else z = x[2] + x[4] - x[1] - x[3];

   return z;
}

Hence, here is the code of the allocator, which allows us to claim back much better codegen (https://godbolt.org/g/hvPY14) :

template <class T>
class pod_allocator
{
  public:
    static_assert(std::is_pod_v<T>, "can only be used with POD types");
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using is_always_equal = std::true_type;

    constexpr T* address(T& value) const noexcept { return &value; }
    constexpr const T* address(const T& value) const noexcept { return &value; }

    constexpr auto max_size() const noexcept {
        return std::numeric_limits<std::size_t>::max() / sizeof(T);
    }

    auto allocate(std::size_t num) { return new T[num]; }
    void deallocate(T* p, std::size_t) { delete[] p; }

    constexpr void construct(T*, const T&) noexcept { }
    constexpr void destroy(T*) noexcept { }
};

template<class T1, class T2>
constexpr bool operator==(const pod_allocator<T1>&, const pod_allocator<T2>&) noexcept { return true; }

template<class T1, class T2>
constexpr bool operator!=(const pod_allocator<T1>&, const pod_allocator<T2>&) noexcept { return false; }

template<typename T>
using pod_vector = std::vector<T, pod_allocator<T>>;

Are there some subtle bugs that I could be introducing this way ? (not counting of course the lack of value-initialization, which is, in this case, a feature and not a bug).

\$\endgroup\$
  • \$\begingroup\$ I'm no expert but what about this approach? \$\endgroup\$ – yuri May 28 '18 at 12:44
  • 1
    \$\begingroup\$ deallocate leaks memory because you're using delete and not delete[]. \$\endgroup\$ – monkey0506 Jan 27 at 4:34
  • 2
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. That being said, @monkey0506's comment should have been a review answer. As no answer is invalidated, it's fine, but please keep this in mind for future edits. \$\endgroup\$ – Zeta Jan 27 at 10:48
5
\$\begingroup\$

If you're going to roll your own allocator in C++17, you can save yourself a lot of grief by just leaving everything to default. The only things you need to include are value_type, allocate(), deallocate(), and operators == and !=.

In fact, I believe by not using the defaults, you've introduced a nasty little bug. Try doing this: auto v = pod_vector<int>(5, 42);. This should create a vector with five ints, all set to 42. But without construct() properly defined, who knows what will happen?

My advice:

  • Your allocator should be 4 lines.
    1. the static_assert
    2. value_type
    3. allocate()
    4. deallocate()

(And you need the == and != comparisons too.)

At the very least, either remove construct() or give it a sensible implementation (i.e., placement new). With destroy() it's less of an issue because you're only dealing with PODs.


AFTER EDIT 1: I'd wager the reason you're seeing better code generation for malloc() than new is that new throws std::bad_alloc automatically when it can't allocate.

I suspect if you changed your allocate() function to:

auto allocate(std::size_t num)  {
    auto const p = (T*) malloc(sizeof(T) * num);
    if (!p)
        throw std::bad_alloc{};
    return p;
}

you'd see a very different code gen situation.

As it stands, if you get an allocation failure, you're just returning a null pointer... which will lead to undefined behaviour, because allocate() must return a pointer to allocated memory.

\$\endgroup\$
  • \$\begingroup\$ I changed by taking in account your comments. Thanks ! all the tutorials for allocators I could find had all the members ; it's much clearer like this. \$\endgroup\$ – Jean-Michaël Celerier May 28 '18 at 17:58
  • \$\begingroup\$ Hmmm.. regarding your original comment: in practice, both libc++ and MSVC's vector required me to implement == and != (both for msvc and only != for libc++). \$\endgroup\$ – Jean-Michaël Celerier Jun 10 '18 at 19:38
  • \$\begingroup\$ I just checked the standard, and you are correct: the bare minimum is value_type, allocate(), deallocate(), ==, and !=. I'll fix up my answer. (Note also I made a typo in the list! You need deallocate(), not destroy()!) \$\endgroup\$ – indi Jun 12 '18 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.