3 ms·

Would it make sense to have the VM to do partial mark and sweeps instead? Let's say the references are a lot. Like tens of millions order of magnitude. Would

Would it make sense to have the VM to do partial mark and sweeps instead? Let's say the references are a lot. Like tens of millions order of magnitude. Would it make sense to GC sweeping it in chunks?

vore 4y ago
This is what incremental garbage collection does: you don't necessarily have to do it all at once, you can make incremental progress as needed.
- MaulingMonkey 4y ago
  And the big caveat to this simple modification is that, if done naively, previously marked objects may become the sole referencers of non-garbage without being re-enumerated - potentially leading to the garbage-collection of non-garbage, which would be a serious bug. To fix this, you might have the live code that runs in-between the partial mark+sweeps mark objects to be re-swept as it runs. This adds overhead and complexity, of course. This code is apparently called write barriers by Ruby's GC: https://jemma.dev/blog/gc-incremental https://jemma.dev/blog/gc-incremental https://blog.peterzhu.ca/notes-on-ruby-gc/ https://blog.peterzhu.ca/notes-on-ruby-gc/ http://www.atdot.net/~ko1/activities/rgengc_ismm.pdf http://www.atdot.net/~ko1/activities/rgengc_ismm.pdf I'm left wondering what the overhead of such greylisting / write barriers are, compared to the reference counting overhead mentioned by shwestrick in the "Reference count, don't garbage collect" thread: https://news.ycombinator.com/item?id=32277088 https://news.ycombinator.com/item?id=32277088
  - chc4 4y ago
    Conventual wisdom is the overhead of write barriers is somewhere around 5-10%. There are tricks you can use to reduce it, though; you can coalesce the barriers for objects together into one block of operations if you have a JIT, only do the write barrier if the GC is in a collecting state (and then the overhead is 0% most of the time!), skip the barrier if you know an object is short lived and doesn't escape a scope, etc.
  - moonchild 4y ago
    > This code is apparently called write barriers by Ruby's GC 'write barrier' is a standard term (along with 'read barrier'). See memory management glossary: https://www.memorymanagement.org/glossary/b.html#barrier-1 https://www.memorymanagement.org/glossary/b.html#barrier-1 > wondering what the overhead of such greylisting / write barriers are https://twitter.com/stevemblackburn/status/1494240906006110209 https://twitter.com/stevemblackburn/status/14942409060061102... Read barriers are more expensive.
    - whizzter 4y ago
      Slight correction, write barriers are usually more expensive(even far more complex sometimes). HOWEVER reads outnumbers writes by a large margin of 10:1 in common code (iirc this was measured in Java code some 20 years ago so might vary by language), so most GC implementations only use write-barriers since they're an prerequisite for incremental GC marking. Read-barriers are a prerequisite for incremental GC moving if you need to compact the heap (many earlier GC's accept pauses for compacting work since they often compact smaller parts of the heap in each pause), Java ZGC introduced incremental compacting in recent years and whilst it hurts computation performance(called "mutator" in papers) more than just write barriers they were positively surprised at how low they managed to get the penalty.
  - im3w1l 4y ago
    So maybe I'm missing something but couldn't the algorithm as described lead to an infinite loop where some annoying thread insists on making black objects grey faster than the gc can turn them black again, so that the GC ends up not being able to make progress? I think the fix is that when a black object makes a new reference to a white object, instead of making the black object grey, it should make the white object grey.
    - deleted 4y ago
      [deleted]
    - ridiculous_fish 4y ago
      There's a variety of ways in which the mutator ("annoying thread") may outrun the collector. These can be resolved by throttling at the point of allocation, "stop the world" collections, or giving up and exploding.
- iainctduncan 4y ago
  Do you have a suggestion for accessible material on learning about incremental GC?
ridiculous_fish 4y ago
Yes indeed. The hard part is knowing when objects are referenced by something you didn't scan. For example you scan the first half of the heap and find some unreferenced objects; how do you know those objects aren't reachable from the second half of the heap? A lot of GC engineering is an attempt to answer that question as efficiently as possible.
mhh__ 4y ago
Why not the CPU? (Intel put a garbage collector in hardware in the iAPX 432)
- sebastianconcpt 4y ago
  Woha! didn't knew that one! So that in 1985? Why this feature didn't got supported further in today's architectures? https://en.wikipedia.org/wiki/Intel_iAPX_432 https://en.wikipedia.org/wiki/Intel_iAPX_432

