Introduction
In this post, I will go through a feature in my game engine,a simple block allocatorL: custom HeapManager.
Contants of tables:
- Why we need a custom heap manager in our engine.
- Core structures and implementations like BlockDescriptor, HeapManager and related functionalities like guard banding and defragmentation.
- Advanced features like Address Alignment, Fixed-size Allocator, Bit Array and so on.
1. Why we need a custom Heap Manager in game engine?
First of all, performance could be one of the biggest issuses of a game engine. The original allocation function in C++ (malloc and new), are normally slow since they’re general purpose functions and there are rare ways to check memory leak during developments.
In that case it is easier to check(DEBUG) if there are any memory pollution or leaking from other teams’ plugin.
If the engine have a very specific purpose, for instance if we need to allocate frequently, then having a custom heap manager using certain structures might be helpful like using the fixed-size allocator for frequent small-pieces allocations.
Also it ensures the robustness of your program. Preallocating a big chunk of memory will prevent program from crashing when it is out of system memory.
2. My Heap Manager structures
A block descriptor will be placed as the overhead of a memory to help manage it. It contains the size of this memory piece, if this is a outstanding memory, the pointer to the address.
Fist we allocate big memory from heap, in this case, the size of this meomory pool is 1024*1024 bytes
const size_t sizeHeap = 1024 * 1024;
const unsigned int numDescriptors = 2048;
// Allocate memory for my test heap.
void * pHeapMemory = HeapAlloc(GetProcessHeap(), 0, sizeHeap);
assert(pHeapMemory);
// Create a heap manager for my test heap.
HeapManager * pHeapManager = CreateHeapManager(pHeapMemory, sizeHeap, numDescriptors);
assert(pHeapManager);
if (pHeapManager == nullptr)
return false;2.1 Initialize the heap manager
Place a block descriptor at the beginning of the memory. Imagine it as a big chuck of a free memory.
2.2 Allocate the memory
When first allocation comes, cut the remaining piece of the memory, return the first avaliable memory.
2.3 Fill the memory
Before free the memory, let us make a rule about how the memory pool should look like in different situations so that it is easier to debug when we check the memory in debug mode. There are four cases:
- Guard banding fills
- Alignment fills
- Free object fills
- New object fills
/* fill no-man's land with this */
static unsigned char _bNoMansLandFill = 0xFD;
/* fill AlignLand for aligned routines */
static unsigned char _bAlignLandFill = 0xED;
/* fill free objects with this */
static unsigned char _bDeadLandFill = 0xDD;
/* fill new objects with this */
static unsigned char _bCleanLandFill = 0xCD; 2.4 Free the memory
Free a memory is easy. Use the memory address user passed in to check if this address is correct. If it is correct, get the address of the block descriptor and modify the information (address return to the user, if it is allocated) of it.
2.5 Defragmentation (Garbage collection)
After a lot of allocate and free, this poll may contains a lot of block descriptor and a lot of small chuck of memories. They can be combined to make a bigger memory chuck. In this case, the pool can fulfill the request of large allocation after tons of small or medium allocations.
This is the proxy interface of the heap mamager.
HeapManager * CreateHeapManager(void * i_pMemory, size_t i_sizeMemory,
unsigned int i_numDescriptors);
void Destroy(HeapManager * i_pManager);
void * alloc(HeapManager * i_pManager, size_t i_size);
void * alloc(HeapManager * i_pManager, size_t i_size, unsigned int
i_alignment);
bool free(HeapManager * i_pManager, void * i_ptr);
void Collect(HeapManager * i_pManager);
bool Contains(const HeapManager * i_pManager, void * i_ptr);
bool IsAllocated(const HeapManager * i_pManager, void * i_ptr);
size_t GetLargestFreeBlock(const HeapManager * i_pManager);
size_t GetTotalFreeMemory(const HeapManager * i_pManager);
void ShowFreeBlocks(const HeapManager * i_pManager);
void ShowOutstandingAllocations(const HeapManager * i_pManager);
3. Advaced topics of the heap manager
In the previous paragraphs, I have introduced a very basic form of a heap manager that I implemented when I was studying. There are more specific heap managers to handle specific situations, which can speed up memory allocation and defragmentations. But in general
Boson Area 