15 ms·

Go GC: Prioritizing low latency and simplicity

214 points by dbaupp 11y ago

w_t_payne 11y ago
I'd prioritize predictability over anything else.
z92 11y ago
I was wondering, why not use ARC, as in C++ and Obj-C?
- mehrdada 11y ago
  Reference counting generally suffers from the cyclic reference problem, e.g. if you lose a reference to a doubly-linked-list, the entire data structure leaks and won't get freed. In Obj-C, this problem is tackled via manually annotating some pointers as "weak", explicitly (and you have to be extra careful with them). There are less fundamental issues as well, like high contention on the reference count in highly parallel environments, and more memory fragmentation compared to a compacting garbage collector. Also, memory allocation tends to be faster on a compacting garbage collected heap (simply increment the heap pointer instead of searching for a large enough available block). Additionally, freeing memory when things run out of scope cause challenges when optimizing code, like making it more difficult to optimize function invocations that otherwise would have been eliminated as tail calls with a garbage collector. In practice, in some cases, the cost of a tracing garbage collector might be well worth when you amortize it over the lifetime of the program, compared to keeping track of reference counts at runtime.
- frnzkfk 11y ago
  The classic problem: cycles. Either you make the programmer manually deal with cycles via weak references, which can be error prone and allow memory bugs to creep in, or you have a secondary GC to collect cycles. The first one increases programmer complexity and the second one increases implementation complexity, which are, respectively, the first and second things Go attempts to avoid. There's also the issue that ARC vs. GC is a tradeoff between CPU overhead and memory overhead, and that in the scenarios Go was initially designed for (Google's servers) memory is much cheaper.
- millstone 11y ago
  The Go FAQ addresses this: http://golang.org/doc/faq#garbage_collection http://golang.org/doc/faq#garbage_collection Upon re-reading, it's distressing to hear that the GC latency has been raised from "not significant" to "low."
- zurn 11y ago
  In addition to the cyclic references problem, rc has a high constant overhead (memory traffic from constant manipulation of rc fields) and a problem with pauses (cascading deallocations). Also it precludes efficient shared memory concurrent access of managed objects.
- mzl 11y ago
  Simple reference counting is quite possibly the worst possible choice for automatic garbage collection, especially since it is so intuitively appealing. The common objection is that cycles are hard to handle; leading to either a broken behaviour (leaking garbage) or adding complicated cycle detection (negating the premise of a simple solution). Apart from cycles, reference counting has several other issues. Some of my pet objections are: * The need to add a mutable field to every object increases the active memory foot-print significantly (especially bad for caches). * The frequent updates to that field must be done using atomic operations if the objects may be accessed by different threads (even though the objects themselves may be immutable). * The updates to the reference field trashes the caches in a multi-core processor. * The amount of work done managing these updates can easily become a significant part of the run-time of the program, in some cases dwarfing the actual work. * Uncontrolled arbitrarily long pauses will happen when cascading deletions happen. There are really cool and smart algorithms that make reference counting much better, but then the appeal of a simple natural algorithm for collecting garbage has come and gone.
  - fauigerzigerk 11y ago
    >There are really cool and smart algorithms that make reference counting much better, but then the appeal of a simple natural algorithm for collecting garbage has come and gone. That's probably true, but if the win is pauseless automatic memory management that doesn't require twice as much memory as using a GC, then it may be worth it. I think, realistically, we'll have to accept that both tracing GC and reference counting (however smart) will always suffer from some drawbacks that manual memory management can solve. The reverse is also true.
    - mzl 11y ago
      Sure, a really smart implementation (coalescing reference count updates, concurrent de-allocations to get pauslessness, etc) could have some nice properties. However, while the amount of virtual memory needed for a tracing GC might seem large, it is not active memory. Reference counting on the other hand will significantly increase the amount of active used memory, especially if many small objects are common. As for GC vs. manual memory management, both have their uses. For most systems I would argue that GC is the way to go since it is quite efficient and is much more productive. On the other hand, I actually like writing code that has manual memory management. My current interest is learning more Rust for that kind of development.
