5 ms·

I only skimmed the document, but couldn't find any details about the implementation; it deals mostly with how to pace the GC so that it doesn't run out of memor

by tomp 12y ago

I only skimmed the document, but couldn't find any details about the implementation; it deals mostly with how to pace the GC so that it doesn't run out of memory. I can give you a few hints, though. The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature - it usually means that parts of the GC are concurrent with the mutator (user program), but that there are still synchronization points where pausing the mutator is required. If GC that is actually concurrent 100% of the time, fully-concurrent or on-the-fly label (edit: and pauseless as well, as bradleyjg mentioned) is used. Second, while it's not that hard to implement a mostly-concurrent GC, it's practically impossible to implement an efficient compacting, on-the-fly GC, as it would require read barriers during the compaction phase, which would significantly slow down the program. Azul makes such a GC, but they use privileged (kernel) code to implement read barrier (mutator threads still need to be paused/sychronized with, but not all at the same time) (edit2: Azul's C4 collector doesn't use a kernel read barrier, and apparently their read barrier is much more efficient than most). I don't know if Go features a compacting GC (although many languages do, as that's the only thing that can prevent unbounded heap growth over time), but if it does, it's almost certainly not on-the-fly GC. To summarize, I assume this will only reduce the pauses, not eliminate them.

deleted 12y ago
[deleted]
rdtsc 12y ago
> The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature It is confusing. I think they started using pausless as the term now instead to distinguish between the two. > Azul makes such a GC Anyone who is interested in this, should read how that is implement. Really fascinating and cool. However they are not the only ones. Erlang's GC is also pause-less and concurrent between actors. So GC in one actor won't pause other actors on a multi-core system.
- easytiger 12y ago
  > Anyone who is interested in this, should read how that is implement. Are is it implemented? my understanding was that it retains 4 copies of the entire heap in memory and continuously switches between them, or something like that.
  - nickik 12y ago
    That is not at all how it works. Essentially it splits the hole heap up into pages, pages have a state empty, allocating, evacuting. There are GC threads who constantly reallocate objects from pages that have high amount of unreachable objects to new pages. In order not to have mutator threads waiting for GC threads, they use worksharing. When the mutator wants to read from a page that is evacuting then, it will move that object itself (this is where the need the read barrior). This all requires very small amount of syncronisation, there is one small checkin point that every thread has to visit, then its all concurrent again. The pauses are only relate to how long it takes everybody to checkin, not the size of the heap, or the size of the pages. This allows multible 100GB with very small pause times. I just wrote this from memory and its of course more complicated, but this might help you to think about it.
    - easytiger 12y ago
      Thanks
- tomp 12y ago
  Erlang's threads (called processes in Erlang) don't observably share data, so "concurrent" GC is basically a stop-the-world GC on a thread's local heap. There might be some thread synchronisation involved, but I assume it's much simpler to implement, because you don't have to deal with mutability.
deleted 12y ago
[deleted]
joseraul 12y ago
> it's practically impossible to implement an efficient compacting, on-the-fly GC Go doesn't try (yet) to compact heap by moving objects there. They first need a solution not to break C code. https://groups.google.com/forum/#!msg/golang-nuts/AFEf6VM-qrY/9xxejtH5_pcJ https://groups.google.com/forum/#!msg/golang-nuts/AFEf6VM-qr...
rsc 12y ago
[I work on Go.] As you say, the pacing strategy is about delivering good performance, not about pause times. Pause times are a separable concern. The current (in development) GC is not pauseless. It stops the world to finish each collection. Those pauses are very short (well under 10ms, often under 1ms) so we are not worrying about eliminating them at the moment. But we know how to do that if we choose to. http://dl.acm.org/citation.cfm?id=376810 http://dl.acm.org/citation.cfm?id=376810 (Sapphire) is the current state of the art for pauseless collectors, and one of the authors is the primary developer working on the Go GC now. As a side note, if you don't compact then pauseless becomes much easier. And while it was taken as gospel for decades, it's not clear that on today's hardware you necessarily need to compact, ever. (Cue flames.)
- tomp 12y ago
  > And while it was taken as gospel for decades, it's not clear that on today's hardware you necessarily need to compact, ever. (Cue flames.) Yeah, my (theoretical) designs skipped compaction as well. I would have different arenas for differently-sized objects instead (akin to e.g. TCMalloc), which could be reused very efficiently (although that's probably a common allocation technique by now). Although you could still grow a huge heap in very specific situations, if the program behaved at least somewhat consistently (kept allocating objects of roughly the same size), you wouldn't need compaction at all. Again, this is just theory, unfortunately :) I'll check out Sapphire!

