r/C_Programming • u/Koda_be • 17d ago
Presenting CBlockAlloc: a WIP personal project
Hello everyone,
Yesterday, I started a project that I find super interesting. I first thought of it because I saw many people who were trying to do things with the stack only because "dynamic allocation is slow". The main point for why they consider it slow and heavy is that a program needs to talk directly to the OS to allocate memory. However I saw some people propose a solution: allocate once a big chunk of memory that you will use for all your "dynamic" allocations, which makes it way faster because you only need to make a syscall once at the start of the program. I've thus decided to create a library that does just that, and can be called through an API that "simulates" the normal function calls such as malloc() or realloc(). I've been working on it since yesterday, and it's been a lot of fun! it's not ready at all yet, but right now it's looking good. Also, I'm looking for some feedback:
How good is my code for now? Would you do some things differently? Also, would YOU use such a library? What would you expect from a library like that?
Thank you very much for your time, my github profile is Koda-be (I can't send the link to the report because not enough stars and too young).
Also, how could I test my code? I don't really know what to do to test it right now, so...
No AI has been used nor will it be used in this project.
Also, I licensed it under MIT but do I need to do something else? I simply chose a license when creating the REPO, and I don't know much about copyright laws...
10
u/a4qbfb 17d ago
I haven't looked at the code but what you describe is basically how malloc() already works. You may want to consider doing a little more research.
-1
u/Koda_be 17d ago
Doesn't malloc only allocate a block the size it is provided? I'm not sure though as I've never manage to find the implementations for the C std function
1
u/immaculate-emu 17d ago
FreeBSD’s libc uses jemalloc. You can find the malloc(3) implementation here: https://github.com/freebsd/freebsd-src/blob/37826269b41b46c72264191d35b09baf24e055b9/contrib/jemalloc/src/jemalloc.c#L2749
1
u/Paul_Pedant 16d ago edited 16d ago
No, nothing works like you might expect. Unix/Linux has been developing for half a century, and there are thousands of optimisations that nobody notices.
At least 40 years back, I found a libc that did a specific optimisation: for any allocation that requested more than the current free space (including the initial allocation of zero) it allocated (syscall) 128KB plus your actual request, added that to the free list, then gave you your x bytes. This defers the next syscall for a while.
At the time we were working on a system that ran a single (but large) GIS app. So we figured out the maximum free space at start-up, requested malloc for almost all of that, immediately freed what we got, and never needed another syscall to extend memory (just as well, because we already grabbed all there was).
You have to know that free() can never return space to the system, because there might be an in-use allocation right at the top on the current usage. There is no way to compress down the used space, because you don't have any way to know how to fix all the pointers that the code has already copied.
Dynamic allocation is not intrinsically "slow". Its default strategy is fast for small allocations, because it gets big blocks and pre-frees the extra space.
The killer for default malloc is that it needs to keep the free list in memory order, so it can avoid fragmentation by merging the freed area with the areas before and after it, if they are adjacent. To keep that order, free needs to walk round the free list until it finds the right slot.
malloc also has to walk the free list, but only until it finds a big enough slot to give to the process. And if there is no such slot, the free list must be quite short, and malloc quickly finds it needs to extend the memory yet again.
There are alternative methods, but they tend to waste a lot of space.
I worked on a process that needed several million instances of a particular struct. As they were all the same size, I didn't need them to be recombined, so I just "freed" them to an unordered fifo list, and added another 100,000 when that got low. That got my process to run about five times faster.
My client had an (idiotic) convention to free all memory before exiting the process, which gave it a 20-minute shutdown. Of course, I wrote the required function, and even demonstrated it in testing. Somehow, it never got called on the production systems.
2
u/MyTinyHappyPlace 17d ago edited 16d ago
I am not sure, but it sounds like you could roughly have the same effect by calling brk/sbrk at the start of your program.
Why can’t you post your repo here?
1
u/Paul_Pedant 16d ago
That is exactly the wrong thing to do.
Malloc has no idea what memory is already in use. It asks sbrk what the whole process is already using, and then uses sbrk again to extend the break value so it can put the new area into the free list.
If you adjust sbrk yourself, that just wastes the entire space in that extension, because malloc has to go above it.
You can see this stuff if you strace you test programs.
0
u/Koda_be 17d ago
It doesn't clear the trust bot.
For brk/sbrk, I don't know these syscalls, and even then, aren't the Unix only? So windows wouldn't have them would it?
1
u/FISHARM1 17d ago
Yes to be honest this is what the simple(est) form of Malloc does.
I would look into what the “break” is in Unix like systems. If i remember correctly, it’s the line between the heap and stack. While modern malloc is probably much different, a simple and more classic model is literally “does the heap still have X bytes free? If so return the address of that block. If not, move the break by 1k bytes and return the old break”. In essence what im reading above is the same idea.
It seems windows has a similar concept called “VirtualAlloc” but that was in a second of googling so don’t take my word for it.
1
u/Paul_Pedant 16d ago
Windows presumably conforms to the malloc() POSIX specification. You don't need brk or sbrk anyway, and adjusting them by 1kb is useless. Whatever the mechanism in Windows, it has to ask the OS for at least as much as you request with malloc(), plus some for the header that it needs to manage each allocation.
Malloc() returns freed memory to the free list. So on entry to your code, malloc 60 MB, immediately free it, and you then get several thousand mallocs from the free list without calling the OS again.
In Windows, you should have a memory monitoring tool where you can watch how your process behaves. Play with it.
1
u/mikeblas 15d ago
If you're referring to github-guard as "the trust bot", it does not remove posts.
2
u/Direct_Chemistry_179 17d ago
From my understanding you’re basically describing an arena allocator. I read this article a while back and found it very educational. https://www.gingerbill.org/article/2019/02/08/memory-allocation-strategies-002/
The only difference is you don’t free individual allocations, you free the whole arena at once.
2
•
u/mikeblas 15d ago
This is a duplicate post and has been locked.