windlep 11y ago
"To create a garbage collector for the next decade, we turned to an algorithm from decades ago. Go's new garbage collector is a concurrent, tri-color, mark-sweep collector, an idea first proposed by Dijkstra in 1978." So, the best GC for the next decade was proposed in 1978. Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home? I'd be really really curious to hear from some academic computer scientists if the best that can be done was first proposed back then, and they've all just failed to find anything better since. Cause this is just downright depressing otherwise (If you actually want to believe that we're making progress).
- mholt 11y ago
  I'm no academic (just a CS student), but from the very little I understand about GC algorithms, there's no free lunch. In other words, choosing GC isn't like shopping for a new condo... different algorithms have different advantages and implementation difficulties. There may also be caveats with some algorithms that others aren't plagued by. "Better" means different things to different people and in different situations. For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them. Theory doesn't obsolete like technologies do. No need to get depressed by this. Hard problems are still hard (until proven otherwise), and taking out the trash is the same today as it has ever been.
  - eternalban 11y ago
    > For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them. This is only the case/sensible for algorithms that have not been practically improved.
- pcwalton 11y ago
  > Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home? 1. Most modern high-performance garbage collectors are both concurrent/incremental and generational. Generational GC is really important for throughput and I think Go will need to get it eventually. 2. The tri-color marking algorithm plus the idea of a nursery and tenured generation are all very old as far as ideas go, but the devil is in the details, and that's where the research lies. Hash tables, for example, date back to the '50s, but there's been constant research on refinements of the technique up to the present day.
spullara 11y ago
Quite a lot of hubris in thinking they are just going to solve this as if no one has been working on it. Who knows, maybe they have, but color me skeptical.
- robmccoll 11y ago
  Garbage collection was solved long ago: just manage your own memory ;-)
  - pekk 11y ago
    This comment shouldn't have been hit so hard. It's a valid response to people complaining about the throughput/latency tradeoff, especially in special areas like small embedded devices. Go's GC can't just remove all the latency. If you can't stand the tradeoff, then you have to manage your own memory in a way that suits your special case.
    - pkroll 11y ago
      My guess? It's not being downvoted because people don't think managing your own memory is verbotten. It's being downvoted because it's a smart-ass comment seemingly meant to be humorous more than insightful. Your reply is about 10x more useful than the parent.
- eloff 11y ago
  I'm sorry, what exactly is your criticism?
  - spullara 11y ago
    Presenting a new GC implementation as solving the low latency problem that people have been working on for decades without any real proof.
- seanmcdirmid 11y ago
  Good GC is an open problem. Even though there has been much work done on the subject, there is still plenty of room for improvement! Server GC, for example, typically tends to be less concurrent to improve throughput. Client GC is more responsive, but also sacrifices throughput. Since Go is positioned for server work, it is very interesting that they are choose what is typically seen as client-side priorities.
alberth 11y ago
>> "Go's new garbage collector is a concurrent, tri-color, mark-sweep collector" So basically, it's the same GC that Mike Pall had planned to implement for LuaJIT 3.0. Too bad Mike recently announced he was transitioning away from doing daily LuaJIT work. http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector
- eloff 11y ago
  Actually he wanted to use a quad-color implementation, which AFAIK is a Mike Pall tweak of a tri-color collector.
- tedunangst 11y ago
  Actually, it's the same GC already used by Lua and Luajit. Read the note at the end of the section on tri-color collectors?
- sriram_malhar 11y ago
  OCaml's collector has also been the three color variety (4, including a color for a free list). But it hasn't been concurrent, which is the non-trivial part.
