matherial
2 hours ago
If your algorithm does a ton of small allocations to the point where the allocator is the bottleneck, you're already doing it wrong. The allocator necessarily comes with a lot of overhead because it needs to accommodate diverse use cases, avoid fragmentation, and ideally, implement a variety of security checks. If you're doing something alloc-intensive, you're probably allocating and freeing a lot of identical structures and you'd be better off grabbing some continuous memory and managing that yourself in a task-specific way.
But the reality is that almost no one actually cares about performance because compute is cheaper than expertise and labor, at least in the short haul. Everything is getting more bloated and slower and we just compensate by adding CPU cores, gigabytes and gigahertz.
aseipp
an hour ago
No, musl's allocator is just bad even in completely normal programs, and it is especially awful if you are using even two threads much less a lot of them. It has no TLABs or arenas. It has a single global mutex over alloc/free paths. It does syscalls underneath that lock (mmap) meaning the few fast paths it has are rarely taken under contention and have to fall back to futex wakes, so even 2 threads with minor contention and allocation rate will have visible wait points in profiles, stuck waiting for the allocator. It returns mapped memory to the OS very eagerly when a size class is empty, so even single allocs followed by a single free can cause thrashing as it mmaps/unmmaps things repeatedly for a size class over and over. Etc. You quite literally have to limit your thread count when using musl, because it will tank the performance of actually highly threaded programs that can scale with core count, even at very modest allocation rates and small working set sizes.
Its string routines and memory copy routines are also similarly bad, as the article alludes to. They are just naive loops with nearly no optimization. These are not small insignificant functions where using them is "doing it wrong", they are the backbone of vast amounts of code and can be made multiple times faster. You can similarly see string routines pop up in profiles all the time in musl builds in my experience. And unlike the memory allocator these cannot be "fixed" systematically across the application at link time, so you are stuck with it.
Real programs have to often do things like allocate memory and use multiple threads and process strings. People have been optimizing these things for decades, there is vast amounts of prior art, the musl developers simply did not do so because they prioritize simplicity over nearly everything else (from what I can tell) including performance.
CyberDildonics
20 minutes ago
It has a single global mutex over alloc/free paths. It does syscalls underneath that lock (mmap)
Every default malloc implementation worked this way about 12 years ago. Making lots of small allocations, even from multiple threads then blaming the allocator is a losing strategy. An allocator is only going to be able to mitigate the damage to speed and interactivity.
The solution is and always has been to make larger allocations and use those efficiently.
They are just naive loops with nearly no optimization.
The compiler should be able to take something with good access patterns and make something fast, especially out of the basic C functions.
they are the backbone of vast amounts of code
Performance wise it's unlikely C string functions are actually the bottleneck in a program. Maybe for specific programs a naive memory copy function could benefit from AVX instructions.
Real programs have to often do things like allocate memory
"Have to" and "often" are debatable. Any allocations in a hot loop are the very first things that should be optimized away after profiling.
wakawaka28
15 minutes ago
>Performance wise it's unlikely C string functions are actually the bottleneck in a program. Maybe for specific programs a naive memory copy function could benefit from AVX instructions.
Many programs use lots of strings. It tends to become a bottleneck. It also tends to be very difficult to improve because the strings are everywhere in that kind of program, and refactoring to eliminate them is either impossible or very risky.
haolez
2 hours ago
That's an interesting viewpoint, but then, will the allocator's performance never matter for any use case that is not "wrong"? It doesn't feel right.
gumby
an hour ago
Think about it this way because the issue isn’t specific to allocators: it’s pretty good in general but can often be beaten if you have special understanding of what you need to do. That’s OK.
You can buy cars and trucks that are optimized for driving on freeways and residential streets carrying stuff people often carry. But then there are special vehicles like fork lifts and such that are kinds of large special cases. And then there are weirdo specialised vehicles that have four wheels but are rare and their users can’t live without them.
Languages like C++ let you plug in special allocators if you want. But most people don’t. Some, like HFT people do crazy headstands to avoid slow allocations. I don’t ever want to do that but if they want to, why not. I don’t think they complain that the default case doesn’t fit their needs!
matherial
an hour ago
For a typical program, I bet that the overall impact of the glibc allocator is well under 0.1%. If you can choose between < 0.1% and < 0.12%, I guess it matters in some sense, but not in any practical way. We almost never spend time on other sub-0.1% optimizations. You could probably squeeze a lot more by optimizing CPU branch predictor performance, minimizing CPU cache misses, or fine-tuning the scheduling strategy, but we also don't bother. 'Tis is the era of "native" apps written in Electron.
weinzierl
an hour ago
"But the reality is that almost no one actually cares about performance because compute is cheaper than expertise and labor, at least in the short haul."
Doesn't have to stay that way, with hardware prices soaring and development cost allegedly in free fall.