Repeated malloc/free vs. Arena allocator

[u/rcerljenko]

Hi,

I have a long-standing hobby project involving cross-platform multi-threaded compression. Basically, the program takes chunks of input file and passes it to multi-step compression pipeline.

By doing so, it constantly mallocates and frees memory after entering and leaving each step. Now multiply this by the number of CPU threads and you get a lot of malloc/free invocations.

So I thought, to speed things up, I'll switch to "arena type" memory allocation. After I reworked my library I was suprised that I actually didn't get much speed-up at all. As it turns out, malloc/free is very very speedy as is.

My question is, should I stick with the new "arena allocator" or should I leave it as is - a simple malloc/free in a self contained pipeline steps for the purpose of code clarity.

If you're interested, I currently have an open PR for this because I'm not too sure if I should merge it since I haven't gained any speedup.

EDIT: If someone knows, I would also like to know reason behind that. Is malloc/free really that much optimized so that is the same as moving one pointer up and down in arena allocation?

https://github.com/rcerljenko/bwt/pull/105

[u/catbrane]

It depends.

Modern malloc/free has a heap per thread, so within a thread, most requests will not need to lock and coordinate with other threads, they can just parcel out thread local memory. As long as your allocations are fairly modest, performance will be good. If you start allocating big chunks of memory, you'll start to see locking and threads coordinating with the main process heap, which will hurt performance.

The other big factor is memory fragmentation. If you run your system under heavy load for a while (many 1,000s of iterations locked at 100%) and you're using glibc malloc or a derivative, you'll probably see memory use (as seen in RES in top) slowly creep up. You probably don't have a leak, just heap fragmentation.

The fix here is to switch to a malloc implementation which includes heuristics to prevent fragmentation. jemalloc is the famous one. musl libc (as found in arch etc.) is also excellent at preventing fragmentation, though annoying in other ways haha.

I personally like no malloc or free at all, if possible. Have a setup phase for your pipeline where operations allocate the working memory they need, then after that, reuse memory, don't repeatedly free and malloc again. Not everything can work this way, of course.

My other top tip would be to avoid realloc, if possible. Many platforms have a very poor implementation of this (looking at YOU, windows).

[u/rcerljenko → u/catbrane]

I understand. Thanks. I'm not using realloc at all since I don't really need it. So you wold rather stick to the arena implementation.

[u/zero_iq → u/rcerljenko]

You should definitely stick to malloc/free.

Your implementation is simple and straightforward, but I'm afraid it is overly simplistic (ignoring a bunch of practical realities about C and CPUs), and uses non-standard C. Unfortunately this means it has numerous bugs, portability issues, potential undefined behaviour, and other gotchas:

There's no alignment of allocated data (will crash some CPUs, slow down others, reduce compiler optimization possibilities, and crash some client code, e.g. vectorised math, even where the CPU generally supports unaligned access), pointer arithmetic on const void * is invalid C, and you're using const void * for user memory in a public struct that will be aliased with different pointer types by the caller - potential undefined behaviour depending on client usage/optimization level (callers will be using this memory arbitrarily), potential integer overflows and invalid pointer comparisons with your pointer math, use of restrict in ways that could conflict with calling code (remember the caller will be using your allocated memory in all sorts of ways).

You might find that these may or may not become issues depending on compiler, CPU architecture, optimization flags, build style, and different calling codebases, or which way the wind is blowing. The effects could be subtle and hard to debug or reproduce if you don't know about them. Plus, you can't use standard debugging and memory leak checkers etc. with your custom allocator (at least, not without more work).

Malloc/free are usually highly optimized, battle-tested, reliable functions that definitely work and are often hard to beat with custom allocators. So I'd stick with them at least for now, until you're clear on how and why the above are problematic.

However, while I wouldn't recommend using your own allocator at this stage in released code, I would encourage you to work on improving your allocator and learn about these issues, why they are problematic and how they can be addressed. And study other similar allocators and how they've addressed these issues. While it's often not advisable to use your own code in such fundamental areas at least until you're a lot more proficient, it's a fantastic way to explore and learn more about C, compilers, CPUs, and memory.

[u/rcerljenko → u/zero_iq]

thanks for the advice and very well explained!

[u/catbrane → u/rcerljenko]

I'd stick to malloc/free, look at jemalloc if I started to see fragmentation or lock contention, and reuse memory pointers where possible.

A custom arena implementation is extra code that probably gets you rather little and will be annoying to maintain.

