https://screwjankgames.github.io/engine%20programming/2020/0...
https://www.bytesbeneath.com/p/the-arena-custom-memory-alloc...
I also don't know how much we want to butcher this blog post, but:
> RAM is fundamentally a giant array of bytes, where each byte has a unique address. However, CPUs don’t fetch data one byte at a time. They read and write memory in fixed-size chunks called words which are typically 4 bytes on 32-bit systems or 8 bytes on 64-bit systems.
CPUs these days fetch entire cache lines. Memory is also split into banks. There are many more details involved, and it is viewing memory as a giant array of bytes that is fundamentally broken. It's a useful abstraction up until some point, but it breaks apart once you analyze performance. This part of the blog didn't seem very accurate.
> This part of the blog didn't seem very accurate.
It was a sufficient amount of understanding to produce this allocator :-). I think that if we have beginner[0] projects posted and upvoted, we must understand that the author's understanding may be lacking some nuance.
[0] author might be a very good programmer, just not familiar with this particular area!
It's not a failure but relatedly as sbrk is linear, you also don't really have a reasonable way to deal with fragmentation. For example, suppose you allocate 1000 page sized objects and then free all but the last one. With an mmap based heap, you can free all 999 other pages back to the OS whereas with sbrk you're stuck with those 999 pages you don't need for the lifetime of that 1000th object (better hope it's not long lived!).
Really, sbrk only exists for legacy reasons.
Actually... you can free those 999 sbrk() pages using munmap() on Linux and Darwin (so most likely the BSDs too). You can also change the mappings within the sbrk()-allocated range, much like any other mmap.
This feature is not well known, nor particularly useful :-)
Thanks to the wonders of virtual memory, you can madvise(MADV_DONTNEED), and return the memory to the OS, without giving up the address space.
A couple of minor C points:
- The code seems to completely lack use of `static` for things that should be local to the implementation, such as `META_SIZE`, `find_free_block()` and others.
- The header includes `<stdbool.h>` but the interface doesn't use it so it could be included in the C file instead (which, in fact, it is!).
- Could do with more `const` for clarity, but that is quite personal.
- Interesting to use explicit comparison to check for integers being zero, but treat pointers being NULL as implicit boolean. I prefer comparing in both cases.
https://pubs.opengroup.org/onlinepubs/7908799/xsh/brk.html
> The behaviour of brk() and sbrk() is unspecified if an application also uses any other memory functions (such as malloc(), mmap(), free()). Other functions may use these other memory functions silently.
Since this is all allocator.h[0] contains aside from other include statements, why have allocator.h at all?
0 - https://github.com/t9nzin/memory/blob/main/include/allocator...
It's interesting to brainstorm new memory allocation interfaces. Some cool ideas:
https://nullprogram.com/blog/2023/12/17/
https://gist.github.com/o11c/6b08643335388bbab0228db763f9921...
I'm in a position to do this in my programming language project. Wrote my own allocator for it. Maybe it's time to reinvent a better wheel.
I don't think that's the case here though.
No need to free in short living processes
Perfectly usable in many applications. Unfortunately, since it depends on assumptions about the application, it's not really suited for a general purpose library.
I haven’t read in full so not sure if it discusses using blocks vs other structures (eg stack-based allocators, stack being the data structure not the program stack.) Ie, it’s a set of implementation choices. It still seems to reflect common ways of allocating in far more detail than many blogs I’ve read on the topic do.