Memory Pools and Allocators

Creating objects by using new() can be costly in big loops. One way to speed this up is by pre-allocating a chunk of memory and then requesting blocks throughout this chunk.

The first step is to have a struct to hold a chunk of memory.

unsafe public struct MemoryPool
{
    public byte* Buffer;
    public void* Next;
    public int BlockSize;
    public int NumBlocks;
}

Buffer will be large enough to contain all instances of your data, while Next will point to the next available address of free memory.

This is how you would allocate a new pool:

using System;
using System.Runtime.InteropServices;

unsafe public static class MemoryAllocator
{
    public static MemoryPool AllocatePool (int blockSize, int numBlocks)
    {
        MemoryPool pool = new MemoryPool ();
        pool.Next = null;
        pool.NumBlocks = numBlocks;
        pool.BlockSize = blockSize;
        pool.Buffer = (byte*)Marshal.AllocHGlobal (blockSize * numBlocks);

        FreeAllBlocks (&pool);

        return pool;
    }

    public static void FreeAllBlocks (MemoryPool* pool)
    {
        void** current = (void**)pool->Buffer;
        byte* next = pool->Buffer + pool->BlockSize;

        // Point each block except the last one to the next block
        for (int i = 0, count = pool->NumBlocks - 1; i < count; ++i)
        {
            *current = next;
            current = (void**)next;
            next += pool->BlockSize;
        }

        *current = default (void*);

        // The first block is now the head of the free list
        pool->Next = pool->Buffer;
    }
}

Here's how to get and free data from a pool:

public static void* Allocate (MemoryPool* pool)
{
    void* result = pool.Next;
    pool->Next = *((byte**)pool->Next);
    return result;
}

public static void FreeBlock (MemoryPool* pool, void* ptr)
{
    if (ptr == null) return;
    void** head = (void**)ptr;
    *head = pool->Next;
    pool->Next = head;
}

Finally, here's how you can free the pool itself:

public static void FreePool (MemoryPool* pool)
{
    IntPtr ptr = (IntPtr)pool->Buffer;
    if (ptr != IntPtr.Zero) Marshal.FreeHGlobal (ptr);
    pool->Buffer = null;
    pool->Next = null; 
}

To learn more about memory pools, see http://jacksondunstan.com/articles/3770