3 ms·

For malloc/free specific workload is much more important than for a bump allocator; malloc potentially has branching and different cache access/utilization patt

by 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.
- dzaima 1y ago
  The article does include: > The allocation fast path of the RPython GC is a simple bump pointer, and the assembly for it. Indeed a bump allocator has the disadvantage that it effectively continuously thrashes the lower cache layers, but I'd think that'd be a pretty universal workload-independent issue. (and the cache's LRU will still preserve used parts in the cache, and the thrashing is by definition gonna be pretty evenly spread, giving the user code plenty of time to do other things in between using the thing desired to stay in cache again, slightly lowering the issue) And given that a Python impl will necessarily need to have a GC path anyway, which already will thrash cache (and Python users aren't and won't be writing free()s regardless), it's probably not a bad trade overall. I'd assume for pushing to lists the runtime just explicitly reserves capacity ahead-of-time instead of trying to integrate into the memory manager in any way. You'd want to do that anyway even if using malloc & malloc_usable_size or similar, as you'll end up reallocating way too much without that (in a quick test I see my system malloc + malloc_usable_size + realloc used to push 100000 8-byte elts ending up reallocating 8500 times, with the entire code being just this, realloc settling on rounding up to the next 4KB; the actual pointer only changes 10-50 times, but that's still pretty bad, and would presumably get much worse if the code did anything other than just pushing to a single vec)
  - forrestthewoods 1y ago
    The bump allocator declaration occurs after the 2.1 cycles per allocation line. Perhaps all the information is the article. But it is not presently clearly imho. YMMV. FWIW I’m super supportive of bump allocators and arenas. I just don’t find this particular analysis compelling or sufficiently informative. YMMV.
    - dzaima 1y ago
      Yeah, it is a good bit down; that said, bump allocators are a very common (most common?) option around GC anyway; I personally scrolled straight to the disassembly, and it's pretty clear from that, and the explicit mention of bump allocator is just around there too.
    - kragen 1y ago
      The presentation clearly presumes a lot of implicit knowledge about generational garbage collectors that you not only don't have but firmly believed to be false.
      - forrestthewoods 1y ago
        I have spent quite a lot of time updating code to not generate garbage because the ostensibly super fast GC was infact demonstrably not super fast! I could perhaps be convinced that modern GC are super fast. But in hindsight your blog post is intended to preach to the choir and not change the minds of non-believers. If you ever write an apologetic I will gladly read it. It needs to be a holistic analysis of memory operation cost across all threads.
        kragen 1y ago
        I haven't written a blog post about this; do you mean my HN comment or CF Bolz's blog post? Bolz's blog post is not written to persuade anyone but to provide objective, verifiable information from which people can form their own conclusions. I agree that a holistic analysis of memory operation cost across all threads would be not only more persuasive but more informative. But it is also much more difficult.
- kragen 1y ago
  > 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. Yes, actually, you can, if your pointer-bumping allocator is the nursery allocator for a generational GC, which is the case in PyPy. In fact, you can free objects in the middle so freely that it takes literally zero instructions to free them; all you have to do is not retain a reference to them, and when it is time to move the live objects out of the nursery, the GC will avoid moving them because it never finds a pointer to them. That's how this microbenchmark is able to spend only 2% of its time in the GC, even though it's doing nothing but allocating and initializing objects! This allows you to, precisely, take a random Python GC'd workload and satisfy almost all of its allocations with a simple pointer-bumping allocator. It avoids all the trickiness of pushing onto alternating lists/vec/etc. It's true that in production workloads the time spent in the GC is usually more than 2%, typically more like 15%. The time wasted on write barriers, or on writing your code to copy objects unnecessarily to avoid write barriers, is harder to quantify, much like the time wasted on mutating objects unnecessarily to avoid allocation. It is also true that workload always matters for allocator performance. So it's instructive to see how well RPython's allocator does with a workload which would be a pathological worst case for the kinds of allocators you're accustomed to, yielding performance so dramatically superior that you dismissed it as impossible, like when GMail launched with a gigabyte of email storage per user and Hotmail assumed it was a joke.

