Post B8aOjMpUR9Y8bl40O0 by puniko@mk.absturztau.be
(DIR) More posts by puniko@mk.absturztau.be
(DIR) Post #B8aOg2U5ci1udjT0Qi by ariadne@social.treehouse.systems
2 likes, 1 repeats
my conclusion is that the answer to malloc performance problems is to malloc less
(DIR) Post #B8aOjMpUR9Y8bl40O0 by puniko@mk.absturztau.be
0 likes, 0 repeats
@ariadne@social.treehouse.systems :nekoyoriNo: serverless:nekoyoriYes: mallocless
(DIR) Post #B8aOuvfhEekDr0zoAK by icing@chaos.social
0 likes, 0 repeats
@ariadne do everything less, smell the roses.
(DIR) Post #B8aPNIWHsbNwpD7dD6 by ariadne@social.treehouse.systems
1 likes, 0 repeats
like seriously, if you are chasing malloc pressure as a performance issue, you've royally fucked up your data structures, it is just that simpleyes, even on musl, or "MUSL" as the techbros call it for whatever reason
(DIR) Post #B8aPXRlyKefkQ0IXU8 by hyc@mastodon.social
0 likes, 0 repeats
@ariadne yep. And never ever use realloc. Heap fragmentation sucks.https://mastodon.social/@hyc/116942733154261966
(DIR) Post #B8aPaAtxW0TgxiKntg by ariadne@social.treehouse.systems
0 likes, 0 repeats
of course the folks who usually make this complaint are running some managed language like node.js or whatever, so when i mean data structures, what i really mean is "objects"
(DIR) Post #B8aRmk5Oj3ZTT5nzk0 by ariadne@social.treehouse.systems
0 likes, 0 repeats
as in, you have too many of them and need to reevaluate your design because you're fragmenting your data all over the place
(DIR) Post #B8aSlGkwO8AsAS69Oy by krutonium@social.treehouse.systems
0 likes, 0 repeats
@ariadne I'll just be over here, allocating and then discarding 100,000 objects a second.Ironically, even when I did that (on purpose mind), allocations weren't even close to a bottleneck.Which makes me wonder wtf other people are doing.
(DIR) Post #B8abDtMpE4rHevygC0 by fazalmajid@vivaldi.net
0 likes, 0 repeats
@ariadne famously the TigerBeetle database does this:https://tigerbeetle.com/blog/2022-10-12-a-database-without-dynamic-memory/
(DIR) Post #B8acU0iZlOsn2qOvyK by ariadne@social.treehouse.systems
0 likes, 0 repeats
and this fragmentation thing is real. modern processors depend heavily on L1D$, mispredictions are super expensive. you have 48KB of it per core on Zen 5.if you have to dereference through a tree of pointers to get to the data, then you're blowing through L1D$ on every API call.yes, malloc-ng is slower than ptmalloc, but not that much slower.if you have malloc pressure, which is the case where malloc performance matters, because the time each malloc call takes to complete stacks up, then you almost always have fragmentation in how you're storing your data.you're chasing the wrong symptom. yes faster malloc exists, but it's a crutch. the real solution is to refactor how data is structured.
(DIR) Post #B8aieO3ATAdg1rMcvQ by ariadne@social.treehouse.systems
0 likes, 0 repeats
@krutonium it isn't the malloc overhead itself that tanks performance, but the fragmentation. if you have to dereference a forest of pointers, that doesn't come for free.but malloc gets blamed because it's a function call, while the dereferencing or other structural overhead is what actually tanks performance because you blow through your L1D$ lines.
(DIR) Post #B8ajbP7G9L1eQ8Q3nc by henryk@chaos.social
0 likes, 0 repeats
@ariadne So, what you're saying is, I should have one global `uint8_t *memory = malloc(LARGE_NUMBER)` and then one subroutine uses memory[0x1000] and up, and another uses memory[0x2000] and up, etc, yes?Because, I've seen projects that work that way. In Perl, but still ;)
(DIR) Post #B8ayRBU1Tp5MYVeSTQ by mcdanlj@social.makerforums.info
0 likes, 0 repeats
@ariadne A bit of a tangent (sorry)...I believe that C shows its heritage of being developed when memory was precious, and ran at about the same speed as the processor, in both design and idiom.Golang using escape analysis to aggressively allocate on the stack, and idiomatically copy data back and forth between stack frames by value instead of passing references, has a tendency to reduce heap pressure and avoid both expensive indirection and TLB thrashing.Early on, people noticed that re-writing programs from C into idiomatic Go sometimes resulted in a substantial performance gain. It was really weird that (in my experience) people fixated on goroutines when talking about this. I was (and remain) convinced that this aggressive architectural focus on data locality was the primary reason for this result that so many folks found surprising.Being designed in the age of 64-bit systems, they didn't have to worry about blowing the stack from large allocations, because addresses were not a precious resource. That removes one rationale for heap allocation, and leaves heap only for memory allocations that need to live beyond the scope in which they were allocated. (By contrast, growing up in a 16-bit and 32-bit era, I was taught to be cautious about using alloca because, well, stack overflow...) Their answer to "How does this scale to too many threads on my 32-bit machine?" seemed to be approximately "That's the neat part, it doesn't."IMHO you have to work meaningfully harder to get that kind of aggressive locality in C, and it would be easy to end up with code that others would consider non-idiomatic. It's possible, but I'm lazy. So I use C less these days. 😀
(DIR) Post #B8boty8pMJhNBtmhAO by ariadne@social.treehouse.systems
0 likes, 0 repeats
@henryk no. I am saying that you should structure your data to avoid superfluous allocations. people blame system malloc for what is typically a data locality problem.
(DIR) Post #B8caQO0Y8jaSd2xaCW by david_chisnall@infosec.exchange
0 likes, 0 repeats
@ariadne @krutonium Malloc often gets blamed because glibc continues to ship with an embarrassingly slow implementation. When we first released snmalloc, we got a report from someone whose end-to-end performance of a Rust codebase doubled when they switched to it from the glibc implementation.This is especially true for multithreaded workloads. A lot of existing malloc implementations started as single threaded. Then they added a lock, which worked fine for low thread counts but rapidly became a problem. Then they added thread caching to avoid hitting the lock. But anything that has a producer-consumer model (allocate on one thread, free on another) hits the pathological case for thread-caching allocators: the produce thread fills its cache then allocates from the cache, then calls the global allocator to fill it again, the consumer thread is always filling its cache but never consuming from it, so the global allocator is still a contention point only now the thread caching is causing objects to sit for longer between being freed and reallocated, so your CPU caches churn more. Moving to a message-passing allocator (such as snmalloc or mimalloc) eliminates this bottleneck.
(DIR) Post #B8czdSOlcnBWrfcJQe by matt@toot.cafe
0 likes, 0 repeats
@ariadne I wonder how common this problem is in Rust, and if there's anything about Rust that makes it hard to avoid excessive mallocs. Anecdotally, it seems fairly common to use an alternative malloc in Rust projects running on musl.
(DIR) Post #B8dFdQ0U7DAoiJGLCK by ariadne@social.treehouse.systems
0 likes, 0 repeats
@david_chisnall @krutonium yes, malloc is slow (and in practice, malloc-ng is approximately ~half the raw performance of ptmalloc), but that's not my point.my point is that in many cases, malloc performance issues are a symptom of a program design problem rather than the root cause.(that doesn't mean that improving malloc performance isn't an interesting problem! snmalloc is great :))
(DIR) Post #B8dGeqn07kJ81QCbia by david_chisnall@infosec.exchange
0 likes, 0 repeats
@ariadne @krutonium I'm not sure I agree with your diagnosis though. A lot of the fragmentation issue that you refer to is really two things:Without help, malloc will not put two objects in adjacent locations. That may or may not matter because, for moderately large objects, they'll be multiple cache lines. Prefetchers are pretty good now. Intel's prefetchers have been able to do 'scanning an array of pointers to object, prefetch the target objects' for so long the patent either just did or is just about to expire, for example. The worst case is for small objects where they may be in the same cache line and you'll get false sharing. If you have a multithreaded workload and send small objects to different threads that both write to the objects, you'll play a lot of cache-line ping-pong. That may be fixable by combining more objects, but if the data are truly independent then padding can help more. But that's largely orthogonal to use of malloc.On top of that, pointer-chasing introduces data dependencies between instructions. Two loads from the same base pointer are independent, a load of a load is a data dependency. This impacts speculative execution because the independent instructions can retire in parallel. This can have a huge impact or zero impact, depending on the design of the CPU (and that varies across microarchitectures in the same generation). Modern CPUs are quite aggressively optimised for pointer-chasing workloads (load-to-use delay for pointer chasing is one of the key metrics that you tune for and microarchitects really hate me when I want things that add a cycle to that cost, even if it's only in the worst case). Independent loads may not actually be faster because they can end up with more rename registers being live and rename register pressure is the thing that can tank performance on a big superscalar chip, but it doesn't always. A bunch of these things have decidedly non-linear performance characteristics. They have quite sharp cliffs, where things below a threshold are fast and above are really slow. And these tend to relate to whole-program properties, rather than be easy to reason about locally.And this is why I don't like computers.