Skip to main content
added 459 characters in body
Source Link
G. Sliepen
  • 69.3k
  • 3
  • 75
  • 180

Your allocator requires each node, once allocated, to be at the same place in memory for the rest of its life. If you resize a std::vector or use realloc(), the storage might be moved. This is why you are using chunks. However, there is a STL container that gives you stable pointers andand the ability to resize: std::deque. This allows you to get rid of chunks.

If you want to store small objects (for example, struct message is not that big), then instead of having a linked list of free nodes, it might be better to use (a tree of) bitmaps to store which elements of the chunk are used or not. Finding a region of consecutive free elements might also be much easier this way.

Use a testing framework

Consider using an existing (unit) testing framework, like CppUnit or Google Test, and a benchmarking framework like Google Benchmark. You still need to write the actual tests yourself, but they take away some of the burden and impose some order to what you are doing.

Your allocator requires each node, once allocated, to be at the same place in memory for the rest of its life. If you resize a std::vector or use realloc(), the storage might be moved. This is why you are using chunks. However, there is a STL container that gives you stable pointers and the ability to resize: std::deque. This allows you to get rid of chunks.

If you want to store small objects (for example, struct message is not that big), then instead of having a linked list of free nodes, it might be better to use (a tree of) bitmaps to store which elements of the chunk are used or not. Finding a region of consecutive free elements might also be much easier this way.

Your allocator requires each node, once allocated, to be at the same place in memory for the rest of its life. If you resize a std::vector or use realloc(), the storage might be moved. This is why you are using chunks. However, there is a STL container that gives you stable pointers and the ability to resize: std::deque. This allows you to get rid of chunks.

If you want to store small objects (for example, struct message is not that big), then instead of having a linked list of free nodes, it might be better to use (a tree of) bitmaps to store which elements of the chunk are used or not. Finding a region of consecutive free elements might also be much easier this way.

Use a testing framework

Consider using an existing (unit) testing framework, like CppUnit or Google Test, and a benchmarking framework like Google Benchmark. You still need to write the actual tests yourself, but they take away some of the burden and impose some order to what you are doing.

Source Link
G. Sliepen
  • 69.3k
  • 3
  • 75
  • 180

Don't abbreviate unnecessarily

Most of the names you've chosen for variables and functions look fine to me, but there are some weird, unnecessary abbreviations:

  • resiz -> just write resize
  • alloc_sz -> I would write alloc_size or size

Some abbreviations are quite commonly used so I'd keep those (like Elems and alloc instead of Elements and allocation). However, be consistent: why is it nElems but m_MaxElements?

Create a class chunk

Your pool consists of multiple chunks, and each chunk is an array of nodes. It makes sense to make a proper type for chunks as well. While you are at it, avoid doing manual memory allocations, and let std::vector do it for you. The alloc_chunk() function can become the constructor of chunk.

struct chunk {
    std::vector<node> nodes;
    chunk(size_t nElems): nodes(nElems) {
        for (auto &node: nodes)
            node.next = &node + 1;
        nodes.back().next = nullptr;
    }
};

But this also leads me to:

Consider using a std::deque to store nodes

Your allocator requires each node, once allocated, to be at the same place in memory for the rest of its life. If you resize a std::vector or use realloc(), the storage might be moved. This is why you are using chunks. However, there is a STL container that gives you stable pointers and the ability to resize: std::deque. This allows you to get rid of chunks.

template <typename T>
class pool {
    struct node {/* same as before */};
    std::deque<node> m_Nodes;
    node *m_Head{};

public:
    pool(pool const&)               = delete;
    pool& operator=(pool const&)    = delete;

    pool()                          = default;
    pool(pool&& o)                  = default;
    ...
    T *alloc() {
        if (!m_Head) {
            m_Nodes.emplace_back({});
            m_Head = &m_Nodes.back();
        }
        ...
    }
    ...
};

Performance

Your allocator is very good when storing large objects and when the game doesn't need to allocate large batches of objects at a time. However, it has the overhead of one pointer per element, so if you are storing small objects, you might be wasting a lot of memory. Furthermore, there is no better way to allocate a batch of objects than to allocate them one by one.

If you want to store small objects (for example, struct message is not that big), then instead of having a linked list of free nodes, it might be better to use (a tree of) bitmaps to store which elements of the chunk are used or not. Finding a region of consecutive free elements might also be much easier this way.