Simple Pool Allocator

Question

This is a simple pool allocator, based (to at least some degree) on a previous answer. The basic idea is pretty simple: allow a user to allocate objects of some type quickly (in relatively large contiguous chunks) and only free objects when the allocator itself is freed, then destroy all the objects and free the memory they occupy.

#include <iostream>
#include <vector>

template <class T, size_t T_per_page = 200>
class Allocator {
    const size_t pool_size = T_per_page * sizeof(T);
    std::vector<T *> pools;
    size_t next_pos;

    void alloc_pool() {
        next_pos = 0;       
        void *temp = operator new(pool_size);
        pools.push_back(static_cast<T *>(temp));
    }

public:
    Allocator() {
        alloc_pool();
    }

    T* operator()(T const &x) {
        if (next_pos == T_per_page)
            alloc_pool();

        T *ret = new(pools.back() + next_pos) T(x);
        ++next_pos;
        return ret;
    }

    ~Allocator() {
        while (!pools.empty()) {
            T *p = pools.back();
            for (size_t pos = T_per_page; pos > 0; --pos)
                p[pos - 1].~T();
            operator delete(static_cast<void *>(p));
            pools.pop_back();
        }
    }
};

#ifdef TEST

struct list_node {
    int val;
    list_node *next;

    list_node(int x) : val(x), next(nullptr) {}

    friend std::ostream &operator<<(std::ostream &os, list_node const &n) { return os << n.val; }
};

Allocator<list_node> alloc;

int main() {
    for (int i = 0; i < 20; i++) {
        list_node *j = alloc(i + 1000);
    }
}

#endif

I'd welcome any and all suggestions (including adding specialization to avoid executing destructors on trivially destructible types). I'm also wondering (sort of thinking out loud) whether it would make sense to use a geometric allocation strategy, similar to std::vector's, to (perhaps) fit allocation time to size more effectively.

Answer 1

Allocation of raw memory

Rather than using operator new you could use std::get_temporary_buffer<T>(n). This allocates contiguous "correctly aligned" storage for enough memory to store approx n objects of type T (its non binding contract read documents).

Constructor

It may be more efficient to use normal constructor than the copy constructor. You should also provide the move constructor.

T* operator()(T&& x);
T* operator()(T const &x);
template<typename... Args>
T* operator()(Args... args);

Destructor

Yes you can optimize the destructor if Ts destructor is guranteed to do nothing.

template<typename T>
struct SimpleDestructableTrivialy
{
    static constexpr bool value = std::is_trivially_destructible<T>::value;
};
template<typename T, bool = SimpleDestructableTrivialy<T>::value>
class SimpleDestroy
{
    public:
        void destroyElements(T* p, std::size_t T_per_page);
};
template<typename T>
class SimpleDestroy<T, true>
{
    public:
        void destroyElements(T* p, std::size_t T_per_page) {}
};
template<typename T>
class SimpleDestroy<T, false>
{
    public:
        void destroyElements(T* p, std::size_t T_per_page)
        {
            for (size_t pos = T_per_page; pos > 0; --pos)
                p[pos - 1].~T();
        }
};

Answer 2

The strategy for the operator() function is flawed, I think.