mehrdada 11y ago
> Today 16 gigabytes of RAM costs $100 and CPUs come with many cores, each with multiple hardware threads. In a decade this hardware will seem quaint. This is a potentially dangerous worldview. While it is true for the server/desktop/laptop segment, it is less of a surety for phones, and downright scary for smaller, low-power embedded/IoT devices.
- zik 11y ago
  Also it assumes that only one program is running on a machine and it's ok to use all the machine's resources. In practice that isn't true - if your web application uses twice as much server memory then you're going to be paying nearly twice as much for your cluster of servers. That makes a big difference.
  - e3b0c 11y ago
    "The most amazing achievement of the computer software industry is its continuing cancellation of the steady and staggering gains made by the computer hardware industry." (Henry Petroski)
    - fauigerzigerk 11y ago
      Right! Had we not squandered all those wonderful hardware performance gains on useless stuff like web browsers, searching the entire internet in milliseconds or streaming HD video over the net, we could now play Pac-Man thousands of times faster than in 1983!!!
- rancur 11y ago
  > potentially dangerous worldview those tools are the same freaks that make Chrome take 150MB-200MB per Tab and ruined my perfectly usable 8GB-RAM system in a matter of 2 years.
  - clessg 11y ago
    You may enjoy this: https://chrome.google.com/webstore/detail/the-great-suspender/klbibkeccnjlkjkiokjodocebajanakg?hl=en https://chrome.google.com/webstore/detail/the-great-suspende...
