3
\$\begingroup\$

I wrote this memory pool as a code sample for a job interview. It provides a per-class memory pool that can offer faster runtime performance for classes that need to be traversable and (de)allocatable during runtime.

Specifically, it provides in-order traversal of the allocated data blocks, to improve cache effectiveness. Both allocation and deallocation are \$O(1)\$ operations. Traversal of the allocated blocks is linear in the number of allocated blocks, with a one-time potentially full traversal of the pool upon the first call to begin() after (de)allocation.

The pool stores metadata about the (un)allocated data in two structures both store in a singly linked list. The list of free blocks behaves like a stack: upon an allocation request a single block is popped off the front and upon deallocation a single block is pushed onto it. The list of allocated blocks functions as a singly linked list, and is mainly used for efficient traversal.

Any suggestions? Obvious issues? Glaring mistakes?

#pragma once

#include <iostream>
#include <iterator>
#include <cassert>

template<class T>
class Pool {

    friend class iterator;

    private:
        struct Node {
            T* data;
            Node* next;
            bool alloc;
        };

        unsigned int size;              ///< The total number of instances that fit in the pool
        unsigned int nrOfAllocs;        ///< How many instances have been allocated
        T* pool;                        ///< Starting address of the data block
        Node* metadata;                 ///< Storage for the free and allocated block list
        Node* firstFree, *firstAlloc;   ///< Pointers to the first blocks of both lists
        bool dirty;                     ///< Flag that is set upon (de)allocation, indicates that cleanup() should be called
        static Node EndNode;            ///< Used by the iterator

    public:
        class iterator : public std::iterator<std::forward_iterator_tag, T> {

            friend class Pool;

            public:
                bool operator == (iterator const& rhs) const {return node->data == (*rhs);}
                bool operator != (iterator const& rhs) const {return node->data != (*rhs);}
                bool operator <  (iterator const& rhs) const {return node->data < (*rhs);}
                bool operator <= (iterator const& rhs) const {return node->data <= (*rhs);}
                bool operator >  (iterator const& rhs) const {return node->data > (*rhs);}
                bool operator >= (iterator const& rhs) const {return node->data >= (*rhs);}
                iterator operator ++ () {
                    node = node->next == nullptr ? &Pool::EndNode : node->next;
                    return (*this);
                }
                iterator operator ++ (int){
                    iterator original(*this);
                    node = node->next == nullptr ? &Pool::EndNode : node->next;
                    return original;
                }

                T* operator * () const {
                    return node->data;
                }

            private:
                iterator(Pool::Node* node):node(node){}
                Pool::Node* node;
        };

        class const_iterator : public std::iterator<std::forward_iterator_tag, const T> {

            friend class Pool;

            public:
                bool operator == (const_iterator const& rhs) const {return node->data == (*rhs);}
                bool operator != (const_iterator const& rhs) const {return node->data != (*rhs);}
                bool operator <  (const_iterator const& rhs) const {return node->data < (*rhs);}
                bool operator <= (const_iterator const& rhs) const {return node->data <= (*rhs);}
                bool operator >  (const_iterator const& rhs) const {return node->data > (*rhs);}
                bool operator >= (const_iterator const& rhs) const {return node->data >= (*rhs);}
                const_iterator operator ++ () {
                    node = node->next == nullptr ? &Pool::EndNode : node->next;
                    return (*this);
                }
                const_iterator operator ++ (int){
                    const_iterator original(*this);
                    node = node->next == nullptr ? &Pool::EndNode : node->next;
                    return original;
                }

                const T* operator * () const {
                    return node->data;
                }

            private:
                const_iterator(Pool::Node* node):node(node){}
                Pool::Node* node;
        };

        /** \note Calling begin() triggers a potentially full traversal of the pool after a (de)allocation. */
        iterator begin() {
            cleanup();
            if ( firstAlloc == nullptr )
                return iterator(&Pool<T>::EndNode);
            return iterator(firstAlloc);
        }

        iterator end() const {
            return iterator(&Pool<T>::EndNode);
        }


        /** \param size Integer representing the number of instances that should be able to fit in the pool. */
        Pool(unsigned int size = 1024):size(size),nrOfAllocs(0),dirty(false),firstAlloc(nullptr) {

            // Allocate pool and metadata
            pool = static_cast<T*>(malloc(size * sizeof(T)));
            metadata = new Node[size];
            firstFree = &metadata[0];
            assert(firstFree != nullptr);

            // Initialise nodes
            for ( int i = 0; i < size; ++i ) {
                metadata[i].data = pool + i;
                metadata[i].next = &metadata[i+1];
                assert(metadata[i].next != nullptr);
                metadata[i].alloc = false;
            }
            metadata[size-1].next = nullptr;

            // Setup end node
            Pool::EndNode.data = pool + size;
        }

