4 ms·

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 c

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.

haolez 2mo 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 2mo 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 2mo 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.
  - entrope 2mo ago
    A decade ago, I worked on a simulation program that involved a C++ core with a Python wrapper and DB interface. End users cared a lot about throughout with a rather limited size, weight and power budget. We spent a lot of time optimizing the core -- but basically hit a bottleneck once we got to about 15% of the time that was spent in malloc-related functions. It turned out that was all in the Python layer. Probably there was some level of bad code in our Python code, but it was impractical to figure out where that was. I was shocked because I assumed the simulation core (which ended up almost allocation-free by the end) would always dominate CPU usage. Both allocators and Python have probably gotten better since then, but it was a fascinatingly large and stubborn fraction of CPU time.
    - afiori 2mo ago
      C++ and python are exactly where I would expect this problem to come up
weinzierl 2mo 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.
aseipp 2mo 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 2mo 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.
pseudohadamard 2mo ago
Also: > these numbers are from 4 core EC2 VMs Yeah, because that's the exact sort of hardware musl is aimed at. Here's my counter-bogus-statistic: musl is infinitely faster than glibc on a Nios II processor because musl will fit into memory and glibc won't. Therefore, don't use glibc if you care about your code being able to run. QED.

haolez 2mo 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 2mo 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 2mo 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.
- entrope 2mo ago
  A decade ago, I worked on a simulation program that involved a C++ core with a Python wrapper and DB interface. End users cared a lot about throughout with a rather limited size, weight and power budget. We spent a lot of time optimizing the core -- but basically hit a bottleneck once we got to about 15% of the time that was spent in malloc-related functions. It turned out that was all in the Python layer. Probably there was some level of bad code in our Python code, but it was impractical to figure out where that was. I was shocked because I assumed the simulation core (which ended up almost allocation-free by the end) would always dominate CPU usage. Both allocators and Python have probably gotten better since then, but it was a fascinatingly large and stubborn fraction of CPU time.
  - afiori 2mo ago
    C++ and python are exactly where I would expect this problem to come up

weinzierl 2mo 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.

aseipp 2mo 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 2mo 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.

pseudohadamard 2mo ago

Also: > these numbers are from 4 core EC2 VMs Yeah, because that's the exact sort of hardware musl is aimed at. Here's my counter-bogus-statistic: musl is infinitely faster than glibc on a Nios II processor because musl will fit into memory and glibc won't. Therefore, don't use glibc if you care about your code being able to run. QED.