anarcticpuffin 11y ago
This is very similar to Java's CMS collector[1]. Unfortunately, 10ms is still far too long for some applications. I have hopes for something like Azul's pauseless GC[2] eventually becoming a common GC strategy, but I'm not holding my breath. In the meantime, there's always sun.misc.Unsafe[3] in the JVM world :-( [1] - https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/cms.html https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gc... [2] - http://www.azulsystems.com/zing/pgc http://www.azulsystems.com/zing/pgc [3] - http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/ http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot...
- hencq 11y ago
  In this old thread [1] one of the Azul developers outlines a potential path to having a C4 type GC for Go. Interestingly he mentions moving to a generational collector first, before moving to concurrent. It seems the Go developers have decided to go the other way, i.e. make the collector concurrent, but not generational. One of the reasons given for going generational first is implementing a write-barrier, but from the blog post it sounds like that is implemented for this concurrent collector anyway, so maybe it doesn't really matter. [1] - https://groups.google.com/d/msg/golang-dev/GvA0DaCI2BU/SmEelQsFybkJ https://groups.google.com/d/msg/golang-dev/GvA0DaCI2BU/SmEel...
- rancur 11y ago
  I'm really surprised this is so new. I'm only beginning to enter the field and falling asleep the other night one of my thoughts was 'why doesn't the GC happen piecemeal?' AKA 'who said we have to collect everything, just unload 2 bins worth'. Mainly WRT use in Android, where it causes perceivable hitching
  - Gibbon1 11y ago
    My experience is a lot of people/groups get obsessed with one metric in this case average speed. A pauseless GC is always going to be a bit slower than one that pauses once in a blue moon (meaning all the time from the users standpoint). Requires a really strong will to go against that sort of grain. Just remembered though: Friend who is a Azul developer said that 0x86 processors did not have the correct instructions to support pausesless GC up until very recently. So probably a chicken and the egg problem.
qznc 11y ago
> Maintaining this invariant is the job of the write barrier, which is a small function run by the mutator whenever a pointer in the heap is modified. Synchronization whenever a heap pointer is changed? That does not sound like "low latency".
- dfox 11y ago
  In case of GC terminology "barrier" simply means that some kind of hook is run on read or write of pointer, it does not necessarily imply barrier in the caching or synchronization sense. Typical implementation of write barrier involves adding item to some kind of thread-local queue.
issaria 11y ago
Will this collector evolve into generational in 1.6? or it already does it.
copsarebastards 11y ago
As always with Go, they assume nothing that has happened in the last 3 decades is worth looking at, and retrofit their justifications for their choices to fit that. It's inherently a language that is 3 decades behind other modern languages. It's embarrassing.

214 points by dbaupp 11y ago

w_t_payne 11y ago

I'd prioritize predictability over anything else.

z92 11y ago

I was wondering, why not use ARC, as in C++ and Obj-C?

mehrdada 11y ago
Reference counting generally suffers from the cyclic reference problem, e.g. if you lose a reference to a doubly-linked-list, the entire data structure leaks and won't get freed. In Obj-C, this problem is tackled via manually annotating some pointers as "weak", explicitly (and you have to be extra careful with them). There are less fundamental issues as well, like high contention on the reference count in highly parallel environments, and more memory fragmentation compared to a compacting garbage collector. Also, memory allocation tends to be faster on a compacting garbage collected heap (simply increment the heap pointer instead of searching for a large enough available block). Additionally, freeing memory when things run out of scope cause challenges when optimizing code, like making it more difficult to optimize function invocations that otherwise would have been eliminated as tail calls with a garbage collector. In practice, in some cases, the cost of a tracing garbage collector might be well worth when you amortize it over the lifetime of the program, compared to keeping track of reference counts at runtime.
frnzkfk 11y ago
The classic problem: cycles. Either you make the programmer manually deal with cycles via weak references, which can be error prone and allow memory bugs to creep in, or you have a secondary GC to collect cycles. The first one increases programmer complexity and the second one increases implementation complexity, which are, respectively, the first and second things Go attempts to avoid. There's also the issue that ARC vs. GC is a tradeoff between CPU overhead and memory overhead, and that in the scenarios Go was initially designed for (Google's servers) memory is much cheaper.
millstone 11y ago
The Go FAQ addresses this: http://golang.org/doc/faq#garbage_collection http://golang.org/doc/faq#garbage_collection Upon re-reading, it's distressing to hear that the GC latency has been raised from "not significant" to "low."
zurn 11y ago
In addition to the cyclic references problem, rc has a high constant overhead (memory traffic from constant manipulation of rc fields) and a problem with pauses (cascading deallocations). Also it precludes efficient shared memory concurrent access of managed objects.
mzl 11y ago
Simple reference counting is quite possibly the worst possible choice for automatic garbage collection, especially since it is so intuitively appealing. The common objection is that cycles are hard to handle; leading to either a broken behaviour (leaking garbage) or adding complicated cycle detection (negating the premise of a simple solution). Apart from cycles, reference counting has several other issues. Some of my pet objections are: * The need to add a mutable field to every object increases the active memory foot-print significantly (especially bad for caches). * The frequent updates to that field must be done using atomic operations if the objects may be accessed by different threads (even though the objects themselves may be immutable). * The updates to the reference field trashes the caches in a multi-core processor. * The amount of work done managing these updates can easily become a significant part of the run-time of the program, in some cases dwarfing the actual work. * Uncontrolled arbitrarily long pauses will happen when cascading deletions happen. There are really cool and smart algorithms that make reference counting much better, but then the appeal of a simple natural algorithm for collecting garbage has come and gone.
- fauigerzigerk 11y ago
  >There are really cool and smart algorithms that make reference counting much better, but then the appeal of a simple natural algorithm for collecting garbage has come and gone. That's probably true, but if the win is pauseless automatic memory management that doesn't require twice as much memory as using a GC, then it may be worth it. I think, realistically, we'll have to accept that both tracing GC and reference counting (however smart) will always suffer from some drawbacks that manual memory management can solve. The reverse is also true.
  - mzl 11y ago
    Sure, a really smart implementation (coalescing reference count updates, concurrent de-allocations to get pauslessness, etc) could have some nice properties. However, while the amount of virtual memory needed for a tracing GC might seem large, it is not active memory. Reference counting on the other hand will significantly increase the amount of active used memory, especially if many small objects are common. As for GC vs. manual memory management, both have their uses. For most systems I would argue that GC is the way to go since it is quite efficient and is much more productive. On the other hand, I actually like writing code that has manual memory management. My current interest is learning more Rust for that kind of development.

windlep 11y ago