by tomp 12y ago

deleted 12y ago

[deleted]

rdtsc 12y ago

> The title says concurrent GC, which is, unfortunately, usually a misnomer in GC literature It is confusing. I think they started using pausless as the term now instead to distinguish between the two. > Azul makes such a GC Anyone who is interested in this, should read how that is implement. Really fascinating and cool. However they are not the only ones. Erlang's GC is also pause-less and concurrent between actors. So GC in one actor won't pause other actors on a multi-core system.

easytiger 12y ago
> Anyone who is interested in this, should read how that is implement. Are is it implemented? my understanding was that it retains 4 copies of the entire heap in memory and continuously switches between them, or something like that.
- nickik 12y ago
  That is not at all how it works. Essentially it splits the hole heap up into pages, pages have a state empty, allocating, evacuting. There are GC threads who constantly reallocate objects from pages that have high amount of unreachable objects to new pages. In order not to have mutator threads waiting for GC threads, they use worksharing. When the mutator wants to read from a page that is evacuting then, it will move that object itself (this is where the need the read barrior). This all requires very small amount of syncronisation, there is one small checkin point that every thread has to visit, then its all concurrent again. The pauses are only relate to how long it takes everybody to checkin, not the size of the heap, or the size of the pages. This allows multible 100GB with very small pause times. I just wrote this from memory and its of course more complicated, but this might help you to think about it.
  - easytiger 12y ago
    Thanks
tomp 12y ago
Erlang's threads (called processes in Erlang) don't observably share data, so "concurrent" GC is basically a stop-the-world GC on a thread's local heap. There might be some thread synchronisation involved, but I assume it's much simpler to implement, because you don't have to deal with mutability.

deleted 12y ago

[deleted]

joseraul 12y ago

> it's practically impossible to implement an efficient compacting, on-the-fly GC Go doesn't try (yet) to compact heap by moving objects there. They first need a solution not to break C code. https://groups.google.com/forum/#!msg/golang-nuts/AFEf6VM-qrY/9xxejtH5_pcJ https://groups.google.com/forum/#!msg/golang-nuts/AFEf6VM-qr...

rsc 12y ago

[I work on Go.] As you say, the pacing strategy is about delivering good performance, not about pause times. Pause times are a separable concern. The current (in development) GC is not pauseless. It stops the world to finish each collection. Those pauses are very short (well under 10ms, often under 1ms) so we are not worrying about eliminating them at the moment. But we know how to do that if we choose to. http://dl.acm.org/citation.cfm?id=376810 http://dl.acm.org/citation.cfm?id=376810 (Sapphire) is the current state of the art for pauseless collectors, and one of the authors is the primary developer working on the Go GC now. As a side note, if you don't compact then pauseless becomes much easier. And while it was taken as gospel for decades, it's not clear that on today's hardware you necessarily need to compact, ever. (Cue flames.)

tomp 12y ago
> And while it was taken as gospel for decades, it's not clear that on today's hardware you necessarily need to compact, ever. (Cue flames.) Yeah, my (theoretical) designs skipped compaction as well. I would have different arenas for differently-sized objects instead (akin to e.g. TCMalloc), which could be reused very efficiently (although that's probably a common allocation technique by now). Although you could still grow a huge heap in very specific situations, if the program behaved at least somewhat consistently (kept allocating objects of roughly the same size), you wouldn't need compaction at all. Again, this is just theory, unfortunately :) I'll check out Sapphire!