5 ms·

> Every allocation takes 110116790943 / 10000000000 ≈ 11 instructions and 21074240395 / 10000000000 ≈ 2.1 cycles I don’t believe this in even the slightest. Th

> Every allocation takes 110116790943 / 10000000000 ≈ 11 instructions and 21074240395 / 10000000000 ≈ 2.1 cycles I don’t believe this in even the slightest. That is not a meaningful metric for literally any actual workload in the universe. It defies common sense. A few years ago I ran some benchmarks on an old but vaguely reasonable work load. I came up with a p95 or just 25nanoseconds but p99.9 on the order of tens of microseconds. https://www.forrestthewoods.com/blog/benchmarking-malloc-with-doom3/ https://www.forrestthewoods.com/blog/benchmarking-malloc-wit... Of course “2% of time in GC” is doing a lot of heavy lifting here. But I’d really need to see a real work load for me to start to believe.

kragen 1y ago
You should believe it, because it's true. You were measuring malloc, so of course you came up with numbers that were 20 times worse than PyPy's nursery allocator. That's because malloc is 20 times slower, whatever common sense may say. Also, you're talking about tail latency, while CF Bolz was measuring throughput. Contrary to your assertion, throughput is indeed a meaningful metric, though, especially for interactive UIs such as videogames, tail latency is often more important. For applications like compilers and SMT solvers, on the other hand, throughput matters more. You're right that there are some other costs. A generational or incremental GC more or less requires write barriers, which slow down the parts of your code that mutate existing objects instead of allocating new ones. And a generational collector can move existing objects to a different address, which complicates FFIs that might try to retain pointers to them outside the GC's purview. There are a lot of papers running captured allocation traces like you did against different memory allocators, some of them including GCed allocators. Ben Zorn did a lot of work like this in the 90s, coming to the conclusion that GC was somewhat faster than malloc/free. Both GCs and mallocs have improved substantially since then, but it would be easy to imagine that the results would be similar. Maybe someone has done it. But to a significant extent we write performance-critical code according to the performance characteristics of our platforms. If mutation is fast but allocation is slow, you tend to write code that does less allocation and more mutation than you would if mutation was slow and allocation was fast, all else being equal. So you'd expect code written for platforms with fast allocation to allocate more, which makes faster allocation a bigger advantage for that code. Benchmarking captured allocation traces won't capture that effect. Tail latency has always been one of the worst things about GCs. I hear amazing things about new real-time GC algorithms, including remarkable reports from Azul, but I don't know if they're true or what their price is.
- forrestthewoods 1y ago
  Sorry, I refuse to accept a trivial loop of generating up to 2 objects at a time as ever being a relevant benchmark. I didn’t say throughput wasn’t relevant. I said this test isn’t convincing. > coming to the conclusion that GC was somewhat faster than malloc/free Many people have made that conclusion. Certainly not true for real-time cases where tail latency is critical. Modern GC certainly better than old ones.
  - dzaima 1y ago
    For malloc/free specific workload is much more important than for a bump allocator; malloc potentially has branching and different cache access/utilization patterns depending on requested sizes or distance/pattern between mallocs & frees, whereas a bump allocator is just bumping a single pointer, with basically zero mispredicts, and very simple linear cache utilization that's easily prefetched.
    - forrestthewoods 1y ago
      Yes bump allocators are very fast. (It would have been helpful if the blog post explained what type of allocator it was benchmarking). But you can’t take a random Python GC’d workload and slap it on a bump allocator and call it good. A consequence of bump allocators is you can’t, ahem, freely free objects in the middle. And pushing onto alternating lists/vec/etc is notoriously tricky. Workload always matters. Always.
      - yvdriess 1y ago
        In defense of the OP: bump allocators are part of the CPython runtime. It's used to avoid calling malloc a bazillion times a second. Of course, it still needs to defer to libc for certain objects and to grab more memory for its pools/arena/nursery.
        kragen 1y ago
        This is about the PyPy runtime, not the CPython runtime.
yvdriess 1y ago
Thanks for that article by the way. I've referenced it often to make the point that allocation behaviour is complex and messy. > I don’t believe this in even the slightest. That is not a meaningful metric for literally any actual workload in the universe. It defies common sense. I just want to make the point here that making bump allocators fast is useful because it's an essential part of modern allocators and will be called A LOT in case of CPython. That benchmark is useful to make sure the codegen/JIT is performing like it should, but it is still just measuring bump pointer allocation in the most ideal situation. 2 cycles/alloc is entirely normal reasonable considering modern uarchs, the critical path is two one-cycle uops. Now, I agree with your point that this is far from meaningful for the p95/p99 of actual workloads. That is indeed the metric that users or customers actually care about. Modern GCs, like Go's, have moved away from using throughput as a metric. It's "easy" to make bump allocators fast, the hard problem is everything else around it: you still need to allocate your arenas/pools and manage the object lifetime. In the case of CPython that's refcounting, deallocs, GCs, work that modern CPUs really suck at (bad locality, bad branching). I measured ~19.5% of the wallclock time of pyperformance benchmarks being related to memory management (ISPASS25 poster). That's not taking into account the extra boxing and struct slots being created for bookkeeping purposes, which adds more second-order effect related to cache pressure. It's insanely hard to accurately measure memory management overheads.
- forrestthewoods 1y ago
  > Thanks for that article by the way. I've referenced it often to make the point that allocation behaviour is complex and messy. Happy to hear it! Thanks.