vore 4y ago

This is what incremental garbage collection does: you don't necessarily have to do it all at once, you can make incremental progress as needed.

MaulingMonkey 4y ago
And the big caveat to this simple modification is that, if done naively, previously marked objects may become the sole referencers of non-garbage without being re-enumerated - potentially leading to the garbage-collection of non-garbage, which would be a serious bug. To fix this, you might have the live code that runs in-between the partial mark+sweeps mark objects to be re-swept as it runs. This adds overhead and complexity, of course. This code is apparently called write barriers by Ruby's GC: https://jemma.dev/blog/gc-incremental https://jemma.dev/blog/gc-incremental https://blog.peterzhu.ca/notes-on-ruby-gc/ https://blog.peterzhu.ca/notes-on-ruby-gc/ http://www.atdot.net/~ko1/activities/rgengc_ismm.pdf http://www.atdot.net/~ko1/activities/rgengc_ismm.pdf I'm left wondering what the overhead of such greylisting / write barriers are, compared to the reference counting overhead mentioned by shwestrick in the "Reference count, don't garbage collect" thread: https://news.ycombinator.com/item?id=32277088 https://news.ycombinator.com/item?id=32277088
- chc4 4y ago
  Conventual wisdom is the overhead of write barriers is somewhere around 5-10%. There are tricks you can use to reduce it, though; you can coalesce the barriers for objects together into one block of operations if you have a JIT, only do the write barrier if the GC is in a collecting state (and then the overhead is 0% most of the time!), skip the barrier if you know an object is short lived and doesn't escape a scope, etc.
- moonchild 4y ago
  > This code is apparently called write barriers by Ruby's GC 'write barrier' is a standard term (along with 'read barrier'). See memory management glossary: https://www.memorymanagement.org/glossary/b.html#barrier-1 https://www.memorymanagement.org/glossary/b.html#barrier-1 > wondering what the overhead of such greylisting / write barriers are https://twitter.com/stevemblackburn/status/1494240906006110209 https://twitter.com/stevemblackburn/status/14942409060061102... Read barriers are more expensive.
  - whizzter 4y ago
    Slight correction, write barriers are usually more expensive(even far more complex sometimes). HOWEVER reads outnumbers writes by a large margin of 10:1 in common code (iirc this was measured in Java code some 20 years ago so might vary by language), so most GC implementations only use write-barriers since they're an prerequisite for incremental GC marking. Read-barriers are a prerequisite for incremental GC moving if you need to compact the heap (many earlier GC's accept pauses for compacting work since they often compact smaller parts of the heap in each pause), Java ZGC introduced incremental compacting in recent years and whilst it hurts computation performance(called "mutator" in papers) more than just write barriers they were positively surprised at how low they managed to get the penalty.
- im3w1l 4y ago
  So maybe I'm missing something but couldn't the algorithm as described lead to an infinite loop where some annoying thread insists on making black objects grey faster than the gc can turn them black again, so that the GC ends up not being able to make progress? I think the fix is that when a black object makes a new reference to a white object, instead of making the black object grey, it should make the white object grey.
  - deleted 4y ago
    [deleted]
  - ridiculous_fish 4y ago
    There's a variety of ways in which the mutator ("annoying thread") may outrun the collector. These can be resolved by throttling at the point of allocation, "stop the world" collections, or giving up and exploding.
iainctduncan 4y ago
Do you have a suggestion for accessible material on learning about incremental GC?

ridiculous_fish 4y ago

Yes indeed. The hard part is knowing when objects are referenced by something you didn't scan. For example you scan the first half of the heap and find some unreferenced objects; how do you know those objects aren't reachable from the second half of the heap? A lot of GC engineering is an attempt to answer that question as efficiently as possible.

mhh__ 4y ago

Why not the CPU? (Intel put a garbage collector in hardware in the iAPX 432)

sebastianconcpt 4y ago
Woha! didn't knew that one! So that in 1985? Why this feature didn't got supported further in today's architectures? https://en.wikipedia.org/wiki/Intel_iAPX_432 https://en.wikipedia.org/wiki/Intel_iAPX_432