3 ms·
All GC algorithms have pessimal cases; I believe there is a mathematical proof of that, though I can never find it on the net through the chatter of all the oth
by jerf 9y ago
All GC algorithms have pessimal cases; I believe there is a mathematical proof of that, though I can never find it on the net through the chatter of all the other stuff about garbage collection. This is a pessimal case for the current Go GC, but that alone doesn't prove much because all algorithms have pessimal cases. (Even "manual memory management" can end up with pessimal cases for the automatic part, which is why you might see an improvement with your "manually managed" program by swapping malloc for jemalloc or something. What people call "manual memory management" still generally includes a lot of automatic stuff.)
I believe Go does something like set a threshold of memory use. Once that memory usage is hit, a collection is run. After that collection is run, it uses the new accurate amount of memory used to set the next threshold. The threshold of course start small and have an exponential increase of some sort.
When the program first starts, the threshold is set fairly low. If you immediately start allocating lots of things and keeping them, a common case, it grows to a sensible size in a reasonable number of allocations and sweeps (which as you are growing into your initial footprint, amortize out pretty cheap), and in a lot of cases you won't think much about the GC until you are really pushing performance.
If, however, you write a program that isn't holding on to much RAM in the steady state, such as a crypto algorithm (which for all their algorithmic complexity typically don't take much RAM to run, as compared to, say, loading an image, and I don't know for sure but it's possible this ends up all stack-allocated), and that algorithm allocates a lot of short-term stuff, perhaps even just allocates for its final answer, then you get into a situation where you are quickly generating enough garbage to cross the initial low threshold, but the GC immediately cleans it all up when it runs, so when it is deciding on what the new threshold should be it still picks a low number, causing it to repeat the cycle indefinitely.
Fixes will immediately leap to your mind, but remember you must evaluate your fixes holistically, not as if this is the only case in the world. If it were the only case in the world, it would be an easy problem, and Go never would have exhibited the problem in the first place. In particular, as you consider your "fix", consider also that a real program that used real crypto would be much less likely to see this pessimal case occur, because it is very likely the rest of the program would push the memory thresholds up to something sensible, so the fix of "do nothing" is actually quite likely to work well on non-artifical-benchmark programs. It is likely that the most obvious fix that comes to mind will result in making a program that is deliberately running some small server process or something appearing to leak memory after running for a long period of time, for instance.
(I suspect quite strongly in this case that the correct "fix" is to do nothing.)
- nkurz 9y agoI suspect quite strongly in this case that the correct "fix" is to do nothing. What about a fix that gives the user optional control over the thresholds, or even just a hint as to the desired behavior? Keep the defaults as they are, but add a “pragma” that would set the minimum threshold for GC? Or it could go a long way just to have an option to set a minimum time between collections. While it could easily make things worse for certain situations, I much prefer the option to hang myself over an immutable default that periodically does so without my input or consent.