blog.s11n.net

Allocating memory in C without dynamic memory

Hi, all!

The past year or two i’ve been working on various C-based projects. Through that work i’ve taken a strong interest in conserving memory and reducing the number of calls made to make new memory available (e.g. via malloc()). For example, i’ve spent many hours optimizing the whefs embedded filesystem library to run with fewer than 2kb of dynamic memory for the average use case (and as little as 96 bytes(!!!) for a highly-optimized case).

The past few days, that latent fascination with saving calls to malloc() has culminated into a new library:

whalloc (the WanderingHorse.net Allocator) is a small C library which provides an alternative memory management approach. It is initialized with a block of client-supplied memory, typically a stack-allocated char buffer, and then it can slice up that memory and use it for allocations and deallocations. The whole process looks a bit like:

whalloc_bt pool = whalloc_bt_empty;
enum { BufLen = 1024 * 8 };
unsigned char buffer[BufLen];
whalloc_size_t blockSize = sizeof(my_type);
int rc = whalloc_bt_init(&pool, buffer, BufLen, blockSize );
if( whalloc_rc.OK != rc ) { … error … }
my_type * m = whalloc_bt_alloc(&pool, sizeof(my_type));
// ^^^ m now lives somewhere inside of buffer
…
whalloc_bt_free(&pool, m); // makes the memory available for re-use
whalloc_bt_drain(&pool); // “deallocates” all allocated objects at once

The most interesting part is how it stores its memory management information: by taking up a small slice of the memory it is managing. It needs only two bits of storage for each block of memory it manages (there are (memBufferSize/blockSize) blocks in the buffer). The allocator takes up, worst-case (block size of 1 byte), 18-19% of that memory, dropping to 11% for 2-byte blocks, 6% for 4-byte-blocks, and halving for each additional doubling of block size. With a block size of 64 bytes it uses less than 0.5% of the memory for its own purposes. If its storing only a small number of blocks (default setting=128) then it can use its own few-byte-long internal cache and must reserve none of the client’s memory for its own purposes.

For the average use case, where objects are destroyed in reverse of their allocation order, it can perform O(1) if the allocations are equal to or smaller than the defined block size. Its worst-case performance is O(N), with N being a function of the number of blocks being allocated, the total number of blocks managed, and current memory pool fill status. Deallocation is always O(N), with N being the number of blocks being deallocated. For deallocation, finding the underlying management data is always O(1) - a simple hashing operation which uniquely maps any given pointer to its memory block index.

There’s also a variant of the allocator which requires 2 bytes (instead of 2 bits) per managed block. The primary difference is that it stores the requested size of each allocation, whereas the optimized variation simply knows whether a block as a whole has been allocated or not.

The allocators optionally support a client-provided mutex, to lock the allocator, and fallback allocation/deallocation functions, which they can use if their own pool runs out of space (e.g. falling back to malloc() and free()).

For those of you interested in C, in particular in shaving off a few bytes of dynamic memory in your C apps, the code is available (it’s in the Public Domain) over on the whalloc web page:

http://fossil.wanderinghorse.net/repos/whalloc

Happy hacking!