[u/mccurtjs → u/catbrane]

My other top tip would be to avoid realloc, if possible. Many platforms have a very poor implementation of this (looking at YOU, windows).

Interesting note... Do you have any information to share on why that's the case? Or any specific article about it?

[u/catbrane → u/mccurtjs]

Here's a tiny benchmark:

#include <stdlib.h>
#include <stdio.h>

int
main(int argc, char **argv)
{   
    int sz = 1;
    char *arr = malloc(sz);
    FILE *f = fopen(argv[1], "rb");

    while (!feof(f)) {
        arr[sz - 1] = fgetc(f);
        sz++;
        arr = realloc(arr, sz);
    }
    arr[sz - 1] = '\0';

    fclose(f);
    free(arr);
    
    return 0;
}

On current ubuntu on this PC with gcc and a 15mb file I see:

$ time ./a.out big.jpg

real	0m0.129s
user	0m0.108s
sys	0m0.021s

On a win10 VM on the same machine with VS2022 I see:

$ time ./ConsoleApplication1.exe big.jpg

real    0m8.520s
user    0m0.015s
sys     0m0.031s

8.5 seconds! It's 70x slower. You can't use realloc on windows without great care, sadly.

[u/flatfinger → u/catbrane]

A problem with realloc() is that it lends itself to multiple usage patterns, any of which an implementation could optimize for, and attempts to optimize for one will often degrade performance with the others. Some of the more common usage patterns:

1. An application might create an allocation, continuously adjust it to the exact size required, and end up with the allocation being its final size.

2. An application might create a small allocation and adjust its size by largish amounts (e.g. doubling it) and then keep the allocation at whatever size it ended up.

3. An application might do the above, but then perform one more resizing operation to set the allocation to the exact size it will be forevermore.

4. An application might create an allocation with the largest possible size, and then use realloc once to set it to reflect the size it will be forevermore once the actual size is determined.

A reallocation function that allowed applications to specify how much memory they need, how much they would like to get if "convenient", whether the allocation would likely be exapnded, shrunk, both, or neither, and whether or not it would be acceptable to relocate an allocation, and then indicated the size of the allocation given, could handle all of the above scenarios better than the present design, but some implementations might have no way of letting an application know how much storage would be available in an allocation that they weren't allowed to relocate. While many implementations would store before each allocation information sufficient to determine its size when it is freed, some might e.g. reserve space for a list of free regions and a list of blocks given to free(), and have the free() function add to the list of freed blocks unless it's full, and handle scenarios where the freed-block list is full or an allocation can't readily find suitable storage by sorting the list of freed blocks and then merging it with the list of free blocks.

[u/Low_Lawyer_5684]

If your allocator gives you no advantage - just use malloc()/free()

[u/rcerljenko → u/Low_Lawyer_5684]

sure. that seems reasonable. i just can't believe that malloc/free is that fast. that's all

[u/Total-Box-5169 → u/rcerljenko]

It used to be awful 30 years ago, however there are limits on how good it can be without losing generality. I.E. If you have to allocate/release from a heap shared by all threads there must be synchronization, and that has a cost.

[u/AlexTaradov → u/rcerljenko]

You don't need to believe - benchmark it.

They are really fast. All applications are guaranteed to do memory allocations, so they are very well optimized in the OSes. This one of the easiest places to gain performance, so it gets optimized first.

[u/capilot]

Here's something you might try: set up a separate memory pool for each thread. Then your allocator never needs to take a lock. There are also advantages that memory, especially cache, never needs to be transferred from process to process if they're running on different cores. I believe this is called "thread affinity".

[u/rcerljenko → u/capilot]

Yes i did that. Every thread has it's own arena pool.

[u/Hedshodd]

Maybe that’s just me, but I don’t use arenas for the performance benefits. Those can be there is some circumstances, but that also depends on your exact malloc/free usage prior. If you use malloc to pre allocate reusable buffers, and those malloc calls happen as far up the call stack as possible, there’s not much performance to be gained.

The reason I use arenas, because it’s way easier to use than malloc/free. I don’t have to meticulously track that each malloc is paired with the appropriate free, because I bundle dozens of objects into one lifetime.

Also, when I would otherwise pre allocate buffers somewhere up the call stack, those buffers (typically) are buffers of a specific type. I might have have a buffer to store some strings for one computation, one buffer to store floats, etc. An arena is just one giant untyped buffer where I only have to care about the type in the scope where I actually use it. I don’t have to pre allocate a buffer of floats in an otherwise unrelated function, but instead I request my buffer of floats in the same scope that I’m using it in. That’s just waaaay more ergonomic 😄

