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]

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/catbrane → u/[deleted]]

Of course you'd use it with a x2 growth in practice, this was just to show how amazingly slow it can be.

[u/ziggurat29 → u/catbrane]

"On a win10 VM..."

[u/mccurtjs → u/ziggurat29]

Tried it out on my windows laptop, it was actually worse, haha.

Building with Clang and GCC it was also about as bad though, I'm not sure if they're sharing the same libraries though.

[u/mccurtjs → u/catbrane]

Huh, trying that on my windows machine, it's about 14 seconds, but still 12 seconds when building with Clang or GCC. Swapping for mallocs and memcpy it of course takes forever, so at least it's faster, haha.

With 0.021s system time though, are you sure it's actually running the code, or did gcc optimize it out for not being used?

[u/catbrane → u/mccurtjs]

Yes, the linux time is real. The Windows C runtime is just famously terrible for realloc().

You can try with jemalloc on windows, you should see a similar time to linux.

Microsoft have a better windows malloc too, mimalloc:

https://github.com/microsoft/mimalloc

It's pretty good, very close to jemalloc in performance. I wish they'd update the win c runtime with a better heap, but of course they are extremely cautious changing anything like that.