2
\$\begingroup\$

Currently, in my games, I'm using new and delete to create entities and components. It works fine, but there are slowdowns when creating/deleting many (5000+) entities or components at once.

After asking for advice on StackOverflow, I decided to create my own memory pre-allocator.

  • It allocates a specific amount of memory on the heap when constructed.
  • It creates objects on "pieces" of the allocated memory by using Preallocator::create<T>()
  • It destroys (calls destructor and reclaims memory "pieces") objects with Preallocator::destroy<T>
  • It holds no specific type - it can hold different type of objects at once
  • It is faster than using new and delete.

But is it ready to use in production code?

Could it be even faster?


class PreAllocator
{
    private:
        constexpr static unsigned int bufferSize{1000};
        using MemoryUnit = char;
        using MemoryPtr = MemoryUnit*;

        struct Piece
        {
            // Piece is a range of memory [begin, end)
            MemoryPtr begin, end;

            inline Piece(MemoryPtr mStart, MemoryPtr mEnd) : begin{mStart}, end{mEnd} { }
            inline size_t getSize() const { return sizeof(MemoryUnit) * (end - begin); }
        };

        MemoryUnit* buffer{new MemoryUnit[bufferSize]};
        vector<Piece> available;

        inline void unifyFrom(unsigned int mIndex)
        {
            auto lastEnd(available[mIndex].end);
            auto itr(std::begin(available) + mIndex + 1);

            for(; itr != std::end(available); ++itr)
                if(itr->begin == lastEnd) lastEnd = itr->end;
                else break;

            available.erase(std::begin(available) + mIndex, itr);
            available.emplace_back(available[mIndex].begin, lastEnd);
        }

        inline void unifyContiguous()
        {
            std::sort(std::begin(available), std::end(available), [](const Piece& mA, const Piece& mB){ return mA.begin < mB.begin; });
            for(unsigned int i{0}; i < available.size(); ++i) unifyFrom(i);
        }

        inline std::vector<Piece>::iterator findSuitableMemory(size_t mRequiredSize)
        {
            // Tries to find a memory piece big enough to hold mRequiredSize
            // If it is not found, contiguous memory pieces are unified
            // If it is not found again, throws an exception

            for(int i{0}; i < 2; ++i)
            {
                for(auto itr(std::begin(available)); itr != std::end(available); ++itr) if(itr->getSize() >= mRequiredSize) return itr;
                unifyContiguous();
            }
            throw;
        }

    public:
        PreAllocator()
        {
            // Add the whole buffer to the available memory vector
            available.emplace_back(&buffer[0], &buffer[bufferSize]);
        }
        ~PreAllocator() { delete[] buffer; }

        template<typename T> inline T* create()
        {
            // Creates and returns a T* allocated with "placement new" on an available piece of the buffer
            // T must be the "real object type" - this method will fail with pointers to bases that store derived instances!

            auto requiredSize(sizeof(T));
            auto suitable(findSuitableMemory(requiredSize));

            MemoryPtr toUse{suitable->begin};
            Piece leftover{toUse + requiredSize, suitable->end};

            available.erase(suitable);
            if(leftover.getSize() > 0) available.push_back(leftover);

            return new (toUse) T;
        }
        template<typename T> inline void destroy(T* mObject)
        {
            // Destroys a previously allocated object, calling its destructor and reclaiming its memory piece
            // T must be the "real object type" - this method will fail with pointers to bases that store derived instances!

            mObject->~T();
            auto objStart(reinterpret_cast<MemoryPtr>(mObject));
            available.emplace_back(objStart, objStart + sizeof(T));
        }
};

Test/benchmark:

struct ObjBase { };
struct TestObj : ObjBase { char data[100]; };
struct TestObjBig : ObjBase { char data[500]; };

