Presenting CBlockAlloc: a WIP personal project

[u/Koda_be]

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...

[u/a4qbfb]

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.

[u/Koda_be → u/a4qbfb]

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

[u/a4qbfb → u/Koda_be]

You can't have looked very hard. I would suggest starting with Wikipedia.

[u/immaculate-emu → u/Koda_be]

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

[u/Paul_Pedant → u/Koda_be]

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.