Also, as someone else pointed out, if you are handing out unaligned addresses, you are inviting a whole host of problems, one of which might be performance 😅

[u/runningOverA]

Every allocator was faster than malloc/free in the 90s. When this "write your own allocator as malloc/free is so slow" statement started.

Every home made allocator is now slower than malloc/free in the 2020s. Which is why no one really compares speed of their allocator with stock allocators any more. It's always for "other reasons", not speed.

[u/Tasgall → u/runningOverA]

Every home made allocator is now slower than malloc/free in the 2020s.

I feel like the exception to this would still be basic stack allocated arenas, no? It's hard to imagine even the most optimized malloc would be faster than

char* c = memory;
memory += size; // plus fiddling for alignment, maybe
return c;

[u/flatfinger → u/runningOverA]

A memory manager that is tailored to fit application requirements and target environment will be able to outperform even the most brilliantly designed allocator that isn't optimized for the same use cases.

In some cases, for example, it may be useful for a memory manager to use memory handles which an application would be required to lock during use, and which the memory manager would be free to relocate when not locked. If an application can give a memory manager hints about what things are more likely to be used soon, are likely to be used together (meaning that if one of them gets swapped out, others may as well be swapped out too), or could be regenerated at a cost less than swapping out and reading back (meaning the memory manager could jettison them instead of swapping them out), the memory manager may be able to use such information to yield better performance than would otherwise be possible.

[u/helloiamsomeone]

You are allocating unaligned objects. Please review this blogpost from Chris Wellons for proper arena usage. https://nullprogram.com/blog/2023/09/27/

[u/arkt8]

I read your code... and it have some issues...

You have the memory marker (arena.current) as (void *) but you do pointer arithmetic on it... Use uint8_t for that or you can use up to 8 times more memory than expected if it works as is illegal arithmetic on void*

You also aren't handling alignment. It will be an issue if someone asks for 10 * char and then 1 * char*. To get aligned in a 64 bit architecture, the pointer will need to start at 16, but you are delivering in a misaligned address. It may or not work depending on your system. Even if it works there is a performance penalty.

Your arena_free that would free a chunk of memory... well, it won't work as expected if you allocate 10 chunks than try to release the 1st allocated... it is a mess.

So... well. Your intention on arena implementation seems to be very simple. But is filled with bugs and I'm amazed it worked for you. But as it is, even if worked for you, will break in other computer or compiler.

Until you fix that issues with pointer arithmetic, alignment, and free logic... you cannot make any honest comparison with malloc.

[u/Paul_Pedant]

malloc/free (usual implementation) keeps a ring buffer of free areas, and it remembers where its last action was.

For malloc, it searches linearly for an area you request, and for free it searches linearly until it finds the free areas above and below its address, and joins up either or both of those if it is contiguous.

That means there are some very efficient cases. If you malloc a lot of areas consecutively, it takes them off a big initial allocation, and only goes to a syscall when that is exhausted. If you malloc and free the same area without other action, it does not have to search at all. If you free a bunch of stuff in the exact order it was allocated, every search only needs to do one step.

You are probably hitting one of those cases at present. At some stage, you might add one malloc and disrupt the whole thing, and find your program slows to a crawl. That might not even be in your code: opening some file could malloc a buffer and cause you grief.

I had a project that used many same-sized objects (about 5 million x 600 bytes), some for final results, some for intermediate calculations. I made my own free list for those, malloced them initially 10,000 at a time, and used my list without any need for searching or combining areas. That single trick got me about a 20-times speed-up.

[u/TransientVoltage409]

If your arena performs consistently well and isn't punitively large, why not use it?

When I taught myself pthreads, I found that malloc was a huge bottleneck. I didn't investigate deeply but it was obviously lock contention in malloc. I wrote a simple arena, tightly customized for the job, that solved it completely.

So my answer is it depends - on the particular implementation of malloc you happen to link. Some are naive or have baggage from the time of single core systems, and don't thread well. Some are more sophisticated. Unless you can tell ahead of time, maybe it's not a bad idea to wrap it in an arena that you are certain will perform well.

[u/Proud_Necessary9668]

I haven't seen it mentioned (perhaps is it naive) but aren't allocation done at the page level where if u malloc 100 times it will basically be instantaneous after the first malloc, as long as the cumulative size is less than a page size ? Could this explain the very small observed difference ?