int main()
{
    PreAllocator p;

    startBenchmark();
    {
        for(int k = 0; k < 10000; ++k)
        {
            vector<TestObj*> objs;
            vector<TestObjBig*> objsbig;

            for(int n = 0; n < 300; ++n)
            {
                for(int i = 0; i < 5; ++i) objs.push_back(p.create<TestObj>());
                for(int i = 0; i < 5; ++i) p.destroy(objs[i]);
                objs.clear();
            }

            for(int n = 0; n < 100; ++n)
            {
                for(int i = 0; i < 2; ++i) objsbig.push_back(p.create<TestObjBig>());
                for(int i = 0; i < 2; ++i) p.destroy(objsbig[i]);
                objsbig.clear();
            }
        }
    }
    string b1 = endBenchmark();

    startBenchmark();
    {
        for(int k = 0; k < 10000; ++k)
        {
            vector<TestObj*> objs;
            vector<TestObjBig*> objsbig;

            for(int n = 0; n < 300; ++n)
            {
                for(int i = 0; i < 5; ++i) objs.push_back(new TestObj());
                for(int i = 0; i < 5; ++i) delete objs[i];
                objs.clear();
            }

            for(int n = 0; n < 100; ++n)
            {
                for(int i = 0; i < 2; ++i) objsbig.push_back(new TestObjBig());
                for(int i = 0; i < 2; ++i) delete objsbig[i];
                objsbig.clear();
            }
        }
    }
    string b2 = endBenchmark();

    cout << b1 << endl; // prints "193ms"
    cout << b2 << endl; // prints "957ms"

    return 0;
\$\endgroup\$
  • 1
    \$\begingroup\$ Why don't you use Boost.Pool? \$\endgroup\$ – Lstor Aug 3 '13 at 22:28
  • \$\begingroup\$ Not convinced your benchmarks are very useful. They do a very simple situation that does not seem to exercise your code very much. \$\endgroup\$ – Martin York Aug 4 '13 at 4:22
  • \$\begingroup\$ @Lstor: I do not want to introduce a Boost dependency in my projects. \$\endgroup\$ – Vittorio Romeo Aug 4 '13 at 9:29
  • \$\begingroup\$ @LokiAstari: How can I improve my benchmark? What cases do I have to take into account? \$\endgroup\$ – Vittorio Romeo Aug 4 '13 at 9:30
  • \$\begingroup\$ @VittorioRomeo: Run your real code. But put print statements in your constructors and destructors to get an idea of the number of objects being created and destroyed (and an approximate order). Then write a benchmark that imitates a real run of your application. \$\endgroup\$ – Martin York Aug 4 '13 at 15:29
5
\$\begingroup\$

Big Issue:

Alignment. You do not consider alignment. You may not need too. But you should definitely comment the code to explain how it can be used.

p.create<char>();
p.create<int>();   // This will probably crash

Unlike new you don't support objects that don't have a default constructor. Using the C++11 varargs this should be easily doable:

template<typename T, typename... Args>
T* PreAllocator::create(Args... args)
{
    .. STUFF ..

    // Not 100% sure the syntax is perfect
    // And I have not tried this. SO experiments and verification are in order
    return new (toUse) T(args...);
}

I am not convinced your benchmarks are representative of what you are code would do. That looks like an awfully simple test.

Also the order you do things can be important in benchmarking so putting both tests into the same executable is not a good idea. Build separate executables for each benchmark then run the tests independently. This way you know that both systems start off with a clean environment to test in.

Rather than use the allocator object directly why not overload the new/delete operators for the classes you want. Then you can turn your allocator on/off as appropriate without searching the code and modifying create => new etc.

Code Review

    // Does not seem like a very big buffer.
    // surprised the general purpose allocator is not working for you.
    constexpr static unsigned int bufferSize{1000};

Avoid the use of inline unless it is needed. And it is not needed here.

    inline void unifyFrom(unsigned int mIndex)

Avoid use of auto for this type of case. Here the types of the variables provided contextual meaning to the reader. Here I found myself thinking lastEnd was an iterator and it took me several reads to actually work out what it was.

        auto lastEnd(available[mIndex].end);

I am fine with auto for iterators. As there creation is obvious and I don't need to know the exact type. Just the fact that it is an iterator.

        auto itr(std::begin(available) + mIndex + 1);

Note: Not all iterators support + as an operator. Prefer to use std::advance()

Why erase all then put at the back? You break up space locality in the data if there are lots of pieces being allocated and deallocated in a random orders.

        available.erase(std::begin(available) + mIndex, itr);
        available.emplace_back(available[mIndex].begin, lastEnd);

I would erase all the items after the current one. Then update the current one with its new size. That way you keep the correct ordering. Thus reducing sorting costs.

Also the way you have done it will not work correctly with unifyContiguous(). As the element after a squished block now becomes the ith element. The loop will advance to the next element so each Piece after a squished set of blocks is not considered for squishing in the next block set.

This is not legal:

        throw;

The only time that throw is valid is during an exception handler (and functions called from the exception handler) where there is currently propagating exception (when the exception handler finishes the exception is dead unless re-thrown.

OK Good.

    PreAllocator()
    ~PreAllocator() { delete[] buffer; }

But you forgot the rule of 3(or 5). So you need to define (or undefine) the copy constructor and assignment operator.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the advice. I'm new to Code Review - should I update the original post with the improved code to get further feedback? \$\endgroup\$ – Vittorio Romeo Aug 4 '13 at 9:55
  • \$\begingroup\$ It depends on the level of changes. If they are substantial, I think it's better to start a new post. \$\endgroup\$ – Lstor Aug 4 '13 at 14:46
  • \$\begingroup\$ PreAllocator::create should return T*, not void. I was surprised to see that throw; does in fact compile. \$\endgroup\$ – Lstor Aug 4 '13 at 15:01
  • \$\begingroup\$ @Lstor: thorw; is perfectly valid statement. BUT it can only be used in the context of an exception handler were it means re-throw the currently propagating exception. The trouble doing the static analysis to see if the statement is being used in the correct context is beyond the scope of the compiler (this is not a compiler solvable problem). Remember that an exception handler can call any function. \$\endgroup\$ – Martin York Aug 4 '13 at 15:36
  • 1
    \$\begingroup\$ @VittorioRomeo: When I am using it as a placeholder I do throw 1; It throws an integer. And they are easy to find with a grep at the end to make sure you have not missed any. \$\endgroup\$ – Martin York Aug 4 '13 at 15: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.