Fil-C's GC has basically always had size-specialized allocation and I've done some experiments with this so I have my own data.
As the post says, there are two potential benefits:
- Faster memory clearing when the compiler knows the size. In Fil-C, I leverage that by having LLVM emit a memset inline, so it often ends up being some SIMD crap.
- Faster size class computation.
Interestingly, the faster size class computation isn't really faster in practice. I implemented it and that's how the ABI works today, but I'm likely to move the size class computation into the runtime to simply the ABI, since repeated experiments show that there are no savings to be had there. It's super surprising, but the numbers don't lie.
Anyway, cool to see other fast non-moving GCs also finding the same sweet spot as me.
(Posted from WebKit built with Fil-C so for extra meta, I'm using the GC I describe to write this post)
I’m not sure if you were getting at this by mentioning the ABI specifically, but for Go the “faster size class computation” isn’t purely about the computation itself.
There are lots of cases in the allocator that are conditional on size class (tiny allocations have a bunch of special cases, as do large allocations). Pointer/no-pointer allocations also have lots of special cases.
In the specialized functions, these conditionals become constant and lots of code falls away. We don’t pay the cost for those comparisons anymore, plus since code size is smaller it is now more reasonable to inline callees a bit more aggressively.
Michael also put a lot of time into finding the right balance of code size. At first you want to specialize everything, but that is going to increase code size a lot and thus hurt icache performance. If I recall correctly, our initial version had a code size increase ~4x higher than what we ended up with in 1.27. The final version specializes far fewer size classes yet actually had better performance than the original version.
Regarding the ABI, we definitely see an improvement with static calls vs computing the size class in the runtime. If I recall correctly, it’s the indirect call to the specialized function through a lookup table that stalls the dynamic case.
> I’m not sure if you were getting at this by mentioning the ABI specifically
Fil-C dynamically links its runtime, and it's a goal to support having different runtime versions link against code compiled by different versions of the compiler, within the same ABI epoch.
Hence, the current thing where the compiler computes the allocator bucket means that the shape of allocator buckets in the thread object is part of the ABI.
> In the specialized functions, these conditionals become constant and lots of code falls away
I see. That's a key difference from Fil-C.
Fil-C's GC only specializes on size in the sense that you end up in a different allocator bucket.
> we definitely see an improvement with static calls vs computing the size class in the runtime
On a sufficiently anemic CPU doing enough fast allocation you can get measurable improvements from that kind of thing, but for a superscalar CPU and a general purpose allocator I agree you'd be hard pressed.
Super interesting!
Fil-C's GC has basically always had size-specialized allocation and I've done some experiments with this so I have my own data.
As the post says, there are two potential benefits:
- Faster memory clearing when the compiler knows the size. In Fil-C, I leverage that by having LLVM emit a memset inline, so it often ends up being some SIMD crap.
- Faster size class computation.
Interestingly, the faster size class computation isn't really faster in practice. I implemented it and that's how the ABI works today, but I'm likely to move the size class computation into the runtime to simply the ABI, since repeated experiments show that there are no savings to be had there. It's super surprising, but the numbers don't lie.
Anyway, cool to see other fast non-moving GCs also finding the same sweet spot as me.
(Posted from WebKit built with Fil-C so for extra meta, I'm using the GC I describe to write this post)
I’m not sure if you were getting at this by mentioning the ABI specifically, but for Go the “faster size class computation” isn’t purely about the computation itself.
There are lots of cases in the allocator that are conditional on size class (tiny allocations have a bunch of special cases, as do large allocations). Pointer/no-pointer allocations also have lots of special cases.
In the specialized functions, these conditionals become constant and lots of code falls away. We don’t pay the cost for those comparisons anymore, plus since code size is smaller it is now more reasonable to inline callees a bit more aggressively.
Michael also put a lot of time into finding the right balance of code size. At first you want to specialize everything, but that is going to increase code size a lot and thus hurt icache performance. If I recall correctly, our initial version had a code size increase ~4x higher than what we ended up with in 1.27. The final version specializes far fewer size classes yet actually had better performance than the original version.
Regarding the ABI, we definitely see an improvement with static calls vs computing the size class in the runtime. If I recall correctly, it’s the indirect call to the specialized function through a lookup table that stalls the dynamic case.
> I’m not sure if you were getting at this by mentioning the ABI specifically
Fil-C dynamically links its runtime, and it's a goal to support having different runtime versions link against code compiled by different versions of the compiler, within the same ABI epoch.
Hence, the current thing where the compiler computes the allocator bucket means that the shape of allocator buckets in the thread object is part of the ABI.
> In the specialized functions, these conditionals become constant and lots of code falls away
I see. That's a key difference from Fil-C.
Fil-C's GC only specializes on size in the sense that you end up in a different allocator bucket.
> we definitely see an improvement with static calls vs computing the size class in the runtime
I don't doubt that you do.
I just find it interesting that I don't.
Not sure what the difference is
https://github.com/protocolbuffers/protobuf/commit/50f9ac3ba...
On a sufficiently anemic CPU doing enough fast allocation you can get measurable improvements from that kind of thing, but for a superscalar CPU and a general purpose allocator I agree you'd be hard pressed.
Not sure that protobuf change is the same thing
But you might be right on your overall point: on my big x86 CPU, it doesn't matter, but it might matter on some tiny arm thingy