correctnessFor a submitted implementation to be considered valid, it has to run the benchmark in valgrind without producing warnings and free any memory allocated from the heap.
performanceA benchmark is provided that measures the time each implementation takes to allocate and deallocate a large number of random sized blocks.
focus and simplicityImplementations that provide specific features, solve specific problems well and play nice with other allocators are preferred to global, time traveling masters of all trades.
exampleThe following minimal implementation may be used as a starting point.
reference implementationsFour reference implementations are provided, a basic allocator that delegates to malloc/free, a slab allocator that allocates memory in blocks of user defined size from any upstream allocator, a pool allocator that adds the ability to track pointers to any allocator, and a free list allocator that adds pointer recycling on top of pool allocators.
performance comparisonThe short story is that slabs are faster than the basic allocator; adding a free list to recycle pointers is typically about as fast, while reducing memory usage. The reason the pool/slab combination sticks out is most probably that the added overhead pushes the number of slab allocations, the problem disappears when a free list is added in front. I still haven't solved the mystery of why the pool allocator by itself is faster than the basic allocator; some kind of alignment effect from the prefix, maybe; all I know is it executes additional code before delegating to the basic allocator, allocates additional memory, and still manages to run faster.
getting startedlibc4life includes everything you need to get started; start by forking the repository and following the instructions to build and run the tests. Add the files for your allocator to the src/mem directory, add the implementation below the others in tests/malloc_perf.c. Rerun cmake/make and launch 'build/tests' to run the benchmark.
May the source be with you...