3
\$\begingroup\$

I've recently read an interesting blog post by Philipp Zschoche: it explains how it's possible to avoid unnecessary allocations/deallocations by keeping track of previously allocated memory in a stack.

It's very easy to code a drop-in replacement for smart pointers (such as std::unique_ptr and std::shared_ptr) that will make use of the memory recycler.

When creating a smart pointer, before allocating, it's sufficient to check if there is any unused allocated memory block in the recycler: if there is one, use it, otherwise allocate new memory.

Upon destroying a smart pointer, instead of deallocating, simply call the object's destructor and push the now undefined/unusable memory block on the memory recycler stack, so that other smart pointers of the same type can make use of it.

The memory will be only deallocated at the end of the program (or manually).

namespace ssvu
{
    namespace Internal
    {
        template<typename T, typename TBase> class Recycler
        {
            private:
                std::vector<TBase*> ptrs;
                std::allocator<T> alloc;

                inline T* pop() noexcept
                {
                    SSVU_ASSERT(!ptrs.empty());

                    auto result(ptrs.back());
                    ptrs.pop_back();
                    return reinterpret_cast<T*>(result);
                }

            public:
                inline Recycler() = default;

                // Deallocate all memory on destruction
                inline ~Recycler() noexcept { for(auto p : ptrs) alloc.deallocate(reinterpret_cast<T*>(p), 1); }

                // Recycle: call the allocated object's destructor, but do not deallocate memory
                // Instead, store the pointer to the allocated memory block for reuse
                inline void recycle(TBase* mPtr) noexcept(noexcept(alloc.destroy(mPtr)))
                {
                    SSVU_ASSERT(mPtr != nullptr);
                    alloc.destroy(mPtr);
                    ptrs.emplace_back(mPtr);
                }

                // Create: either reuse allocated unused memory, or allocate a new memory block
                template<typename... TArgs> inline T* create(TArgs&&... mArgs)
                {
                    auto result(ptrs.empty() ? alloc.allocate(1) : pop());
                    alloc.construct(result, std::forward<TArgs>(mArgs)...);
                    return result;
                }
        };

        template<typename T, typename TBase> inline Recycler<T, TBase>& getRecycler() noexcept
        {
            static Recycler<T, TBase> result; return result;
        }
    }

    // Uptr<T, TDeleter> is a typedef for std::unique_ptr<T, TDeleter>

    template<typename T, typename TBase> using UptrRecPoly = Uptr<T, void(*)(TBase*)>;
    template<typename T> using UptrRec = UptrRecPoly<T, T>;
    template<typename TBase> using VecUptrRec = std::vector<UptrRec<TBase>>;

    template<typename T, typename TBase, typename... TArgs> inline UptrRecPoly<T, TBase> makeUptrRecPoly(TArgs&&... mArgs)
    {
        return {Internal::getRecycler<T, TBase>().create(std::forward<TArgs>(mArgs)...), [](TBase* mPtr)
        {
            Internal::getRecycler<T, TBase>().recycle(mPtr);
        }};
    }
    template<typename T, typename... TArgs> inline UptrRec<T> makeUptrRec(TArgs&&... mArgs) { return makeUptrRecPoly<T, T>(std::forward<TArgs>(mArgs)...); }
}

There is a static Recycler instance for every <T, TBase> type pairs.

Example:

struct Base { ~Base(); };
struct Der1 : Base { };
struct Der2 : Base { };

VecUptrRec<Base> vec;