by dzaima 1y ago

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.
dzaima 1y ago
The article does include: > The allocation fast path of the RPython GC is a simple bump pointer, and the assembly for it. Indeed a bump allocator has the disadvantage that it effectively continuously thrashes the lower cache layers, but I'd think that'd be a pretty universal workload-independent issue. (and the cache's LRU will still preserve used parts in the cache, and the thrashing is by definition gonna be pretty evenly spread, giving the user code plenty of time to do other things in between using the thing desired to stay in cache again, slightly lowering the issue) And given that a Python impl will necessarily need to have a GC path anyway, which already will thrash cache (and Python users aren't and won't be writing free()s regardless), it's probably not a bad trade overall. I'd assume for pushing to lists the runtime just explicitly reserves capacity ahead-of-time instead of trying to integrate into the memory manager in any way. You'd want to do that anyway even if using malloc & malloc_usable_size or similar, as you'll end up reallocating way too much without that (in a quick test I see my system malloc + malloc_usable_size + realloc used to push 100000 8-byte elts ending up reallocating 8500 times, with the entire code being just this, realloc settling on rounding up to the next 4KB; the actual pointer only changes 10-50 times, but that's still pretty bad, and would presumably get much worse if the code did anything other than just pushing to a single vec)
- forrestthewoods 1y ago
  The bump allocator declaration occurs after the 2.1 cycles per allocation line. Perhaps all the information is the article. But it is not presently clearly imho. YMMV. FWIW I’m super supportive of bump allocators and arenas. I just don’t find this particular analysis compelling or sufficiently informative. YMMV.
  - dzaima 1y ago
    Yeah, it is a good bit down; that said, bump allocators are a very common (most common?) option around GC anyway; I personally scrolled straight to the disassembly, and it's pretty clear from that, and the explicit mention of bump allocator is just around there too.
  - kragen 1y ago
    The presentation clearly presumes a lot of implicit knowledge about generational garbage collectors that you not only don't have but firmly believed to be false.
    - forrestthewoods 1y ago
      I have spent quite a lot of time updating code to not generate garbage because the ostensibly super fast GC was infact demonstrably not super fast! I could perhaps be convinced that modern GC are super fast. But in hindsight your blog post is intended to preach to the choir and not change the minds of non-believers. If you ever write an apologetic I will gladly read it. It needs to be a holistic analysis of memory operation cost across all threads.
      - kragen 1y ago
        I haven't written a blog post about this; do you mean my HN comment or CF Bolz's blog post? Bolz's blog post is not written to persuade anyone but to provide objective, verifiable information from which people can form their own conclusions. I agree that a holistic analysis of memory operation cost across all threads would be not only more persuasive but more informative. But it is also much more difficult.
kragen 1y ago
> 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. Yes, actually, you can, if your pointer-bumping allocator is the nursery allocator for a generational GC, which is the case in PyPy. In fact, you can free objects in the middle so freely that it takes literally zero instructions to free them; all you have to do is not retain a reference to them, and when it is time to move the live objects out of the nursery, the GC will avoid moving them because it never finds a pointer to them. That's how this microbenchmark is able to spend only 2% of its time in the GC, even though it's doing nothing but allocating and initializing objects! This allows you to, precisely, take a random Python GC'd workload and satisfy almost all of its allocations with a simple pointer-bumping allocator. It avoids all the trickiness of pushing onto alternating lists/vec/etc. It's true that in production workloads the time spent in the GC is usually more than 2%, typically more like 15%. The time wasted on write barriers, or on writing your code to copy objects unnecessarily to avoid write barriers, is harder to quantify, much like the time wasted on mutating objects unnecessarily to avoid allocation. It is also true that workload always matters for allocator performance. So it's instructive to see how well RPython's allocator does with a workload which would be a pathological worst case for the kinds of allocators you're accustomed to, yielding performance so dramatically superior that you dismissed it as impossible, like when GMail launched with a gigabyte of email storage per user and Hotmail assumed it was a joke.