When my system starts using swap space, I've already given up all hopes of a decently running system, so IMHO this particular "bug" doesn't matter much.
Unfortunately that's somewhat expected - regardless of implementation, the sole fact that the GC needs to somehow walk the entire tree to trace still referenced sections makes swap highly impractical -- even if you had not had 40ms stop-the-world pauses the LRU cache used by swap would get thrown away at every GC.
I believe that's actually the same reason why Apple stopped using GC in their frameworks in favour of automatic reference counting.
I remember a research paper about swap and GC, where the GC cooperated with the OS to avoid this kind of issue. AFAIK it went nowhere, too bad.
[–]andreiross[S] 15 points il y a 21 jours
Are you talking about this one? https://cse.buffalo.edu/\~mhertz/bc-pldi-2005.pdf. If so, yes. Too bad. I don't know the repercusions this paper had in the past, though, in the sense of pros and cons of the bookmark collector. Don't know if anyone tried to actually implement it or design it at some point.
This is not entirely correct. If you care about latency, then it doesn't matter on which major fault your application gets paused. Disabling swap protects you from data pages being evicted, but code pages can still be paged out.
If you care about latency, mlock() your memory, do not disable swap. Swap is good and gives the kernel an equal opportunity to evict data and code pages.
For GC enabled languages swap is universally bad. Some gc-pauses are indistinguishable from a system crash. It's a side effect on not having tightly specified memory limits.
I'd rather have applications be oom_killed than having them swap out, the former is rather obvious and demands action.
If you want you application to stay in memory, then make it explicitly with mlock()/mlockall().
Disabling swap will just moves pressere elsewhere: to code pages. And evicted code page is no better: full stall while kernel loads that page from disk.
I think discussing it in a vacuum is pointless, it should depend on how much memory you have. You can have a swap on, but with a low `vm.swappiness` number.
There are good sibling replies answering your question, but to give a specific example: if your application writes something but then doesn't need it anymore. Since we're talking about go, perhaps a data structure you need also holds a reference to data you don't need.
When the kernel needs memory, it goes hunting for a page it can discard. But since that's transparent, the kernel can only discard a page if it knows it can get it back (after all, it's still got valid data on it, and maybe you'll try access it again later).
If there's swap, a page full of stale/unneeded data can be written out to swap. But if there's no swap, your page of "dangling data that you'll never use, but is still valid & referenced" can't be discarded; the kernel doesn't know you won't want it later, and it can't recreate the page if it throws it away.
So like sibling said, at that point it has to find other pages it can evict from memory, ones that _do_ have somewhere persistent they can be written out to. Pages loaded from binaries on disk satisfy that, so those will get dropped instead.
There are two types of pages: anonymous and mapped from files. The code pages are mapped from a binary; they are not very special.
Under memory pressure, the kernel evicts less popular pages from memory. If a page has been mapped from a file, it is dropped (if dirty, then it is written out first). If it is needed later, the kernel can read it back from the file. If a page is anonymous (read: heap page), then there is no backing file and the kernel copies it to swap before dropping it. This is swapping.
So, what happens if you disable swap and the kernel is low on memory? What can it evict? Anonymous pages cannot be evicted: there is no swap to put a copy in. The only choice the kernel has is to evict pages that are mapped from files. Those include pages mapped from the executable. You don't eliminate stalls by disabling swap, you just move them elsewhere: the kernel will page out code and your app gets paused whenever the execution flow hits such a page.
Under memory pressure the system will free the ram used for code pages because it can always load them back from the executable on disk. It’s the same virtual memory mechanism as swap but without needing dedicated swap space. The op is saying disabling swap doesn’t prevent long pauses during memory pressure, because the system just swaps code out instead of dynamically allocated memory.
I don't understand why they felt necessary to rewrite a core component in another language. If you have a garbage collection problem my first intuition would be to produce less garbage!
For example better using the stack, or pulling out the big gun of manual memory management.
I'm sure they had reasons to choose Go when they first designed this project but they don't go into them at all.
Feels like they just wanted to play with a new toy.
> If you have a garbage collection problem my first intuition would be to produce less garbage!
FTA:
“These latency spikes definitely smelled like garbage collection performance impact, but we had written the Go code very efficiently and had very few allocations. We were not creating a lot of garbage.
[…]
the spikes were huge not because of a massive amount of ready-to-free memory, but because the garbage collector needed to scan the entire LRU cache in order to determine if the memory was truly free from references”
They explained in the post why this wasn't an issue: they were producing very little garbage, but there was a very large object graph.
> manual memory management
If you need to do manual memory management in a GC language with no builtin support for it, like Go, that's probably a sign that you should switch to a different language.
In general when you tune knobs for GC, you pay for benefits in one area with sacrifices in another. Two big knobs to turn are pause latency and throughput. You probably wouldn’t want to go full “optimize for latency” because you’d end up with poor throughput. Also vice versa. Java’s reputation for poor GC performance is partly due to historical defaults that tune it for throughput.
Go’s GC is already a “concurrent mark-sweep garbage collector” and already has “extremely low mutator pause times, on the order of tens of microseconds”. It sounds like on-the-fly is just a different flavor of what Go already has.
It's a well known algorithm. Folks who do GCs for a living know about it. The folks who work on Go are surely aware of it. I'm assuming that they do not use it for a good reason, hence my question!
Fil-C's GC (Fil's Unbelievable Garbage Collector) uses an alternative on-the-fly algorithm, which I call Phil's Concurrent Marking.
Phil's Concurrent Marking differs from DLG in that it only requires a Djikstra barrier and uses a permagrey stack (something that Go used to do).
However, FUGC does clever things for coroutines (as in ucontexts, which Fil-C supports) - they are not permagrey; they only become grey if they execute. That's relevant to Go because Go moved away from permagrey stacks because of coroutine scan overheads, which the FUGC coroutine strategy might avoid.
But even if Go could not go back to permagrey, then the answer would be to use DLG, which would involve using the combined Yuasa+Dijstra barrier, which Go uses today anyway
This. Memory bloat bugs are relatively easy to fix in Go, but sometimes it’s an adventure to remove swap bloat. And I think it’s worth removing all swap bloat!
I started wondering if there could be swap-aware GC, like first make the required page swapped in (not that there's any obvious API for that...) and only then pause the world?
One can just add APIs to the Linux kernel, and this would be a pretty straightforward one. (though it might be a little more difficult to avoid a syscall here)
I'm sure an agent can work on this and get some numbers with a day's worth of tokens.
I think we are not realizing the paradigm shift here. A coding agent can implement this with a modest little day’s worth of tokens. This means that no one needs to read or know the APIs any more. We can just add them to the kernel as we need them. Then when we forget that we needed them we can just rediscover the API idea later and spend a day’s worth of tokens. (But let’s be real here. By then it will probably be just 1/3 worth of tokens with all the model improvements as well as the ample training material.)
You could do lots of interesting things with sufficiently deep inter-layer integration.
For example, why not swap out not by LRU page but by dense node clusters on the heap graph, maintaining in-memory summaries of inbound and outbound edges for liveness? If you do this, you don't have to swap the cluster in to do a GC involving it.
If the whole cluster becomes unreachable, you wouldn't even have to swap it back in to get rid of it: you'd just drop the swap reference and deem the swap space free.
I don't see anything this deeply integrated happening near-term, but it's fun to think about.
A GC latency SLO should include operating-system memory pressure. Otherwise, a page-fault problem will look like a collector problem and lead to the wrong fix.
The nasty bit is that swap doesn't just make the allocation slower; if GC metadata gets paged out, you have turned memory pressure into a stop-the-world latency spike.
Because the industry has plenty of experience with referece counting as the very first GC algorithm, already in the early 1960's, in early Lisp implementations, BASIC, Cedar, and several other languages.
The predictable runtime performance is also a myth, because they never take into account the use of NUMA memory, lock contention, possible stack overflow and stop the world in the case of cascaded deletions in naive implementations.
ref counting is expensive in multi-threaded applications. Overall it would have worse performance. When it comes to predictability: deallocating a linked list (for instance) would have to deallocate all of the elements. Dealing with reference cycles is also not simple, either.
I believe that's actually the same reason why Apple stopped using GC in their frameworks in favour of automatic reference counting.
Yes, that's expected and no not "regardless of implementation": the GC implementation CAN be improved.
See this discussion on reddit: https://old.reddit.com/r/programming/comments/1wf2fei/40ms_g...
Copy/pasted here: >>
I remember a research paper about swap and GC, where the GC cooperated with the OS to avoid this kind of issue. AFAIK it went nowhere, too bad.
[–]andreiross[S] 15 points il y a 21 jours
Are you talking about this one? https://cse.buffalo.edu/\~mhertz/bc-pldi-2005.pdf. If so, yes. Too bad. I don't know the repercusions this paper had in the past, though, in the sense of pros and cons of the bookmark collector. Don't know if anyone tried to actually implement it or design it at some point.
[–]renozyx 9 points il y a 21 jours
Yes, congratulations for finding it. And I don't know either,. Except that they did implement it on Linux (of course) https://plasma.cs.umass.edu/emery/cooperative-memory-managem...
<<
Many make the mistake to think there is only one way to do a GC.
One of the authoritative books on the subject, https://gchandbook.org/contents.html
And a quite well known paper on the matter as well, https://dl.acm.org/doi/10.1145/1035292.1028982
That is a tracing GC by the way.
There are also tracing GC implementations with deterministic resource management APIs, .NET and D have them for example.
"Stop doing that"
If you care about latency, disable swap. System wide or for the specific the cgroup.
If you care about latency, mlock() your memory, do not disable swap. Swap is good and gives the kernel an equal opportunity to evict data and code pages.
I'd rather have applications be oom_killed than having them swap out, the former is rather obvious and demands action.
Disabling swap will just moves pressere elsewhere: to code pages. And evicted code page is no better: full stall while kernel loads that page from disk.
When the kernel needs memory, it goes hunting for a page it can discard. But since that's transparent, the kernel can only discard a page if it knows it can get it back (after all, it's still got valid data on it, and maybe you'll try access it again later).
If there's swap, a page full of stale/unneeded data can be written out to swap. But if there's no swap, your page of "dangling data that you'll never use, but is still valid & referenced" can't be discarded; the kernel doesn't know you won't want it later, and it can't recreate the page if it throws it away.
So like sibling said, at that point it has to find other pages it can evict from memory, ones that _do_ have somewhere persistent they can be written out to. Pages loaded from binaries on disk satisfy that, so those will get dropped instead.
Under memory pressure, the kernel evicts less popular pages from memory. If a page has been mapped from a file, it is dropped (if dirty, then it is written out first). If it is needed later, the kernel can read it back from the file. If a page is anonymous (read: heap page), then there is no backing file and the kernel copies it to swap before dropping it. This is swapping.
So, what happens if you disable swap and the kernel is low on memory? What can it evict? Anonymous pages cannot be evicted: there is no swap to put a copy in. The only choice the kernel has is to evict pages that are mapped from files. Those include pages mapped from the executable. You don't eliminate stalls by disabling swap, you just move them elsewhere: the kernel will page out code and your app gets paused whenever the execution flow hits such a page.
For example better using the stack, or pulling out the big gun of manual memory management.
I'm sure they had reasons to choose Go when they first designed this project but they don't go into them at all.
Feels like they just wanted to play with a new toy.
FTA:
“These latency spikes definitely smelled like garbage collection performance impact, but we had written the Go code very efficiently and had very few allocations. We were not creating a lot of garbage.
[…]
the spikes were huge not because of a massive amount of ready-to-free memory, but because the garbage collector needed to scan the entire LRU cache in order to determine if the memory was truly free from references”
They explained in the post why this wasn't an issue: they were producing very little garbage, but there was a very large object graph.
> manual memory management
If you need to do manual memory management in a GC language with no builtin support for it, like Go, that's probably a sign that you should switch to a different language.
In general when you tune knobs for GC, you pay for benefits in one area with sacrifices in another. Two big knobs to turn are pause latency and throughput. You probably wouldn’t want to go full “optimize for latency” because you’d end up with poor throughput. Also vice versa. Java’s reputation for poor GC performance is partly due to historical defaults that tune it for throughput.
Go’s GC is already a “concurrent mark-sweep garbage collector” and already has “extremely low mutator pause times, on the order of tens of microseconds”. It sounds like on-the-fly is just a different flavor of what Go already has.
It's a well known algorithm. Folks who do GCs for a living know about it. The folks who work on Go are surely aware of it. I'm assuming that they do not use it for a good reason, hence my question!
Fil-C's GC (Fil's Unbelievable Garbage Collector) uses an alternative on-the-fly algorithm, which I call Phil's Concurrent Marking.
I've documented it here: https://fil-c.org/fugc
Here's the source: https://github.com/pizlonator/fil-c/blob/deluge/libpas/src/l...
Phil's Concurrent Marking differs from DLG in that it only requires a Djikstra barrier and uses a permagrey stack (something that Go used to do).
However, FUGC does clever things for coroutines (as in ucontexts, which Fil-C supports) - they are not permagrey; they only become grey if they execute. That's relevant to Go because Go moved away from permagrey stacks because of coroutine scan overheads, which the FUGC coroutine strategy might avoid.
But even if Go could not go back to permagrey, then the answer would be to use DLG, which would involve using the combined Yuasa+Dijstra barrier, which Go uses today anyway
I'm sure an agent can work on this and get some numbers with a day's worth of tokens.
For example, why not swap out not by LRU page but by dense node clusters on the heap graph, maintaining in-memory summaries of inbound and outbound edges for liveness? If you do this, you don't have to swap the cluster in to do a GC involving it.
If the whole cluster becomes unreachable, you wouldn't even have to swap it back in to get rid of it: you'd just drop the swap reference and deem the swap space free.
I don't see anything this deeply integrated happening near-term, but it's fun to think about.
I use Rust where i need low latency.
(though of course a swap is a swap - but you can "trigger" it depending on your memory or file access pattern)
The predictable runtime performance is also a myth, because they never take into account the use of NUMA memory, lock contention, possible stack overflow and stop the world in the case of cascaded deletions in naive implementations.
Not really, reference counting can cause a single object deallocation to trigger an arbitrarily long chain of deallocations.