21 ms·
Could have used an article like this when I was implementing my own allocator! This is great. The Wilson1995 paper referenced is also quite useful. The algorit
by matheusmoreira 3y ago
Could have used an article like this when I was implementing my own allocator! This is great. The Wilson1995 paper referenced is also quite useful.
The algorithm I implemented is very similar to the one implemented in this article: start with a huge block of free memory; split it into multiple blocks on allocation; merge with free neighbors on deallocation. Merging blocks is the reason why doubly linked lists are needed. It worked well enough so I didn't make it a priority to organize the free lists by size. I really should implement that already but there are so many other things to do...
It's also important to discuss the fact that implementing a memory allocator in C essentially requires undefined behavior. Arithmetic will be done with arbitrary pointers and the result will be cast to structures. Compiling with strict aliasing turned off is essentially a must. Others have described to me "pointer laundering" techniques where they pass the pointer through some inline assembly just to prevent the optimizer from making incorrect assumptions. Just turning off strict aliasing seems like a better idea. It's a stupid feature anyway. If you're writing C, you're probably aliasing pointers and reinterpreting memory and the last thing you need is the compiler getting clever about it.
Alignment was pretty difficult to wrap my head around at first, especially the universal alignment concept. It also illustrates one of the limitations of C's malloc interface:
> malloc() can simply return maximally-aligned pointers in order to accommodate any data type
This wastes quite a lot of memory when the maximum alignment is not necessary... It should also be possible to segregate free lists by alignment, right? Seems like alignment should be a parameter of the memory allocation function.
This article is also really great:
https://nullprogram.com/blog/2023/12/17/ https://nullprogram.com/blog/2023/12/17/
https://news.ycombinator.com/item?id=38675379 https://news.ycombinator.com/item?id=38675379
Explores the idea of breaking away from C's legacy memory allocation interfaces. If you're like me and enjoy the idea of reinventing things from scratch, it's a great read.
Also linked from its HN discussion:
https://gist.github.com/o11c/6b08643335388bbab0228db763f99219#file-memory-allocation-api-md https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...