kragen 1y ago

You should believe it, because it's true. You were measuring malloc, so of course you came up with numbers that were 20 times worse than PyPy's nursery allocator. That's because malloc is 20 times slower, whatever common sense may say. Also, you're talking about tail latency, while CF Bolz was measuring throughput. Contrary to your assertion, throughput is indeed a meaningful metric, though, especially for interactive UIs such as videogames, tail latency is often more important. For applications like compilers and SMT solvers, on the other hand, throughput matters more. You're right that there are some other costs. A generational or incremental GC more or less requires write barriers, which slow down the parts of your code that mutate existing objects instead of allocating new ones. And a generational collector can move existing objects to a different address, which complicates FFIs that might try to retain pointers to them outside the GC's purview. There are a lot of papers running captured allocation traces like you did against different memory allocators, some of them including GCed allocators. Ben Zorn did a lot of work like this in the 90s, coming to the conclusion that GC was somewhat faster than malloc/free. Both GCs and mallocs have improved substantially since then, but it would be easy to imagine that the results would be similar. Maybe someone has done it. But to a significant extent we write performance-critical code according to the performance characteristics of our platforms. If mutation is fast but allocation is slow, you tend to write code that does less allocation and more mutation than you would if mutation was slow and allocation was fast, all else being equal. So you'd expect code written for platforms with fast allocation to allocate more, which makes faster allocation a bigger advantage for that code. Benchmarking captured allocation traces won't capture that effect. Tail latency has always been one of the worst things about GCs. I hear amazing things about new real-time GC algorithms, including remarkable reports from Azul, but I don't know if they're true or what their price is.

forrestthewoods 1y ago
Sorry, I refuse to accept a trivial loop of generating up to 2 objects at a time as ever being a relevant benchmark. I didn’t say throughput wasn’t relevant. I said this test isn’t convincing. > coming to the conclusion that GC was somewhat faster than malloc/free Many people have made that conclusion. Certainly not true for real-time cases where tail latency is critical. Modern GC certainly better than old ones.
- dzaima 1y ago
  For malloc/free specific workload is much more important than for a bump allocator; malloc potentially has branching and different cache access/utilization patterns depending on requested sizes or distance/pattern between mallocs & frees, whereas a bump allocator is just bumping a single pointer, with basically zero mispredicts, and very simple linear cache utilization that's easily prefetched.
  - forrestthewoods 1y ago
    Yes bump allocators are very fast. (It would have been helpful if the blog post explained what type of allocator it was benchmarking). But you can’t take a random Python GC’d workload and slap it on a bump allocator and call it good. A consequence of bump allocators is you can’t, ahem, freely free objects in the middle. And pushing onto alternating lists/vec/etc is notoriously tricky. Workload always matters. Always.
    - yvdriess 1y ago
      In defense of the OP: bump allocators are part of the CPython runtime. It's used to avoid calling malloc a bazillion times a second. Of course, it still needs to defer to libc for certain objects and to grab more memory for its pools/arena/nursery.
      - kragen 1y ago
        This is about the PyPy runtime, not the CPython runtime.

yvdriess 1y ago

Thanks for that article by the way. I've referenced it often to make the point that allocation behaviour is complex and messy. > I don’t believe this in even the slightest. That is not a meaningful metric for literally any actual workload in the universe. It defies common sense. I just want to make the point here that making bump allocators fast is useful because it's an essential part of modern allocators and will be called A LOT in case of CPython. That benchmark is useful to make sure the codegen/JIT is performing like it should, but it is still just measuring bump pointer allocation in the most ideal situation. 2 cycles/alloc is entirely normal reasonable considering modern uarchs, the critical path is two one-cycle uops. Now, I agree with your point that this is far from meaningful for the p95/p99 of actual workloads. That is indeed the metric that users or customers actually care about. Modern GCs, like Go's, have moved away from using throughput as a metric. It's "easy" to make bump allocators fast, the hard problem is everything else around it: you still need to allocate your arenas/pools and manage the object lifetime. In the case of CPython that's refcounting, deallocs, GCs, work that modern CPUs really suck at (bad locality, bad branching). I measured ~19.5% of the wallclock time of pyperformance benchmarks being related to memory management (ISPASS25 poster). That's not taking into account the extra boxing and struct slots being created for bookkeeping purposes, which adds more second-order effect related to cache pressure. It's insanely hard to accurately measure memory management overheads.

forrestthewoods 1y ago
> Thanks for that article by the way. I've referenced it often to make the point that allocation behaviour is complex and messy. Happy to hear it! Thanks.