# 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.

- User can specify the allocation size of pools and the number of pools.
- Pools can grow if their core memory becomes exhausted.
- Pools can optionally shrink if their core memory is freed.
- User can specify the max amount of memory that can be wasted in an allocation while using a larger pool to supply an allocation instead of growing the existing pool.
- Provides the following allocation functions:
  - Malloc(size_t size)
  - MallocAligned(size_t size, size_t align)
  - Realloc(void* p, size_t size, size_t sizeOld = 0)
  - Free(void* p, size_t size = 0)
- Provides the following utility/debug functionality in all builds:
  - ValidateAddress(void* p)
  - ValidateHeap()
  - GetUsableSize(void* p)
- Provides the following optional debug functionality in debug builds:
  - Double free detection.
  - Stale pointer use detection through free memory fills.
  - Extra heap validation.
  - Leak detection.
- Has heap reporting functionality similar to GeneralAllocator and NonLocalAllocator:
  - ReportBegin(), ReportNext(), ReportEnd()
  - TraceAllocatedMemory()

### Future Features

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

- Guard fills for allocated memory in debug builds. This allows for the detection of overruns of allocated memory.
- High water mark tracking for pools. This allows for pool size tuning.
- Allocation hooks. This allows the user to listen in on the allocation activity.

### 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);