Singleton typed memory manager

Question

For my resources management, I wanted the objects allocated on the heap to be in a contiguous block of memory. Obviously, each data type then has to have their own chunk of memory. I could have used a vector for this, of course, but the resources need to be aligned properly with a given alignment which a vector can't do (for alignments above 16 bytes). In addition, I wanted the allocation to be faster than standard new.

#pragma once

#include <vector>
#include <assert.h>
#include <memory>

typedef unsigned __int32 U32;
typedef unsigned __int8  U8;

#define TYPED_ALLOCATION

///////////////////////////////////////////////////////////////////////////////////////////////////
#ifdef TYPED_ALLOCATION
// TODO: the allocation should always return a unique_ptr!
#define MakeUniqueInstance(Type,...) AllocTypedUnique<Type>(__VA_ARGS__)
#define MakeSharedInstance(Type,...) AllocTypedShared<Type>(__VA_ARGS__)

// This defines a deleter functor in a similar way to the default deleter
template<class _Ty>
struct typed_delete
{
    typed_delete() = default;

    template<class _Ty2,
    class = typename enable_if<is_convertible<_Ty2 *, _Ty *>::value,
        void>::type>
        typed_delete( const typed_delete<_Ty2>& ) = default;

    void operator()( _Ty *_Ptr ) const
    {
        FreeTyped( _Ptr );
    }
};
///////////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
using TypedDeleter = typed_delete < T >;

// Unfortunately, I haven't found a way to make unique pointers of a base type
// while allocating for a derived type (e.g. unique_ptr<Base> pB = TypedAlloc<Derived>(args),
// therefor I had to use shared pointers.
template<class T, class...Args>
std::unique_ptr<T, TypedDeleter<T>> AllocTypedUnique( Args&&... args )
{
    return std::unique_ptr<T, TypedDeleter<T>>( AllocTyped<T>( args... ) );
}

template<class T, class...Args>
std::shared_ptr<T> AllocTypedShared( Args&&... args )
{
    return std::shared_ptr<T>( AllocTyped<T>( args... ), TypedDeleter<T>() );
}