        ~Pool() {
            free(pool);
            delete[] metadata;
        }

        /// Called by new. Pops a free block, marks it and returns the associated pool address
        T* alloc() {

            // Check if we have free blocks left
            if ( firstFree == nullptr ) {
                std::cout << "Pool out of memory!" << std::endl;
                abort();
            }

            // Pop front free node
            Node* n = firstFree;
            firstFree = n->next;

            // Set metadata
            n->alloc = true;
            ++nrOfAllocs;
            dirty = true;

            // Fix head
            if ( firstAlloc == nullptr || firstAlloc->data > n->data )
                firstAlloc = n;

            return n->data;

        }

        /// Called by delete. Marks the block as unused, and pushes it on the free list.
        void free(void* block) {

            // Get node
            T* data = static_cast<T*>(block);
            int i = data - pool;
            assert(i >= 0 && i < size);
            Node* n = &metadata[i];
            assert(n->data == block);

            // Fix head
            if ( firstAlloc == n )
                firstAlloc = n->next;

            // Return node to free list
            n->next = firstFree;
            firstFree = n;

            // Set metadata
            n->alloc = false;
            --nrOfAllocs;
            dirty = true;
        }

        /// Called by begin if the pool is marked as dirty. Recreates the linked list for allocated blocks for efficient traversal.
        void cleanup() {

            if ( dirty && nrOfAllocs > 0 ) {

                int allocsFound = 0;
                int i = firstAlloc->data - pool;
                Node* n = firstAlloc;

                // Only search within the range we know has allocated blocks
                while ( allocsFound < nrOfAllocs && (i+1) < size ) {

                    if ( metadata[i+1].alloc ) {
                        ++allocsFound;
                        n->next = &metadata[i+1];
                        assert(n->next != nullptr);
                        n = &metadata[i+1];
                    }
                    ++i;
                }

                n->next = nullptr;
                dirty = false;

            }
        }
};

template <class T>
typename Pool<T>::Node Pool<T>::EndNode = {nullptr, nullptr, false};
\$\endgroup\$
1
\$\begingroup\$

Any suggestions? Obvious issues? Glaring mistakes?

A few observations:

  • you are including iostream ... consider removing it, since you have no i/o code (none that I could see)
  • consider defining your allocation data as:

Code:

struct Node { // name should be changed
    T* data;
    bool alloc;
};

... and defining your allocation list using std::forward_list; This way you will make your code smaller and more idiomatic, increase code reuse and use an already tested implementation of a list.

  • Your iterator and const_iterator classes are identical, except for one defining a T* accessor and the other one a const T* accessor. Consider either writing a templated, common implementation and typedef-ing it to iterator and const_iterator depending on the type, or (as some std:: implementations of iterators do) implementing first the const_iterator, then inheriting the iterator from it and adding a non-const accessor to the implementation.

  • Never mix malloc/free and new/delete in the same code; for C++, always use new and delete, and prefer to not do so directly.

That means, replace this code:

Node* metadata;

// ...

Pool(unsigned int size = 1024) // ...
{
        // Allocate pool and metadata
        pool = static_cast<T*>(malloc(size * sizeof(T)));
        metadata = new Node[size];
        firstFree = &metadata[0];

with this:

std::vector<T>    pool;
std::vector<Node> metadata;

// ...

Pool(unsigned int size = 1024) // ...
{
        // Allocate pool and metadata
        pool.reserve(size);
        metadata.reserve(size);
        firstFree = &metadata[0];

This will make your destructor trivial, and after this, your destructor should be removed (the code that is easiest to maintain is the one you don't have to write at all).

  • Use assertions for checking your invariants, not failed operations; For operations that can fail, use exceptions.

Example:

        pool = static_cast<T*>(malloc(size * sizeof(T)));
        metadata = new Node[size];
        firstFree = &metadata[0];
        assert(firstFree != nullptr); // <- if(!firstFree) throw <your-exception-here>

Otherwise you will have a class that (instead of reporting an error to client code) stops your application with assertion failed. Consider that, as it is right now, you will be unable to write a unit test for Pool(100000000); (such a unit test would not pass with a "failed allocations" message, but stop your unit testing suite execution).

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for your suggestions. Good points about the asserts and template for the iterators, I am going to look into that. :) The iostream header is currently used for displaying the error message upon overflow of the memory pool. I don't think the forward_list would work here, since I basically store two linked lists (one for allocated blocks and one for free blocks) in one list. Also, if I were to use new for the memory block allocation instead of malloc, I would call the constructors, wouldn't I? I explicitly need to call the constructor upon the call to alloc(). \$\endgroup\$ – user3601077 May 7 '14 at 10:38

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.