"To create a garbage collector for the next decade, we turned to an algorithm from decades ago. Go's new garbage collector is a concurrent, tri-color, mark-sweep collector, an idea first proposed by Dijkstra in 1978." So, the best GC for the next decade was proposed in 1978. Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home? I'd be really really curious to hear from some academic computer scientists if the best that can be done was first proposed back then, and they've all just failed to find anything better since. Cause this is just downright depressing otherwise (If you actually want to believe that we're making progress).

mholt 11y ago
I'm no academic (just a CS student), but from the very little I understand about GC algorithms, there's no free lunch. In other words, choosing GC isn't like shopping for a new condo... different algorithms have different advantages and implementation difficulties. There may also be caveats with some algorithms that others aren't plagued by. "Better" means different things to different people and in different situations. For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them. Theory doesn't obsolete like technologies do. No need to get depressed by this. Hard problems are still hard (until proven otherwise), and taking out the trash is the same today as it has ever been.
- eternalban 11y ago
  > For what it's worth, many of today's finest, most important algorithms are from the 50s-70s, or maybe special adaptations of them. This is only the case/sensible for algorithms that have not been practically improved.
pcwalton 11y ago
> Whatever computer scientists have proposed since then apparently hasn't been as good.... so they can all just pack it up and go home? 1. Most modern high-performance garbage collectors are both concurrent/incremental and generational. Generational GC is really important for throughput and I think Go will need to get it eventually. 2. The tri-color marking algorithm plus the idea of a nursery and tenured generation are all very old as far as ideas go, but the devil is in the details, and that's where the research lies. Hash tables, for example, date back to the '50s, but there's been constant research on refinements of the technique up to the present day.

spullara 11y ago

Quite a lot of hubris in thinking they are just going to solve this as if no one has been working on it. Who knows, maybe they have, but color me skeptical.

robmccoll 11y ago
Garbage collection was solved long ago: just manage your own memory ;-)
- pekk 11y ago
  This comment shouldn't have been hit so hard. It's a valid response to people complaining about the throughput/latency tradeoff, especially in special areas like small embedded devices. Go's GC can't just remove all the latency. If you can't stand the tradeoff, then you have to manage your own memory in a way that suits your special case.
  - pkroll 11y ago
    My guess? It's not being downvoted because people don't think managing your own memory is verbotten. It's being downvoted because it's a smart-ass comment seemingly meant to be humorous more than insightful. Your reply is about 10x more useful than the parent.
eloff 11y ago
I'm sorry, what exactly is your criticism?
- spullara 11y ago
  Presenting a new GC implementation as solving the low latency problem that people have been working on for decades without any real proof.
seanmcdirmid 11y ago
Good GC is an open problem. Even though there has been much work done on the subject, there is still plenty of room for improvement! Server GC, for example, typically tends to be less concurrent to improve throughput. Client GC is more responsive, but also sacrifices throughput. Since Go is positioned for server work, it is very interesting that they are choose what is typically seen as client-side priorities.

alberth 11y ago

>> "Go's new garbage collector is a concurrent, tri-color, mark-sweep collector" So basically, it's the same GC that Mike Pall had planned to implement for LuaJIT 3.0. Too bad Mike recently announced he was transitioning away from doing daily LuaJIT work. http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector

eloff 11y ago
Actually he wanted to use a quad-color implementation, which AFAIK is a Mike Pall tweak of a tri-color collector.
tedunangst 11y ago
Actually, it's the same GC already used by Lua and Luajit. Read the note at the end of the section on tri-color collectors?
sriram_malhar 11y ago
OCaml's collector has also been the three color variety (4, including a color for a free list). But it hasn't been concurrent, which is the non-trivial part.

mehrdada 11y ago

> Today 16 gigabytes of RAM costs $100 and CPUs come with many cores, each with multiple hardware threads. In a decade this hardware will seem quaint. This is a potentially dangerous worldview. While it is true for the server/desktop/laptop segment, it is less of a surety for phones, and downright scary for smaller, low-power embedded/IoT devices.