template<class T, class...Args>
T* AllocTyped( Args&&... args )
{
    static_assert( sizeof( T ) > 0,
        "Cannot allocate memory for zero-size type" );
    // Allocate a chunk from the typed memory pool
    T* p = TypedAllocator<T>::Get().Allocate();
    // Construct the object in the allocated space
    new ( (void *) p ) T( std::forward<Args>( args )... );
    return p;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
void FreeTyped( T* p )
{
    TypedAllocator<T>::Get().Free( p );
}
///////////////////////////////////////////////////////////////////////////////////////////////////
// This deleter is used to free the memory allocated by _aligned_alloc function
struct page_delete
{
    page_delete() = default;

    page_delete( const page_delete& ) = default;

    void operator()( char*_Ptr ) const
    {
        _aligned_free( static_cast<void*>( _Ptr ) );
    }
};
///////////////////////////////////////////////////////////////////////////////////////////////////
struct Page
{
    std::unique_ptr<char, page_delete> page;
    std::vector<U32> freeChunks;
    U32 end = 0;

    Page() = default;

    Page( Page&& o )
        : page { std::move( o.page ) }
        , freeChunks { std::move( o.freeChunks ) }
        , end { o.end }
    {}

    Page& operator=( Page&& o )
    {
        page = std::move( o.page );
        freeChunks = std::move( o.freeChunks );
        end = o.end;
        return *this;
    }
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// For each type T, there will be one singleton memory manager which will place the instances
// of the object in a contiquous page of memory.
template <class T>
class TypedAllocator
{
public:
    static TypedAllocator<T>& Get()
    {
        static TypedAllocator m_this;

        return m_this;
    }
    ///////////////////////////////////////////////////////////////////////////////////////////////
    T* Allocate()
    {
        const U32 numPages = (U32) pages.size();

        U32 row = 0;
        U32 col = 0;
        // If there are empty slots on the last page, fill it up first
        if ( numPages > 0 && pages.back().end < width )
        {
            row = numPages - 1;
            col = pages.back().end;
            ++pages[row].end;
        }
        else
        {
            // If the last page is full, then go through all pages and see if there's
            // a free chunck to hold the object.
            bool needNewPage = true;
            for ( ; row < numPages; ++row )
            {
                std::vector<U32>& freeChunks = pages[row].freeChunks;
                if ( !freeChunks.empty() )
                {
                    col = freeChunks.back();
                    freeChunks.pop_back();
                    needNewPage = false;
                    break;
                }
            }
            // All pages are full, so new page is needed.
            if ( needNewPage )
            {
                std::unique_ptr<char, page_delete>
                    uPtr( static_cast<char*>( _aligned_malloc( byteWidth, __alignof( T ) ) ) );

                Page page;
                page.end = 1;
                page.page = std::move( uPtr );
                pages.push_back( std::move( page ) );
            }
        }

        return reinterpret_cast<T*>( pages[row].page.get() + col * stride );
    }
    ///////////////////////////////////////////////////////////////////////////////////////////////
    void Free( T*& ptr )
    {
        const U32 numPages = (U32) pages.size();
        for ( U32 i = 0; i < numPages; ++i )
        {
            const auto tp_begin = pages[i].page.get();
            const auto tp_end = tp_begin + byteWidth;
            const char *const cPtr = reinterpret_cast<const char* const>( ptr );
            if ( cPtr >= tp_begin && cPtr <= tp_end )
            {
                assert( ( cPtr - tp_begin ) % stride == 0 );
                ptr->~T();
                const U32 col = (U32) ( cPtr - tp_begin ) / stride;

                assert( std::find
                    ( pages[i].freeChunks.begin()
                    , pages[i].freeChunks.end()
                    , col ) == pages[i].freeChunks.end() &&
                    "Error: memory at this pointer was already freed!" );

                pages[i].freeChunks.push_back( col );
                // when a page is completely empty, then delete it.
                if ( pages[i].freeChunks.size() == width )
                {
                    pages.erase( pages.begin() + i );
                }
                break;
            }
        }
    }
    ///////////////////////////////////////////////////////////////////////////////////////////////
    TypedAllocator( const TypedAllocator& ) = delete;
    TypedAllocator& operator=( const TypedAllocator& ) = delete;
private:
    TypedAllocator() = default;
    ~TypedAllocator() = default;

    // the aligned size of the object
    const U32 stride{ __alignof(T)* (sizeof(T) / __alignof(T)
        +(U8)((sizeof(T) % __alignof(T)) != 0)) };
    // the width of each page. currently holding just 4 elements for easy debugging.
    const U32 width {4};
    // size of each page in bytes.
    const U32 byteWidth {width * stride};
    std::vector<Page> pages;
};
#else
#define MakeUniqueInstance(Type,...) std::make_unique<Type>(__VA_ARGS__)
#define MakeSharedInstance(Type,...) std::make_shared<Type>(__VA_ARGS__)
template<class T>
using TypedDeleter = std::default_delete < T >;

#endif // TYPED_ALLOCATION

First, by all means, use it if you feel it's useful to you. Second, I'd appreciate any suggestion to improve/optimize the design (or why it would ever fail/bugs). I know this implementation is not thread safe, but other than that all suggestions are welcome. The current problem that I have with this is that I cannot use it to write the following:

void main()
{
    unique_ptr<Base, TypedDeleter<Base>> pB = MakeUniqueInstance(Derived);
}

That's because I can't use TypedDeleter the same way default_delete is used, so I need help with this.

The most important reason for implementing this allocator is the fact that the allocations for each type are mostly on the same contiguous block. So accessing them repeatedly is more cache friendly. I haven't tested if my allocator is faster than new. That'd be nice, but it's not as important as data locality.

Answer 1

Starting on page:

Page( Page&& o )
    : page { std::move( o.page ) }
    , freeChunks { o.freeChunks }   // You want to copy the free chunks.
                                    // Why not move them?
    , end { o.end }
{}

Page& operator=( Page&& o )
{
    page = std::move( o.page );
    freeChunks.swap( o.freeChunks );  // OK works. fine.
                                      // But it looks more logical if you move it.
    end = o.end;
    return *this;

Answer 2

I've noticed that your code is Visual Studio specific at the moment, so I'll give you a few tips you can use to make it more standard and portable.

1. #pragma once is not standard, but it is supported by several compilers, so this is not an issue. Just for the record, an option to it would be an include guard.

2. __int32 and __int8 are Microsoft specific. C++11 provides the header <cstdint>, which defines several sized integral types, including uint32_t and uint8_t. You should use those instead.

3. __alignof is a pre-C++11 Visual Studio extension. The new C++ standard now provides the alignof operator, which should be used instead.

4. _aligned_malloc() is also a Windows specific function, its Unix equivalent being memalign() or posix_memalign(). Your best course of action here would be to avoid calling _aligned_malloc() directly by creating a thin wrapper function that you can redirect to memalign/_aligned_malloc easily with some #ifdefs, in case you ever decide to port this code. See this SO question for more.