Fixed-size block allocator

Question

I have written a fixed-size block allocator implementation and would like some feedback as to what I could improve in my code and coding practices. Your comments or notes are welcomed!

An auxiliary allocator (non-typed, instead unique for the given size of a chunk; without necessary interface for STL containers):

#include <iostream>
#include <list>
#include <vector>

template <size_t ChunkSize>
class TFixedAllocator {
    union TNode { // union
        char data[ChunkSize];
        TNode *next; // free chunks of memory form a stack; pointer to the next (or nullptr)
    };

    TNode *free; // the topmost free chunk of memory (or nullptr)
    std::vector<TNode*> pools; // all allocated pools of memory
    int size = 1; // size of the last allocated pool of memory
    const int MAX_SIZE = 1024;

    void new_pool() { // allocate new pool of memory
        if (size < MAX_SIZE) {
            size *= 2;
        }
        free = new TNode[size];

        // form a stack of chunks of this pool
        pools.push_back(free);
        for (int i = 0; i < size; ++i) {
            free[i].next = &free[i+1];
        }
        free[size-1].next = nullptr;
    }
    TFixedAllocator() { // private for singleton
        new_pool();
    }
public:
    TFixedAllocator(const TFixedAllocator&) = delete; // for singleton
    static TFixedAllocator& instance () { // singleton
        static TFixedAllocator instance;
        return instance;
    }
    void* allocate() {
        if (!free) {
            new_pool();
        }
        TNode* result = free; // allocate the topmost element (saved in free)
        free = free->next; // and pop it from the stack of free chunks
        return static_cast<void*>(result);
    }
    void deallocate(void* elem) {
        TNode* node = static_cast<TNode*>(elem);

        // add to the stack of chunks
        node->next = free;
        free = node;
    }
    ~TFixedAllocator() {
        for (auto ptr : pools) {
            delete ptr;
        }
    }
};

An allocator wrapper for STL containers:

template <class T>
class TFSBAllocator {
public:
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    template <class U>
    class rebind {
    public:
        using other = TFSBAllocator<U>;
    };

    pointer allocate(size_t n) {
        if (n == 1) {
            return static_cast<T*>(TFixedAllocator<sizeof(T)>::instance().allocate());
        } else {
            return std::allocator<T>().allocate(n);
        }
    }
    void deallocate(pointer p, size_t n) {
        if (n == 1) {
            TFixedAllocator<sizeof(T)>::instance().deallocate(static_cast<void*>(p));
        } else {
            return std::allocator<T>().deallocate(p, n);
        }
    }
    void construct(pointer p, const_reference t) {
        new (p) T(t);
    }
    void destroy(pointer p) {
        p->~T();
    }
};

A tester:

#include <chrono>
using namespace std::chrono;

template <class List>
void test(std::string comment, List l) {
    std::cout << comment;
    auto start_time = high_resolution_clock::now();
    for (int i = 0; i < 1e7; ++i) {
        l.push_back(i);
    }
    auto end_time = high_resolution_clock::now();
    std::cout << duration_cast<milliseconds>(end_time - start_time).count() << "ms" << std::endl;
}

int main() {
    // CodeBlocks 12.13, Release mode
    test("std::allocator: ", std::list<int>()); // std::allocator: 1816ms
    test(" TFSBAllocator: ", std::list<int, TFSBAllocator<int>>()); // TFSBAllocator: 204ms
}

By the way, what is about thread-safety?

Answer 1

1. About thread safety: it is not thread safe. There is nothing that prevents member-functions such as TFixedAllocator::allocate, TFixedAllocator::new_pool and others to be executed by multiple threads at the same time. Inside these functions several variables are modified. Modifying them from multiple threads without synchronization is an undefined behavior according to the C++ standard.

   How to fix it? The easiest way to do it is to use one std::mutex for the allocate and deallocate member-functions of the TFixedAllocator class(acquiring it in the very beginning of the function and releasing it in the very end). It is convenient to use an std::lock_guard for this purpose. Something like this:

   template <size_t ChunkSize>
   class TFixedAllocator {
       ...
   
       std::mutex allocator_mutex;
   
   public:
       ...
   
       void* allocate() {
           std::lock_guard<std::mutex> allocator_lock_guard(allocator_mutex);
           if (!free) {
               new_pool();
           }
           TNode* result = free; // allocate the topmost element (saved in free)
           free = free->next; // and pop it from the stack of free chunks
           return static_cast<void*>(result);
       }
   
       void deallocate(void* elem) {
           std::lock_guard<std::mutex> allocator_lock_guard(allocator_mutex);
           TNode* node = static_cast<TNode*>(elem);
   
           // add to the stack of chunks
           node->next = free;
           free = node;
       }
   };
   

2. Functions and variables naming: it is conventional to name functions with a verb(to describe an action). I would use get_instance instead of instance and create_new_pool instead of new_pool, for example.

3. You TFixedAllocator class violates the single responsibility principle. Despite managing memory allocation(which is its main responsibility) it also implicitly implements some data structure(a stack?(I mean things related to the union TNode, the free pointer and so on)). It makes the code rather hard to follow: those operations with free and next pointers are not easy to understand(it is not clear why they are performed in the first place). There are two ways to fix it:

   • Create a separate class that implements this data structure.

   • Use a standard container. If what you need is a stack, std::stack is a good option(again, I'm not completely sure if it is feasible because I do not fully understand how this data structure is used in your code).

4. Writing useless comments is definitely a bad practice. For instance, union TNode { // union doesn't make much sense: it is absolutely clear that it is a union without any comments. I'd recommend simply deleting comments like this one. Comments inside a function that tell what a block of code does, like here:

   void deallocate(void* elem) {
       TNode* node = static_cast<TNode*>(elem);
   
       // add to the stack of chunks
       node->next = free;
       free = node;
   }
   

   usually indicate that this block of code should have been a separate function(in this case, as I have mentioned before, there should probably be another class that implements this data structure). In general, you should try to write self-documenting code.

5. Spacing and indentation: separating different functions with an empty line makes the code more readable.

Answer 2

There is no need in thread safety. Such high-speed custom allocator should be dedicated to a single thread. I can't imagine a good use case where it is better to have one shared multi-threaded allocator, rather than per-thread allocators. Memory is cheap, CPU time is valuable.

Comments, spacing and indentation are subject of chit chat.

I don't like implicit fallback to malloc(). If by design it is required to be fast, it must be fast in all cases. "Sometimes yes, sometimes no" is not the decision of good design. Either make it to work in all cases or prohibit usage of n > 1.