T* operator()(T const &x) {
              ^^^^^^^^^^^

You are forcing the user to construct a temporary object before they can use the allocator.

It will be better to leave Allocator to do couple of things and do them well. Allocate memory when needed and deallocate memory when it is destructed.

You can let the client classes use Allocator to implement operator new and operator delete.

I would add a function template that returns an Allocator.

template <typename T>
Allocator<T>& getAllocator()
{
   static Allocator<T> allocator;
   return allocator;
}

and let client code use it.

struct list_node {

    // operator new and operator delete are there for the
    // sake of symmetry. operator delete is a noop since it
    // doesn't need to do anything.
    void* operator new(size_t s)
    {
       return getAllocator<list_node>().allocate();
    }

    void operator delete(void*)
    {
    }
};

PS

My suggestion for getAllocator can be a problem if used in an interactive application where objects are constructed and destructed based on user action. For such use cases, the memory allocated by the application keep on increasing. There are other ways to manage the life times of Allocator objects for such applications.

Your code, updated with my suggested changes

#include <iostream>
#include <vector>

template <class T, size_t T_per_page = 200>
class Allocator {
    const size_t pool_size = T_per_page * sizeof(T);
    std::vector<T *> pools;
    size_t next_pos;

    void alloc_pool() {
        next_pos = 0;       
        void *temp = operator new(pool_size);
        pools.push_back(static_cast<T *>(temp));
    }

public:
    Allocator() {
        alloc_pool();
    }

    void* allocate() {
        if (next_pos == T_per_page)
            alloc_pool();

        void *ret = pools.back() + next_pos;
        ++next_pos;
        return ret;
    }

    ~Allocator() {
        while (!pools.empty()) {
            T *p = pools.back();
            for (size_t pos = T_per_page; pos > 0; --pos)
                p[pos - 1].~T();
            operator delete(static_cast<void *>(p));
            pools.pop_back();
        }
    }
};

template <typename T>
Allocator<T>& getAllocator()
{
   static Allocator<T> allocator;
   return allocator;
}


#ifdef TEST

struct list_node {
    int val;
    list_node *next;

    // operator new and operator delete are there for the
    // sake of symmetry. operator delete is a noop since it
    // doesn't need to do anything.
    void* operator new(size_t s)
    {
       return getAllocator<list_node>().allocate();
    }

    void operator delete(void*)
    {
    }

    list_node(int x) : val(x), next(nullptr) {}

    friend std::ostream &operator<<(std::ostream &os, list_node const &n) { return os << n.val; }
};

int main() {
    for (int i = 0; i < 20; i++) {
        list_node *j = new list_node(i + 1000);
        delete j;
    }
}

#endif

Answer 3

Since specialization on trivially destructible types was mentioned, I want to focus on pool growth strategies.

In my opinion, it would be better to make it customizable, so that the strategy is not mandated. Adding it as next template parameter would be good, but it faces a few challenges.

Adding growth factor

I think this is good way, although it requires a bit of math to track the size of the pool (sum of geometric sequence). The problem with that is we need to add 2 template parameters in order to support non integral growth factors, but anyway non integral growth factors rarely make any sense (if factor < 1, sometime next pool size will hit zero, if factor > 1, sometimes it will allocate less than expected). The change will affect only pool_size (it won't be const anymore), alloc_pool() and destructor:

void alloc_pool() {
    next_pos = 0;
    pool_size *= factor;
    void *temp = operator new(pool_size);
    pools.push_back(static_cast<T *>(temp));
}

~Allocator() {
    size_t count = pool_size / sizeof(T);
    while (!pools.empty()) {
        T *p = pools.back();
        for (size_t pos = count; pos > 0; --pos)
            p[pos - 1].~T();
        operator delete(static_cast<void *>(p));
        pools.pop_back();
        count /= factor;
    }

Adding functor

Now, the template will always require argument, because it is impossible to make lambda as default template argument. May be shipping default function with the Allocator would make sense, but it is vague still.

Adding policy

This is the best way in my opinion, but it bumps header. Every time we want to allocate next pool we call operator size_t() of the policy. This raises problem when we want to deallocate memory: we will need some way to reverse the sequence. After trying to write it multiple times, I found the most convenient interface for the policy:

• Pre and post increment operators that return size_t. Only pre-increment is called to obtain the capacity in count objects of the next pool.

• Pre and post decrement operators that return size_t. Post decrement
  is called for deallocation.

• operator size_t() to make it convenient to check current pool size.
  Called in different places.

This enables great flexibility. Users may deploy any policy they want.

So, complete code, with destroyer template shamelessly stolen from @LokiAstari:

#pragma once
#include <vector>

template<typename T>
struct SimpleDestructableTrivialy
{
    static constexpr bool value = std::is_trivially_destructible<T>::value;
};
template<typename T, bool = SimpleDestructableTrivialy<T>::value>
class SimpleDestroy
{
public:
    void destroyElements(T* p, std::size_t T_per_page);
};
template<typename T>
class SimpleDestroy<T, true>
{
public:
    void destroyElements(T* p, std::size_t T_per_page) {}
};
template<typename T>
class SimpleDestroy<T, false>
{
public:
    void destroyElements(T* p, std::size_t T_per_page)
    {
        for (size_t pos = T_per_page; pos > 0; --pos)
            p[pos - 1].~T();
    }
};

template <size_t T_per_page>
class LinearGrowth
{
public:
    size_t operator++()
    {
        return T_per_page;
    }

    size_t operator++(int)
    {
        return T_per_page;
    }

    operator size_t()
    {
        return T_per_page;
    }

    size_t operator--()
    {
        return T_per_page;
    }

    size_t operator--(int)
    {
        return T_per_page;
    }
};

template <class T, typename GrowthPolicy = LinearGrowth<200>>
class Allocator {
    size_t pool_size = sizeof(T); //leave it for now
    std::vector<T*> pools;

    size_t next_pos;

    GrowthPolicy policy;
    SimpleDestroy<T> destroyer;

    void alloc_pool() {
        next_pos = 0;
        pool_size *= ++policy;
        void *temp = operator new(pool_size);
        pools.push_back(static_cast<T *>(temp));
    }
public:
    Allocator() {
        alloc_pool();
    }

    template <typename ... ArgsType>
    T* operator()(ArgsType ... args) {
        if (next_pos == policy)
        {
            alloc_pool();
        }

        T *ret = new(pools.back() + next_pos) T(std::forward<ArgsType>(args)...);
        ++next_pos;
        return ret;
    }

    ~Allocator() {
        while (!pools.empty())
        {
            T* p = pools.back();
            destroyer.destroyElements(p, policy--);
            operator delete(static_cast<void *>(p));
            pools.pop_back();
        }
    }
};

Side notes

I had a look at VC++ std::get_temporary_buffer() implementation, so ... The story is that after checks using if statements it tries to allocate memory each time by decreasing the size by 2, and stopping when succeeded. It still invokes operator new, so I think std::get_temporary_buffer() is not mature enough for now to use it.

May be some variables have to be merged or changed, for example pool_size (because there is no T_per_page now).

The templates can increase compilation time, thus light version might be needed.

There might be very bad names in my code, but I couldn't come up with anything better.