// Recycler<Der1, Base> is empty - allocate 2 memory blocks
vec.emplace_back(std::move(makeUptrRecPoly<Der1, Base>());
vec.emplace_back(std::move(makeUptrRecPoly<Der1, Base>());

// Recycler<Der2, Base> is empty - allocate 2 memory blocks
vec.emplace_back(std::move(makeUptrRecPoly<Der2, Base>());
vec.emplace_back(std::move(makeUptrRecPoly<Der2, Base>());

vec.clear();

// Now both Recycler<Der1, Base> and Recycler<Der2, Base> contain 2 allocated (but unused) memory blocks

// Recycler<Der1, Base> won't allocate any additional memory
vec.emplace_back(std::move(makeUptrRecPoly<Der1, Base>());
vec.emplace_back(std::move(makeUptrRecPoly<Der1, Base>());

// Recycler<Der2, Base> won't allocate any additional memory
vec.emplace_back(std::move(makeUptrRecPoly<Der2, Base>());
vec.emplace_back(std::move(makeUptrRecPoly<Der2, Base>());

Here is my WIP complete implementation-

And here's a simple benchmark, showing promising results.

// Benchmark results
// ---

// Time needed to continuously fill/clear vectors of 10000000 polymorphic objects.

[Benchmark #1 - <Vector<Uptr>>]       4896 ms
[Benchmark #1 - <Vector<UptrRecPoly>>] 3506 ms
[Benchmark #1 - <Vector<Uptr>>]       5631 ms
[Benchmark #1 - <Vector<UptrRecPoly>>] 3436 ms
[Benchmark #1 - <Vector<Uptr>>]       5126 ms
[Benchmark #1 - <Vector<UptrRecPoly>>] 3277 ms




// Time needed to create 3500000 polymorphic objects (half of them of type Der1 : Base, half of them of type Der2 : Base)
// The objects are stored in a std::vector of Uptr<Base> or UptrRec<Base>.
// For 20 times, the objects are iterated upon, and every third object is marked as "dead". After that, dead objects are removed with the erase-remove idiom.
// After dead objects removal, the vector is cleared and filled again with 3500000 objects.

[Benchmark #1 - <MemoryManager>]      12956 ms
[Benchmark #1 - <RecMemoryManager>]   7548 ms
[Benchmark #1 - <MemoryManager>]      12974 ms
[Benchmark #1 - <RecMemoryManager>]   8349 ms
[Benchmark #1 - <MemoryManager>]      13582 ms
[Benchmark #1 - <RecMemoryManager>]   8568 ms

The benchmark continuously creates/destroys smart pointers. Performance is almost 2x as fast compared to normal smart pointers.

  • Is there any potential drawback to this approach? Is there a reason not to use recycled smart pointers?
  • Is there any way the code can be improved/optimized further?
\$\endgroup\$
  • \$\begingroup\$ Allocating via malloc/new is possibly not lock free, and it is definitely thread safe. If you add a lock to make this thread safe, how does it compare? Either way, in an ideal world the OS allocator would do this sufficiently well that you couldn't get notable gains on it from such a technique. \$\endgroup\$ – David Jun 4 '14 at 14:08
  • \$\begingroup\$ @Dave: The current implementation is not thread-safe. I will have to test a thread-safe implementation using locks. However most of my gamedev projects are single-threaded, and it works well there. \$\endgroup\$ – Vittorio Romeo Jun 4 '14 at 15:43
  • \$\begingroup\$ I wouldn't call a factor of 1.6 "almost 2x as fast". Still pretty good though. \$\endgroup\$ – TemplateRex Jun 4 '14 at 17:44
2
\$\begingroup\$

My main complaint is the use of the std::vector in such a low level interface. I think that is totally a waste of resources.

Would be interested to know how this performs in comparison to you vector based version.

I basically swapped the std::vector<TBase> for a TBase* and built a chain. It makes the assumption that TBase is at least the size of a pointer (but I am sure we can add a static assert to achieve this).

namespace ssvu
{
    namespace Internal
    {
        template<typename T, typename TBase> class Recycler
        {
            struct Chain
            {
                Chain*  next;
            };
            private:
                Chain*            chain;
                std::allocator<T> alloc;

                T* pop() noexcept
                {
                    SSVU_ASSERT(chain != nullptr);

                    TBase*  result  = reinterpret_cast<TBase*>(chain);
                    chain           = chain->next;

                    return result;
                }

            public:
                Recycler()
                    : chain(nullptr)
                {}

                // Deallocate all memory on destruction
                ~Recycler() noexcept
                {
                    Chain*  next;
                    for(;chain != nullptr; chain = next)
                    {
                        next    = chain->next;
                        alloc.deallocate(reinterpret_cast<TBase*>(chain), 1);
                    }
                }

                // Recycle: call the allocated object's destructor, but do not deallocate memory
                // Instead, store the pointer to the allocated memory block for reuse
                void recycle(TBase* mPtr) noexcept(noexcept(alloc.destroy(mPtr)))
                {
                    SSVU_ASSERT(mPtr != nullptr);
                    alloc.destroy(mPtr);

                    Chain*   newHead = reinterpret_cast<Chain*>(mptr);
                    newHead->next   = chain;
                    chain           = newHead;
                }

                // Create: either reuse allocated unused memory, or allocate a new memory block
                template<typename... TArgs> T* create(TArgs&&... mArgs)
                {
                    auto result(chain == nullptr ? alloc.allocate(1) : pop());
                    alloc.construct(result, std::forward<TArgs>(mArgs)...);
                    return result;
                }
        };
        template<typename T, typename TBase> Recycler<T, TBase>& getRecycler() noexcept
        {
            static Recycler<T, TBase> result; return result;
        }
    }

    // Uptr<T, TDeleter> is a typedef for std::unique_ptr<T, TDeleter>

    template<typename T, typename TBase>    using UptrRecPoly   = Uptr<T, void(*)(TBase*)>;
    template<typename T>                    using UptrRec       = UptrRecPoly<T, T>;
    template<typename TBase>                using VecUptrRec    = std::vector<UptrRec<TBase>>;

    template<typename T, typename TBase, typename... TArgs> inline UptrRecPoly<T, TBase> makeUptrRecPoly(TArgs&&... mArgs)
    {
        return {Internal::getRecycler<T, TBase>().create(std::forward<TArgs>(mArgs)...), [](TBase* mPtr)
        {
            Internal::getRecycler<T, TBase>().recycle(mPtr);
        }};
    }
    template<typename T, typename... TArgs> inline UptrRec<T> makeUptrRec(TArgs&&... mArgs) { return makeUptrRecPoly<T, T>(std::forward<TArgs>(mArgs)...); }
}

Other things I did not like

(but are totally my own personal preference so not that important).

Lining up stuff so it is easy to read and maintain:

    template<typename T, typename TBase>    using UptrRecPoly   = Uptr<T, void(*)(TBase*)>;
    template<typename T>                    using UptrRec       = UptrRecPoly<T, T>;
    template<typename TBase>                using VecUptrRec    = std::vector<UptrRec<TBase>>;

I believe that makes it a lot easier to read.

Don't put inline where it is not needed.

The keyword inline plays absolutely no role in code inlining. Don't use it for that. It only plays a role in the one definition rule so you need it if a function is defined in a header file that is included into multiple compilation units.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. Using Chain instead of an std::vector didn't affect the performance at all. \$\endgroup\$ – Vittorio Romeo Jun 5 '14 at 15:56
  • \$\begingroup\$ @VittorioRomeo: Then I would use the chain method. As the std::vector takes a lot more space. \$\endgroup\$ – Martin York Jun 6 '14 at 8:20

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.