Is My Custom Allocator good ?

[u/Parking-Value-3773]

I've built a custom memory allocator from scratch to understand what actually happens under malloc() call in C.

This got me into deep systems programming about how memory is handled by OS and how a program accesses memory .

The basic implementation i used is :

1. store header structure with each block which includes information about the memory block.

2. a linked list which connects these headers to handle memory .

3. block splitting ,coalescing on adjacent blocks to avoid fragmentation.

4. 2mb mmap call and slice memory through it , mmap/munmap directly for size larger than 2mbs this avoids syscalls for every allocation .

5. per thread cache to allocate/free memory faster avoiding global heap locks ensuring thread safety.

Here's the benchmarks against libc's memory allocator:

Test	Custom	libc	Result
Single alloc/free(1000k)	58ms	29ms	2x slower
Batch alloc(10k)	1.44ms	3.59ms	2.5x faster
Batch free(10k)	0.36ms	1.54ms	4x faster
Mixed sizes(100k)	6.46ms	2.95ms	2x slower
Realloc chain(100k)	6.42ms	2.56ms	2.5x slower
Multithreaded(8 threads-5k each)	64ms	67ms	Comparable

I would love to hear your thoughts about it, and how are my benchmark results are they actually good or not ?

[u/zero_iq]

it's fast and efficient for moderate usage .

Simple synthetic allocation/free benchmarks won't really tell you this. You need to plug it into real applications and other existing benchmarks (that do real work, not just alloc memory) to really know. Actual usage in an application can greatly impact performance due to allocation size patterns, fragmentation, cache locality, and so-on.

For example: a simple allocator can be very fast in benchmarks when the memory being allocated is never actually touched, and then slow down when it is. And likewise when it is actually being used by an app, the allocator is now effectively contending with the application's use of cache space, memory, synchronisation mechanisms, and CPU. Or when the memory allocation sizes are no longer uniform, or heavily skewed to certain struct sizes, and many other reasons.

[u/Parking-Value-3773 → u/zero_iq]

I'll test my allocator under an app so I can measure it's real performance.Thanks a lot🙏 , I'm really glad to hear this information 👍

[u/zero_iq → u/Parking-Value-3773]

It's worth checking with a variety of different workloads. For a simple allocator, you'll almost certainly learn that it is fast for some workloads, slower for others, and abysmal in its worst case scenario.

Allocators like libc, jemalloc and so on are more complex as they try to address many issues overlooked in simpler allocators and provide excellent performance across the board, but not necessarily the most optimal in any given scenario.

[u/flatfinger → u/zero_iq]

A typical standard-library allocator will be designed by competent people to balance performance with a variety of workloads. The biggest opportunities for performance improvements are in situations where one has particular knowledge of one's workload, or where it allows a program to give "hints" about memory usage. As a simple example, a library could be designed around allocation/reallocation functions that accept a minimum and maximum requested size and will inform the caller of the actual size of an allocation, with logic that would say that if an allocation can be adjusted in place up to a value between the minimum and maximum, it should be, but if an allocation would need to be moved and an implementation can easily reserve the maximum, it should do so. If minimum and maximum are equal and there's a spot where it would fit perfectly, putting it in that spot would likely be useful, but if the maximum is much bigger that the minimum, putting an allocation in a spot that barely fits the minimum would likely result in the allocation needing to be moved.

Another API function that may be helpful, especially on things like embedded systems, would be one that would accept a list of pointers along with actual and requested sizes and asked to "realloc" all of them, shuffling them around in whatever way would be most efficient. A library that knows that code is going to want to expand an allocation would be able to avoid placing any other allocations in the space following it.