3 ms·

> The reason why you need to formalize the tri-color invariant is because of multithreading issues. Not specifically "multithreading" issues, but rather co

> The reason why you need to formalize the tri-color invariant is because of __multithreading__ issues. Not specifically "multithreading" issues, but rather concurrency. MRI implements incremental marking and lazy sweeping. The GC and the mutator execute in the same thread, but they execute concurrently. The tri-color algorithm ensures consistency in a single threaded, concurrently executing environment. It allows us to "pause" the GC in the middle of marking and allow the mutator to continue in the same thread. > 2. OR, a way for the GC to set all pointers in all registers, variables, and objects, to the "new correct location" while your code wasn't looking. (Aka: "Stop the world" methodology) We're also able to do compaction concurrently with the mutator via a read barrier. > But it does take more effort to compact the heap. Indeed it does!

ufo 6y ago
This is very important to remember. A lot of the time, the incremental GC is still single threaded. The difference is that while a two-color "stop the world" algorithm has to collect everything in one long GC pause, the three-color incremental algorithm can spread the work over a series of smaller pauses.
- treis 6y ago
  How does it handle the case where a RVALUE is added to an already processed black node in between pauses?
  - tenderlove 6y ago
    MRI implements a write barrier. You can check out the write barrier implementation here: https://github.com/ruby/ruby/blob/7bd93293621b85a87e7e117317612bb0a84efb7a/gc.c#L7802 The behavior for writes on a black object is defined in this function: https://github.com/ruby/ruby/blob/7bd93293621b85a87e7e117317612bb0a84efb7a/gc.c#L7766 Basically when a black -> white reference is written during incremental marking, the white object will be grey'd and added to the mark stack. Happy Thursday!
    - ufo 6y ago
      Alternatively, you can also move the gc "backwards", changing the black object. In Lua, sometimes the write barrier recolors the white child object to grey and sometimes it recolors the black parent object to grey. IIRC, the motivation for going backwards is that if you assign a large number of white children, recoloring the parent once is faster than recoloring all the children.

> The reason why you need to formalize the tri-color invariant is because of __multithreading__ issues. Not specifically "multithreading" issues, but rather co

ufo 6y ago

This is very important to remember. A lot of the time, the incremental GC is still single threaded. The difference is that while a two-color "stop the world" algorithm has to collect everything in one long GC pause, the three-color incremental algorithm can spread the work over a series of smaller pauses.

treis 6y ago
How does it handle the case where a RVALUE is added to an already processed black node in between pauses?
- tenderlove 6y ago
  MRI implements a write barrier. You can check out the write barrier implementation here: https://github.com/ruby/ruby/blob/7bd93293621b85a87e7e117317612bb0a84efb7a/gc.c#L7802 The behavior for writes on a black object is defined in this function: https://github.com/ruby/ruby/blob/7bd93293621b85a87e7e117317612bb0a84efb7a/gc.c#L7766 Basically when a black -> white reference is written during incremental marking, the white object will be grey'd and added to the mark stack. Happy Thursday!
  - ufo 6y ago
    Alternatively, you can also move the gc "backwards", changing the black object. In Lua, sometimes the write barrier recolors the white child object to grey and sometimes it recolors the black parent object to grey. IIRC, the motivation for going backwards is that if you assign a large number of white children, recoloring the parent once is faster than recoloring all the children.