It was a bit of a bummer when go switched from the conservative gc to a precise gc. One of the implications was that they needed to change how interface types were represented.
They had a nice little optimization for word-sized values to store in-place rather than as a pointer out to a value. With the precise gc, they had to make the change to only storing pointers, leading to allocating small values.
I don't know if they've done work to (or perhaps better put: had success) regain the performance hit from the extra allocation & gc load.
On the flip side, my experience is that they've made the pretty unobtrusive with regards to latency and pauses. Or perhaps I'm just not stressing it as much as I had in the past.
Random anecdote on gc tuning: I was once dealing with a go process that sped up (higher throughput, lower latency) by an alarming amount limiting the max processors. This was many years ago, and I wouldn't be able to say what version of go. It was after you no longer had to set GOMAXPROCS, but probably not very long after.
It's always important to know your bottlenecks before tuning. If you're disk io bound, throwing 100 goroutines at it just compounds the problem, for example.
One very common thing I've noticed is that people new to the language overuse/abuse goroutines and channels. I completely get why, they are two selling points you learn about early on. But it's really easy to make things go wrong when spamming them everywhere.
Performance tuning is still largely a dark art from what I see, having dabbled in the space.
It’s both weird and beautiful because getting an end-to-end understanding is instrumental, so you often have to go look at many marginal things that might actually play a significant role.
Disappointingly, it's a dark art often because the CPU is a black box. Intel X86 chips translate the instructions you give them to some internal microcode and then execute them speculatively, out of order, etc. I'm still mystified by the performance gains afforded by randomly inserting NOP instructions.
Fortunately, at least in my experience, the variability that CPUs introduce (which do matter in many contexts) aren't often the source of slowness. In my experience plain old algorithmic complexity would go a long way in making stuff faster.
I can't tell you the number of times I've fixed code like this
matches = []
for (first : items) {
for (second : items) {
if (first.name == second.name)
matches.add(first);
}
}
Very frequently a bright red spot in most profiler output.
I think there's an element of selection bias in that observation. Since that is the type of performance issue that a profiler is good at finding, those are the performance issues you'll find looking at a profiler.
I think there's an element of selection bias in that observation.
Almost certainly true, I can only speak of my own experiences.
Since that is the type of performance issue that a profiler is good at finding, those are the performance issues you'll find looking at a profiler.
I have to disagree with you on this. Sampling profilers are good at finding out exactly what methods are eating performance. In fact, if anything they have a tendency to push you towards looking at single methods for problems rather than moving up a layer of two to see the big picture (it's why flame graphs are so important in profiling).
I have, for example, seen plenty of times where the profiler indicated that double math was the root cause of problems yet popping a few layers up the stack revealed (sometimes non-obviously) that there was n^2 behavior going on.
There is a plethora of information regarding instruction timings, throughout/latency, execution port usage, etc. that compilers make liberal use of for optimization purposes. You could, in theory, also use that information to establish an upper bound on how long a series of instructions would take to execute. The problem lies in the difference in magnitude between average case and worst case, due to dynamic execution state like CPU cache, branch prediction, kernel scheduling, and so on.
There is uiCA, it achieves an error of about 1% relative to actual measurements of basic block throughput across a wide range of microarchitectures. And then FACILE, similar to uiCA. I don't know of any compilers using these more accurate models, but it is certainly possible.
Intel also provides vtune to annotate sequenced instructions and profile the microseconds and power consumption down to the level of individual instructions.
I assume those NOPs you mention exist for alignment padding. Clang and GCC let you configure the alignment padding of any or all functions, and Clang lets you explicitly align any for-loop anywhere you want with `[[clang::code_align]]`.
It took me a bit to hunt down, but it was part of the go 1.4 release in 2014.
the release notes[0] at the time stated
The implementation of interface values has been modified. In earlier releases, the interface contained a word that was either a pointer or a one-word scalar value, depending on the type of the concrete object stored. This implementation was problematical for the garbage collector, so as of 1.4 interface values always hold a pointer. In running programs, most interface values were pointers anyway, so the effect is minimal, but programs that store integers (for example) in interfaces will see more allocations.
@rsc wrote in some detail[0] about it the initial layout on his blog.
I couldn't find a detailed explanation about how the optimization interacted w/ the gc, but my understanding is that it couldn't discern between pointer and integer values
I can't imagine it was impossible to keep the inline-value optimization; after all, the full type information is always right there in the other word of the interface value, but I think it would have been too complicated/expensive for too little benefit.
The bigger issue IMO is and has been that fat pointers (strings, slices) can't be inlined in interface values. There's definitely some benefit to inlining integers and floats, but the indirection that comes from not inlining them isn't that significant compared to the double-indirection that comes from not inlining strings and slices. There was some discussion on the mailing list IIRC about expanding the interface to 3 words wide (to hold strings at least) or 4 words wide (to hold slices too), but this was rejected as going too far the other way (at the time).
Interestingly, the log/slog package does inline string values at least [1], and demonstrates how such a thing can be done when needed, albeit with a fair deal of complexity.
It was a memory model / two word atomicity problem. The mutator uses two writes, one for type and one for value to create the interface. The GC concurrently reads the 2 words of the interface to see if the value is a pointer or not. This is a race that was considered too expensive / complicated to fix.
The problem with precise GC is usually the same problem with malloc/free - if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput.
I don’t know Go. Is that the problem we are seeing here?
One of the realtime GC solutions that stuck with me is amortized GC, which might be appropriate to Go.
Instead of moving dead objects immediately to the free list you “just” need to stay ahead of allocation. You can accomplish that by freeing memory every time you allocate memory - but not a full GC, just finishing the free of a handful of dead objects.
That puts an upper bound on allocation time without a lower bound on reallocation time.
Precise means that on a GC cycle, only true pointers to heap allocated objects are identified as roots, which means that an unreferenced object cannot be kept alive by a value that happens to have a similar bit pattern as a heap pointer. This guarantees that unreferenced objects are eventually cleaned up, but not that this cleanup happens immediately, certainly not as part of a busy loop. (Unless the system runs out of memory, but in that case, a GC iteration is required anyway.)
Since reference counting is GC, isn't reference counting a form of precise GC? That's certainly the scenario I had in mind reading what OP wrote where deallocation within a hot loop would be possible.
Tracing is the technique to find all alive objects from roots. You dereference a pointer to find there some object, and then to recursively iterate over pointers in that object. But before that you need to choose what to use as roots, and here is a difference: you can be precise with choosing the roots, or to err on a conservative side, choosing more roots than you actually need.
This classification was invented decades ago. I think in 1970s or even earlier. Garbage collection is a large field with lots of ideas and research behind it. There are different approaches to structure the heap, to find roots, to trace living objects. These different approaches oftentimes (but not always) replaceable, you can change how you find roots while leaving other things intact.
GC is a large field, it has its own terminology, and instead of asking "why are we inventing terminology", I'd ask "who we are to change the existing terminology".
if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput
I wonder if there's anything that automatically defers collection within a loop and collects the garbage after the loop is exited. Something like Obj-C's old @autoreleasepool but inserted automatically. Static analysis has gotten so fancy that that might not be a terrible idea once you work out all the nuances (e.g. what if the loop is too short, nested loops, what happens when your entire program is a loop like game loops, etc). Could be the best of both worlds.
But generally I think it turns out that in refcounted GC systems you end up just knowing to not allocate/free in your hot loop or if you're doing it in a loop then it's probably not the thing your hot loop is dominated by.
Generational GC - particularly with escape analysis - can make those temp objects just slightly more expensive than stack allocation.
The odd thing about GenGC is that it punishes you for trying to recycle old objects yourself. You create much more pressure to scan the old generation by doing so, which is expensive. If you have the available memory it’s often better to build a new object and swap it for the retained reference to the old one at the end when you’re done (poor man’s MVCC as well if the switch takes a couple context switches to finish)
Comments
It was a bit of a bummer when go switched from the conservative gc to a precise gc. One of the implications was that they needed to change how interface types were represented.
They had a nice little optimization for word-sized values to store in-place rather than as a pointer out to a value. With the precise gc, they had to make the change to only storing pointers, leading to allocating small values.
I don't know if they've done work to (or perhaps better put: had success) regain the performance hit from the extra allocation & gc load.
On the flip side, my experience is that they've made the pretty unobtrusive with regards to latency and pauses. Or perhaps I'm just not stressing it as much as I had in the past.
Random anecdote on gc tuning: I was once dealing with a go process that sped up (higher throughput, lower latency) by an alarming amount limiting the max processors. This was many years ago, and I wouldn't be able to say what version of go. It was after you no longer had to set GOMAXPROCS, but probably not very long after.
Performance tuning is crazy sometimes.
It's always important to know your bottlenecks before tuning. If you're disk io bound, throwing 100 goroutines at it just compounds the problem, for example.
One very common thing I've noticed is that people new to the language overuse/abuse goroutines and channels. I completely get why, they are two selling points you learn about early on. But it's really easy to make things go wrong when spamming them everywhere.
Performance tuning is still largely a dark art from what I see, having dabbled in the space.
It’s both weird and beautiful because getting an end-to-end understanding is instrumental, so you often have to go look at many marginal things that might actually play a significant role.
Disappointingly, it's a dark art often because the CPU is a black box. Intel X86 chips translate the instructions you give them to some internal microcode and then execute them speculatively, out of order, etc. I'm still mystified by the performance gains afforded by randomly inserting NOP instructions.
Fortunately, at least in my experience, the variability that CPUs introduce (which do matter in many contexts) aren't often the source of slowness. In my experience plain old algorithmic complexity would go a long way in making stuff faster.
I can't tell you the number of times I've fixed code like this
Very frequently a bright red spot in most profiler output.I think there's an element of selection bias in that observation. Since that is the type of performance issue that a profiler is good at finding, those are the performance issues you'll find looking at a profiler.
Almost certainly true, I can only speak of my own experiences.
I have to disagree with you on this. Sampling profilers are good at finding out exactly what methods are eating performance. In fact, if anything they have a tendency to push you towards looking at single methods for problems rather than moving up a layer of two to see the big picture (it's why flame graphs are so important in profiling).
I have, for example, seen plenty of times where the profiler indicated that double math was the root cause of problems yet popping a few layers up the stack revealed (sometimes non-obviously) that there was n^2 behavior going on.
There is a plethora of information regarding instruction timings, throughout/latency, execution port usage, etc. that compilers make liberal use of for optimization purposes. You could, in theory, also use that information to establish an upper bound on how long a series of instructions would take to execute. The problem lies in the difference in magnitude between average case and worst case, due to dynamic execution state like CPU cache, branch prediction, kernel scheduling, and so on.
There is uiCA, it achieves an error of about 1% relative to actual measurements of basic block throughput across a wide range of microarchitectures. And then FACILE, similar to uiCA. I don't know of any compilers using these more accurate models, but it is certainly possible.
Intel also provides vtune to annotate sequenced instructions and profile the microseconds and power consumption down to the level of individual instructions.
I assume those NOPs you mention exist for alignment padding. Clang and GCC let you configure the alignment padding of any or all functions, and Clang lets you explicitly align any for-loop anywhere you want with `[[clang::code_align]]`.
That is why tooling like VTune exist.
Why? Many dynamic languages use a tagged pointer representation which isn't incompatible with precise garbage collectors. Couldn't Go do the same?
Perhaps because Go has pointers to the middle of records and arrays? (And records of arrays, etc.) It's an unusual language feature.
This, plus Go pointers are real memory addresses, a property which is guaranteed by the runtime for unsafe pointer operations and C interop.
It took me a bit to hunt down, but it was part of the go 1.4 release in 2014.
the release notes[0] at the time stated
@rsc wrote in some detail[0] about it the initial layout on his blog.
I couldn't find a detailed explanation about how the optimization interacted w/ the gc, but my understanding is that it couldn't discern between pointer and integer values
[0] https://go.dev/doc/go1.4#runtime [1] https://research.swtch.com/interfaces
I can't imagine it was impossible to keep the inline-value optimization; after all, the full type information is always right there in the other word of the interface value, but I think it would have been too complicated/expensive for too little benefit.
The bigger issue IMO is and has been that fat pointers (strings, slices) can't be inlined in interface values. There's definitely some benefit to inlining integers and floats, but the indirection that comes from not inlining them isn't that significant compared to the double-indirection that comes from not inlining strings and slices. There was some discussion on the mailing list IIRC about expanding the interface to 3 words wide (to hold strings at least) or 4 words wide (to hold slices too), but this was rejected as going too far the other way (at the time).
Interestingly, the log/slog package does inline string values at least [1], and demonstrates how such a thing can be done when needed, albeit with a fair deal of complexity.
[1]: https://cs.opensource.google/go/go/+/refs/tags/go1.23.1:src/...
It was a memory model / two word atomicity problem. The mutator uses two writes, one for type and one for value to create the interface. The GC concurrently reads the 2 words of the interface to see if the value is a pointer or not. This is a race that was considered too expensive / complicated to fix.
The problem with precise GC is usually the same problem with malloc/free - if you allocate in an inner loop you have to free in that inner loop and the bookkeeping kills throughput.
I don’t know Go. Is that the problem we are seeing here?
One of the realtime GC solutions that stuck with me is amortized GC, which might be appropriate to Go.
Instead of moving dead objects immediately to the free list you “just” need to stay ahead of allocation. You can accomplish that by freeing memory every time you allocate memory - but not a full GC, just finishing the free of a handful of dead objects.
That puts an upper bound on allocation time without a lower bound on reallocation time.
That's not what precise GC means.
Precise means that on a GC cycle, only true pointers to heap allocated objects are identified as roots, which means that an unreferenced object cannot be kept alive by a value that happens to have a similar bit pattern as a heap pointer. This guarantees that unreferenced objects are eventually cleaned up, but not that this cleanup happens immediately, certainly not as part of a busy loop. (Unless the system runs out of memory, but in that case, a GC iteration is required anyway.)
Since reference counting is GC, isn't reference counting a form of precise GC? That's certainly the scenario I had in mind reading what OP wrote where deallocation within a hot loop would be possible.
No it’s usually called conservative unless you have loop detection.
Oof. We used to just call that tracing.
Tracing is the technique to find all alive objects from roots. You dereference a pointer to find there some object, and then to recursively iterate over pointers in that object. But before that you need to choose what to use as roots, and here is a difference: you can be precise with choosing the roots, or to err on a conservative side, choosing more roots than you actually need.
That is too subtle of a distinction. Tracing demands roots. Why are we inventing a new classification where we have accurate versus inaccurate roots?
This classification was invented decades ago. I think in 1970s or even earlier. Garbage collection is a large field with lots of ideas and research behind it. There are different approaches to structure the heap, to find roots, to trace living objects. These different approaches oftentimes (but not always) replaceable, you can change how you find roots while leaving other things intact.
GC is a large field, it has its own terminology, and instead of asking "why are we inventing terminology", I'd ask "who we are to change the existing terminology".
i think it is still tracing, it's just a matter of identifying possible roots versus actual roots and constraints that fall out from that.
I wonder if there's anything that automatically defers collection within a loop and collects the garbage after the loop is exited. Something like Obj-C's old @autoreleasepool but inserted automatically. Static analysis has gotten so fancy that that might not be a terrible idea once you work out all the nuances (e.g. what if the loop is too short, nested loops, what happens when your entire program is a loop like game loops, etc). Could be the best of both worlds.
But generally I think it turns out that in refcounted GC systems you end up just knowing to not allocate/free in your hot loop or if you're doing it in a loop then it's probably not the thing your hot loop is dominated by.
Generational GC - particularly with escape analysis - can make those temp objects just slightly more expensive than stack allocation.
The odd thing about GenGC is that it punishes you for trying to recycle old objects yourself. You create much more pressure to scan the old generation by doing so, which is expensive. If you have the available memory it’s often better to build a new object and swap it for the retained reference to the old one at the end when you’re done (poor man’s MVCC as well if the switch takes a couple context switches to finish)
Any tracing GC, conservative or precise, generational or not, already does this. Hinkley is wrong about what "conservative" and "precise" mean.