Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
This code is neither complete nor working: where's "..\General\GeneralHeader.h"? Several needed standard library headers aren't shown: <memory> (std::unique_ptr, etc.), <type_traits> (std::enable_if, etc.), <vector>. using declarations are not shown: some standard library symbols have std::, some don't. Types are out of order (AllocTypedUnique depends on and precedes AllocTyped, which in turn depends on and precedes TypedAllocator). Where is U32 declared? –  Niall C. Jul 27 at 17:28
    
@Niall, I added the necessary headers and typedefs. The types ordering is ok. AllocTypedUnique and AllocTyped are template functions, not types. I'm using VS C++ and it compiles and runs without errors and warnings. Please note that you should put the code in a header file (.h) and not in a .cpp –  rashmatash Jul 27 at 17:48
1  
I challenge the assertion resources need to be aligned properly with a given alignment which a vector can't do Is there something specific to your use case where vectors do not hold? –  Loki Astari Jul 27 at 18:56
    
Also I wanted the allocation to be faster than standard new. So technically its possible (allocator pools). But a lot of effort has gone into making new exceedingly fast. I would have to see this as a bottleneck (I never have) before I even tried to optimize it. Because you are trying to implement functionality that already exists and is well debugged (ie known to be correct) there has to be a very good argument for re-implementing it. –  Loki Astari Jul 27 at 19:01
    
@Loki: last time I checked (VS2010) a vector could not be used to hold data if I'd declared the data with __declspc(align(64)) for example. Besides, I'd have to manually declare a vector for every data type that I'd like to allocate on the heap. It seemed impractical. Also using new, doesn't yield the locality that I'm getting with this. I agree the standard functionality is well tested, but I needed some properties that in my opinion is not offered by other solutions. –  rashmatash Jul 27 at 19:40

2 Answers 2

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;
share|improve this answer
    
Good one. I'll edit the main post to apply your suggestion. –  rashmatash Jul 27 at 19:34

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.

share|improve this answer
    
Thank you. I'm indeed aware my MS specific usage. However, for most of my projects the target platform is Windows. So, I'm not very concerned with portability. The only downside is that when I'd share my code like this, not every one could readily use it. –  rashmatash Jul 27 at 19:38
1  
#pragma once may not be standard, but it is widely supported. –  teh internets is made of catz Jul 29 at 11:22
    
You know what, @tehinternetsismadeofcatz, I think you are right, #pragma once is better, and I've based my life on a lie. Heheheh, but seriously, thanks for pointing that out! –  glampert Jul 30 at 0:31
    
I'm not arguing it's better or anything, just pointing out for lazy people like me (whoops) that there's no problem using it! It's something I see quite often judged as "non portable" but it is :p –  teh internets is made of catz Jul 30 at 10:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.