SmallObjectAllocator

The design of SmallObjectAllocator borrows from a number of small block allocators around EA, such as DynamicSOA, CMemPool, and LionSmallAlloc. Basically, it is a collection of fixed-size pools. It attempts to strike a balance between three considerations: speed, fragmentation, and features. These are briefly discussed below.

Speed

SmallObjectAllocator attempts to optimize the primary allocation pathway to be as fast as possible for its circumstances. The result is that most Malloc operations will be very fast. The code path that the large majority of allocations take is shown below. There are only simple accesses to local memory, very basic math, and only 'positive' branches. It's quite fast for the features and fragmentation benefits that it has and operates in O(1) with respect to heap size. You could likely come up with something faster if you hard-coded it to a particular set of circumstances and removed some features.

void* SmallObjectAllocator::Malloc(size_t size)
{
    if(size <= mMaxMallocSize)
    {
        size_t     poolIndex  = mPoolIndexTable[(size - 1) / 8];
        Pool*      pPool      = mPoolArray + poolIndex;
        CoreBlock* pCoreBlock = pPool->mpCoreBlockCurrent;

        if(pCoreBlock)
        {
            Chunk* const pChunk = pCoreBlock->mpChunkList;

            pCoreBlock->mnFreeChunkCount--;
            pCoreBlock->mpChunkList = pChunk->mpNext;

            if(pCoreBlock->mpChunkList)
                return pChunk;
    . . .
}

The Free pathway is very fast (also O(1)) for the case that the user provides page-aligned/sized pool blocks, and is slower (but probably not terribly so) for the case where you provide arbitrarily aligned/sized pool blocks. Providing the allocation size to Free allows it to operate in more or less O(1) as well. SmallObjectAllocator does not do the technique whereby the allocated size is 'stashed' in the bytes behind the allocated pointer.

Feel free to compare the speed of SmallObjectAllocator to existing small block allocators available to you and comment on your findings.

Fragmentation

SmallObjectAllocator follows the same approach that Tiburon's CMemPool small block allocator does regarding block allocation: blocks are allocated and freed in a way that allows for pool reclamation and better packing. It does this by allocating from the most dense pool source freeing back to the pool source instead of to an anonymous shared pool. This results in a few extra lines of code in Malloc and Free but potentially significant benefits in terms of reduced fragmentation.

Features

SmallObjectAllocator has a subset of the features found in PPMalloc GeneralAllocator and NonLocalAllocator. The subset of features that it does have are implemented very similarly and often identically to the equivalent features in the other allocators.

Future Features

A few features that are currently missing but can be added if there is interest include:

Example Usage

The following demonstrates a minimum usage of SmallObjectAllocator.

void* AllocFunction(SmallObjectAllocator*, size_t nSize,
                    size_t nAlignment, size_t nAlignmentOffset, void*)
{
    return pGeneralAllocator->MallocAligned(nSize, nAlignment, nAlignmentOffset);
}

void FreeFunction(SmallObjectAllocator*, void* p, void*)
{
    pGeneralAllocator->Free(p);
}


SmallObjectAllocator soa(SmallObjectAllocator::Parameters(), AllocFunction, FreeFunction, NULL);

void* p = soa.Malloc(17);
soa.Free(p);