zik 11y ago
Also it assumes that only one program is running on a machine and it's ok to use all the machine's resources. In practice that isn't true - if your web application uses twice as much server memory then you're going to be paying nearly twice as much for your cluster of servers. That makes a big difference.
- e3b0c 11y ago
  "The most amazing achievement of the computer software industry is its continuing cancellation of the steady and staggering gains made by the computer hardware industry." (Henry Petroski)
  - fauigerzigerk 11y ago
    Right! Had we not squandered all those wonderful hardware performance gains on useless stuff like web browsers, searching the entire internet in milliseconds or streaming HD video over the net, we could now play Pac-Man thousands of times faster than in 1983!!!
rancur 11y ago
> potentially dangerous worldview those tools are the same freaks that make Chrome take 150MB-200MB per Tab and ruined my perfectly usable 8GB-RAM system in a matter of 2 years.
- clessg 11y ago
  You may enjoy this: https://chrome.google.com/webstore/detail/the-great-suspender/klbibkeccnjlkjkiokjodocebajanakg?hl=en https://chrome.google.com/webstore/detail/the-great-suspende...

anarcticpuffin 11y ago

This is very similar to Java's CMS collector[1]. Unfortunately, 10ms is still far too long for some applications. I have hopes for something like Azul's pauseless GC[2] eventually becoming a common GC strategy, but I'm not holding my breath. In the meantime, there's always sun.misc.Unsafe[3] in the JVM world :-( [1] - https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gctuning/cms.html https://docs.oracle.com/javase/8/docs/technotes/guides/vm/gc... [2] - http://www.azulsystems.com/zing/pgc http://www.azulsystems.com/zing/pgc [3] - http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/ http://mishadoff.com/blog/java-magic-part-4-sun-dot-misc-dot...

hencq 11y ago
In this old thread [1] one of the Azul developers outlines a potential path to having a C4 type GC for Go. Interestingly he mentions moving to a generational collector first, before moving to concurrent. It seems the Go developers have decided to go the other way, i.e. make the collector concurrent, but not generational. One of the reasons given for going generational first is implementing a write-barrier, but from the blog post it sounds like that is implemented for this concurrent collector anyway, so maybe it doesn't really matter. [1] - https://groups.google.com/d/msg/golang-dev/GvA0DaCI2BU/SmEelQsFybkJ https://groups.google.com/d/msg/golang-dev/GvA0DaCI2BU/SmEel...
rancur 11y ago
I'm really surprised this is so new. I'm only beginning to enter the field and falling asleep the other night one of my thoughts was 'why doesn't the GC happen piecemeal?' AKA 'who said we have to collect everything, just unload 2 bins worth'. Mainly WRT use in Android, where it causes perceivable hitching
- Gibbon1 11y ago
  My experience is a lot of people/groups get obsessed with one metric in this case average speed. A pauseless GC is always going to be a bit slower than one that pauses once in a blue moon (meaning all the time from the users standpoint). Requires a really strong will to go against that sort of grain. Just remembered though: Friend who is a Azul developer said that 0x86 processors did not have the correct instructions to support pausesless GC up until very recently. So probably a chicken and the egg problem.

qznc 11y ago

> Maintaining this invariant is the job of the write barrier, which is a small function run by the mutator whenever a pointer in the heap is modified. Synchronization whenever a heap pointer is changed? That does not sound like "low latency".

dfox 11y ago
In case of GC terminology "barrier" simply means that some kind of hook is run on read or write of pointer, it does not necessarily imply barrier in the caching or synchronization sense. Typical implementation of write barrier involves adding item to some kind of thread-local queue.

issaria 11y ago

Will this collector evolve into generational in 1.6? or it already does it.

copsarebastards 11y ago

As always with Go, they assume nothing that has happened in the last 3 decades is worth looking at, and retrofit their justifications for their choices to fit that. It's inherently a language that is 3 decades behind other modern languages. It's embarrassing.