Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

jemma.dev

Post reply on HN
Print view View original

11–16 of 16 posts

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#11

Post by tenderlove »

treis wrote: post #10
ufo wrote: post #9

Earlier quoted context omitted.

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.

How does it handle the case where a RVALUE is added to an already processed black node in between pauses?

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!

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#12

Post by ufo »

tenderlove wrote: post #11
treis wrote: post #10

Earlier quoted context omitted.

How does it handle the case where a RVALUE is added to an already processed black node in between pauses?

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 whi…

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.

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#13

Post by jemmaissroff »

eklitzke wrote: post #3

Does rvalue mean something different here than it normally means? Normally rvalues refer to temporary values.

The first post in the series also explains RVALUES in the context of the Ruby Heap if it's helpful https://jemma.dev/blog/gc-internal

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#14

Post by jemmaissroff »

Author here, let me know if you have any questions / suggestions for future blog posts. Planning a series around Ruby's GC, definitely with future posts on incremental marking, generational gc and compaction.

Also! Writing a book about managed GC with a focus on Ruby. I'll keep posting updates on twitter @jemmaissroff or you can sign up for updates at https://buttondown.email/jemmaissroff

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#15

Post by ammanley »

jemmaissroff wrote: post #14

Author here, let me know if you have any questions / suggestions for future blog posts. Planning a series around Ruby's GC, definitely with future posts on incremental marking, generational gc and compaction. Also! Writing a book about managed GC with a focus on Ruby. I'll keep posting updates on twitter @jemmaissroff or you can sign up for updates at https://buttondown.email/jemmaissroff

Thank you for contributing to this. Very excited to see more of this.

Re: Ruby Garbage Collection Deep Dive: Tri-Color Mark and Sweep

#16

Post by WJW »

tenderlove wrote: post #5
eklitzke wrote: post #3

Does rvalue mean something different here than it normally means? Normally rvalues refer to temporary values.

RVALUE is the base type in Ruby's heap. It refers specifically to [this struct]( https://github.com/ruby/ruby/blob/7bd93293621b85a87e7e117317... ). All Ruby objects are instances of an RVALUE struct. Hope that helps!

In particular in Ruby it derives from "Ruby value" rather than the C/C++ rvalues that can appear on the righthand side of an assignment.
Post reply on HN