Efficient heap-manager for heavy churn, tiny allocs?

Question

I'm looking for ideas for a heap-manager to handle a very specific situation: Lots and lots of very small allocations, ranging from 12 to 64 bytes each. Anything bigger, I will pass on to the regular heap-manager, so only tiny blocks need be catered for. Only 4-byte alignment is needed.

My main concerns are

1. Overhead. The regular libc heap will typically round up an allocation to a multiple of 16 bytes, then add another 16 byte header - this means over 50% overhead on a 20-byte allocation, which sucks.
2. Performance

One helpful aspect is that Lua (which is the user of this heap) will tell you the size of the block it's freeing when it calls free() - this may enable certain optimisations.

I'll post my current approach, which works ok, but I'd like to improve on it if at all possible. Any ideas?

Answer 1

It is possible to build a heap manager that is very efficient for objects that are all the same size. You could create one of these heaps for each size of object that you need, or if you don't mind using a bit of space, create one for 16 byte objects, one for 32, and one for 64. The maximum overhead would be 31 bytes for a 33 byte allocation (which would go on the 64 blocksize heap).

Answer 2

To expand on what Greg Hewgill says, one way to do an ultra-efficient fixed-size heap is:

1. Split a big buffer into nodes. Node size must be at least sizeof(void*).
2. String them together into a singly-linked list (the "free list"), using the first sizeof(void*) bytes of each free node as a link pointer. Allocated nodes will not need a link pointer, so per-node overhead is 0.
3. Allocate by removing the head of the list and returning it (2 loads, 1 store).
4. Free by inserting at the head of the list (1 load, 2 stores).

Obviously step 3 also has to check if the list's empty, and if so do a bunch of work getting a new big buffer (or fail).

Even more efficient, as Greg D and hazzen say, is to allocate by incrementing or decrementing a pointer (1 load, 1 store), and not offer a way to free a single node at all.

Edit: In both cases, free can deal with the complication "anything bigger I pass on the regular heap-manager" by the helpful fact that you get the size back in the call to free. Otherwise you'd be looking at either a flag (overhead probably 4 bytes per node) or else a lookup in some kind of record of the buffer(s) you've used.