Positive Programming

Heap layer design

It has been a long time I did not write stupid articles on this F***ing blog. To celebrate this event I will talk about two subjects I like i.e. memory management and meta programming (ie heavy use of templates to do complicated things).

Few weeks ago I read an amazing article concerning memory allocator design (http://www.cs.umass.edu/~emery/pubs/berger-pldi2001.pdf) written by one of my favorite C++ guru i.e. Andrei Alexandrescu. This design consist in using combination of reusable allocation policies to construct efficient and elegant allocators.

Allocator policy must have an interface which looks like:

struct SMyPolicy
{
     byte * Allocate (size_t size); // mandatory
     void Free (byte * pMemPtr); // mandatory
     size_t GetSize (byte * pMemPtr); // not mandatory
};

For example you can have a simple allocator which uses directly malloc and free (SMallocAllocator) and another one which only track the size of allocations (add allocation's size as header).

struct SMallocAllocator
{
     byte * Allocate (size_t size) {return (malloc(size));}
     void Free (byte * pMemPtr)  {free(pMemPtr);}
     size_t GetSize (byte * pMemPtr)  {return (0);}
}

template <typename TAllocPolicy>
struct SSizedAllocator : TAllocPolicy
{
     byte * Allocate (size_t size)
    {
          size_t * pRealPtr = (size_t*)TAllocPolicy::Allocate(size + sizeof(size_t));   
          *pRealPtr = size;
          return ((byte*)(pRealPtr + 1));
     }

     void Free (byte * pMemPtr)
     {
          TAllocPolicy::(pMemPtr - sizeof(size_t));
      }

      size_t GetSize (byte * pMemPtr)
      {
          return (*((size_t *)pMemPtr - 1));
      }
}

typedef SSizedAllocator<SMallocAllocator> TSizedMallocAllocator;

This is a very simple use of heap layer design because you can build many elaborated heaps (composite heaps, etc.). In his article, Andrei demonstrates that it is possible to rewrite complex existing allocators with heap layers design from multiple simple policies. On top of that, he obtains similar and sometimes better performances.

Why this allocator design is so sexy ?
- It is easy to write new policies and use/reuse them in more complex ones,
- The code is clear,
- The code is efficient because there is no virtual methods and several things could be resolved/optimized at compile time thanks to templates.

After reading this article I realized that this is exactly what I need in my "engine" but there are some details which bother me:
- There is no management of alignment which is very important in game programming,
- I need to create and destroy many heaps depending on what happen in the game. I also need to have some links between heaps without having to specify the type of one of them as a template parameter for the other one. Thus, I need to add polymorphism to this design,
- In modern game progamming, engines use threading and it is important to take this specificity into account.

In my implementation I chose the following design: a heap is an object in charge of allocating/deallocating memory, gather statistics on allocations and its behaviour is defined by:
- an Allocator Policy: policies based on heap layer design,
- a Threading Policy,
- other heap policies depending on heap purpose.

The base heap interface looks like:
class IHeap
{
public:

      IHeap (void);
      virtual ~IHeap (void);

      virtual byte * Allocate(size_t size);
      virtual byte * AlignedAllocate(size_t size, uint32 Alignment);
      virtual void Free(byte *pPtr);
      virtual void AlignedFree(byte *pPtr);
      size_t GetAllocSize(byte *pPtr);
      SMemStats GetStats(void);
      // setc.
};

Examples of heaps:
- Simple heap which allocates memory from its allocator
template<typename TAllocatorPolicy, typename TThreadingPolicy>
class CAllocHeap : public IHeap
{};
- Heap which manages a pool of memory
template<typename TAllocatorPolicy, typename TThreadingPolicy, typename TPoolPolicy>
class CAllocHeap : public TPoolPolicy
{};
- Heap which handles allocation in a different way depending on requested size
template<typename TAllocatorPolicy, typename TThreadingPolicy, typename TLittleAllocPolicy, typename TBigAllocPolicy>
class CSizeHeap : public IHeap
{};
- etc.

I also add specific type of allocators:
- an allocator in charge of allocating memory from another heap,
- allocators in charge of allocating different types of memory e.g. SGraphicAllocator,
- etc.

As mentioned before, I added two important funtions to heap layers design:
- alignedalloc,
- alignedfree.