Ruby Garbage Collection in Under Two

Hours
Jemma Issroff
Contents

Ruby Garbage Collection in Under Two Hours 1

Why do we need garbage collection? . . . . . . . . . . . . . . . . . . . . . . . . 1

Structure of Ruby Memory 3

Visualization of the Ruby Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
GC::INTERNAL_CONSTANTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Tri-Color Mark and Sweep 7

Marking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Sweeping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Generational Garbage Collection 14

Major and Minor GCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
What triggers minor vs major GCs? . . . . . . . . . . . . . . . . . . . . . . . . . 16
Write barriers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Incremental Garbage Collection 20

Stop-the-world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Incremental Pauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Write Barriers, again! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Write Barrier Unprotected Objects . . . . . . . . . . . . . . . . . . . . . . . . . 23
Additional work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Compaction 25
Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Why compact? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Two Finger Compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Current state of compaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Object IDs 31
Before Ruby 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Ruby 2.7 Onwards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Compaction and object_ids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

GC.stat 35

ii
 Contents

Future of Ruby GC 38
Variable Width Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

Thank You 39

Additional Resources 40

Glossary 41

iii
Ruby Garbage Collection in Under Two
Hours

Welcome to Ruby Garbage Collection in Under Two Hours! In the pages that follow, I’ve written
a digestible summary of Ruby garbage collection. If you’re anything like me, you might have
a folder on your desktop of ebooks you intended to read, but only made it through a chapter
or two and then never quite finished.
One of my goals for this ebook is that it doesn’t live in anyone’s folder of unfinished ebooks.
I distilled an explanation of Ruby’s garbage collection into something which, as the title sug-
gests, is concise enough to read in under two hours. If you’re able, I’d recommend blocking
off two hours on your calendar and completing this ebook in one sitting.
I’ve previously shared some of the content featured here in other formats. Some of it is from
my blog post series, some of it is from a RailsConf talk I gave, some of it is from my email series,
and some of it only exists in this ebook. If you’ve seen snippets of my work in other places and
found them compelling, my hope is that you’ll also enjoy this more comprehensive story of
Ruby garbage collection.

Or, How to Pack Your Backpack Efficiently

Throughout this ebook, I’ll also describe another passion of mine and the area of my life where
I learned the most about the necessity of space efficiency: backpacking. I’ve backpacked over
2,000 miles, always carrying everything I need with me in my pack. From a tent and sleeping
bag to a carefully orchestrated water filtration system, I need to be intentional about what I
bring and how I use and reuse it. I obsessively go through my gear, checking what I no longer
need in order to make space for new items. My backpack for any camping trip is a finely tuned
demonstration of space efficiency. I’ll refer to it throughout this ebook in an attempt to make
the concepts of Ruby garbage collection more understandable.

Why do we need garbage collection?

As our Ruby programs run, they consume memory. Ruby itself creates objects. For example,
all built-in classes (like String or Class) are objects. Our programs create objects. The gems
we use create objects. All of these need to be stored somewhere in memory so that our pro-
grams can access them.

1
 Ruby Garbage Collection in Under Two Hours

There are also objects which programs only need briefly. For instance, we might instantiate
variables which are only necessary within a method. After the method call, whatever memory
Ruby used to store these variables can be reused to store different values.
Let’s take this further. Not only can the space in memory where some values are stored be
reused for other values, it will likely, at some point, need to be reused. Why? To take this to
an extreme, what would happen if our programs didn’t reuse any of their memory, instead
consuming and consuming memory without ever giving it back?
Or, to take this to our backpacking analogy, what if I didn’t reuse water bottles? What if, for
a given trip, I carried all the water I would need in individual bottles? Firstly, this would be
so heavy. Secondly, the water bottles would never fit. I drink anywhere from 4-8 liters of
water a day while I backpack, depending on the season. For a week-long trip, I would have
accumulated almost 60 liters of water. I simply don’t have that room in my pack.
Similarly, if we didn’t reuse memory, we’d run out of space eventually. The amount of memory
it would take to run our programs would be strictly increasing. But memory is not an unlimited
resource. Every machine we run programs on, whether our laptop or some Heroku dyno, has
a finite amount of it. At some point, if our programs didn’t reuse their memory, they would
inevitably run out of space on the machines running them.
As we’ll explore throughout this ebook, the process of figuring out exactly which parts of mem-
ory can be reused – and when – is complex. Thankfully, Ruby does this for us. The term
Garbage Collection refers to this process of automatic memory management.

2
Structure of Ruby Memory

In order to discuss the strategies garbage collection strategies Ruby uses, we must understand
how Ruby structures its memory.
We might know from experience that the amount of total memory different Ruby programs
consume can be variable. Maybe we’ve run Ruby programs on different size machines, per-
haps Heroku Dynos or AWS EC2 instances of different sizes. Ruby must have some way, there-
fore, to use more memory for programs which require it, and less for programs which don’t.
One of my favorite features of my hiking backpack is the detachable spare pockets. For in-
stance, there’s a big pocket on the top of my backpack that I usually leave off the pack. How-
ever, if I’m going for a longer trip, or a trip in the winter when I need more warm clothes, I
reattach this piece.
Ruby has a similar concept to these pockets, called pages. If Ruby needs more memory space
from the operating system, it requests this space in increments of pages, which are each
roughly 16KB in size. The entire Ruby memory space which holds all these pages is referred
to as the Ruby Heap.
We also know Ruby needs somewhere to store the objects it will access when running a pro-
gram. Each page stores objects, in the same way that each pocket in my backpack stores my
gear. It’s likely I’ll put multiple pieces of gear in each pocket. It would be inefficient to have an
entire pocket with just one item. Similarly, each page in the Ruby Heap can store either 408 or
409 objects in slots. This way, Ruby is not requesting more space from the operating system
for each individual object, but is rather requesting entirely new pages which will allow storage
of hundreds of new objects. The slots within pages are each 40 bytes. As we’ll learn, pages
also have some header data where they store information about the slots themselves.
At the exact moment when Ruby receives new pages from the operating system, the pages
won’t have any meaningful Ruby values in them. The slots will be unoccupied. When the
slots do have Ruby values, or objects, in them, we internally refer to these values as RValues.
An RValue contains basic information about an object. Ruby is written in the C programming
language, and under the hood, RValues are C structs which are unions of all of the possible
data structures for different Ruby objects.

3
 Structure of Ruby Memory

Visualization of the Ruby Heap

For any visual learners, here’s a diagram explaining the structure of the Ruby Heap we just
discussed:

All of these terms are also defined in the Glossary.

GC::INTERNAL_CONSTANTS

Ruby’s GC module exposes GC::INTERNAL_CONSTANTS which tells us more about the sizes of
terms we’ve just learned.
Printing out GC::INTERNAL_CONSTANTS, we see the following:

{
:DEBUG=>false,
:RVALUE_SIZE=>40,
:HEAP_PAGE_OBJ_LIMIT=>409,
:HEAP_PAGE_BITMAP_SIZE=>56,
:HEAP_PAGE_BITMAP_PLANES=>4,

4
 Structure of Ruby Memory

:HEAP_PAGE_SIZE=>16384
}

Let’s look at each key / value pair one by one.

:DEBUG => FALSE

This :DEBUG constant is really more useful for debugging Ruby source code than writing pro-
grams in Ruby, so we don’t have to worry about it. Almost every Ruby program we run will
have :DEBUG => false.
For the extremely curious, the only way :DEBUG is true is if we compile Ruby source code with
a cppflag setting DGC_DEBUG to true (see this example). But, since most of the time we’re not
compiling Ruby source code, it’ll almost always be false and for our purposes we can ignore
this.

:RVALUE_SIZE => 40

The units for all of the constants in this hash which end in _SIZE are bytes. This constant
is telling us that each RVALUE has a size of 40 bytes. Some of these bytes are used to store
metadata about the RValue itself. If an object’s data is too large to store within the 40 bytes
that an RValue occupies, its RValue will contain a pointer to where in the operating system’s
memory space the Ruby object’s value lives.
As a small example, Strings with 23 characters or fewer have their actual String values stored
inside the RValues themselves, while Strings with more than 23 characters have their values
stored in the operating system’s memory. Pat Shaughnessy has a blog post explaining this
nuance.
A critical point here is that all RValues are the exact same size. As we’ll learn, there’s a trade-
off to having all RValues be the same size. It means there are some objects where the whole
object can’t fit into a single RValue. But it also makes memory easy to scan. Ruby knows
exactly where one RValue ends and the next begins. It also knows exactly where any given
RValue on a page starts.
If RValues within the same page were variable size, each RValue would also have to store in-
formation about how many bytes it was (likely within the RValue itself). Then, whenever Ruby
was scanning objects in a page, it would need to read this field from each RValue to determine
where the next RValue began, which would have a performance cost and make it impossible
for Ruby to know where an arbitrary object on a page began.
When we discuss the future of GC at the end of this ebook, we’ll learn that in a future version
of Ruby, RValues will be variable sizes. More on this later though. For now, we know RValues
are all 40 bytes.

5
 Structure of Ruby Memory

:HEAP_PAGE_OBJ_LIMIT => 409

Okay, next up, HEAP_PAGE_OBJ_LIMIT. As we discussed earlier, 409 is the maximum number of
objects per each HEAP_PAGE.

:HEAP_PAGE_BITMAP_SIZE => 56

Bitmaps are where pages store header data about their slots. These bitmaps are 56 bytes.
There are 8 bits in a byte. Which means with our 56 bytes we can store information about 56
* 8 == 448 slots which will safely cover all of the 409 slots in a page.

:HEAP_PAGE_BITMAP_PLANES => 4

As we can confirm in the Ruby source code, this constant is deprecated and no longer useful
in understanding the structure of Ruby memory.

:HEAP_PAGE_SIZE => 16384

Lastly, we have the size of the pages themselves. Each page is 16,384 bytes, or roughly 16KB.
Again, we can check the math here. There should be enough space within each page for all of
its RValues, and a little extra for the header information. We know each page has a maximum
of 409 RValues, and each RValue is 40 bytes. 409 * 40 == 16,360 < 16384.
Each pocket in my backpack also has a fixed size, but I’ll spare you the details of exactly what
these sizes are.

6
Tri-Color Mark and Sweep

Now that we understand the structure of Ruby’s memory, we’re ready to learn how the
garbage collector itself works. We can think through this in loose terms first.
We know that the role of any garbage collector is to reallocate memory when it’s no longer in
use. This will prevent our programs from using unlimited amounts of memory. We now know
RValues, Ruby’s internal representations of our objects, are stored in slots within pages.
If Ruby’s garbage collector is to reuse memory from objects which are no longer in use, it
needs some way to iterate over objects, check if they’re in use, and if not, use the slots storing
them for other objects.
The questions then become, how does Ruby do this efficiently? How does it know which ob-
jects are no longer in use? How can it look through all of the objects without significantly
impacting the execution time of our programs? In other words, what algorithm does Ruby’s
garbage collector use?
EXERCISE: Let’s pause for a minute here and consider different ways we might approach this
problem. If you had to design an algorithm to perform garbage collection, knowing how Ruby
structures its memory, how would you do it? How would you answer all of the above ques-
tions?
Different programming languages have different solutions. As we learn about Ruby’s
approach, we’ll also consider (in significantly less detail) what other options exist.
As the name of this section gives away, the algorithm that Ruby uses is the Tri-Color Mark
and Sweep algorithm. There are two phases to this: marking and sweeping. In the marking
phase, the garbage collector marks all slots which contain RValues that cannot be removed.
In the sweeping phase, the garbage collector indicates that slots with unmarked RValues can
be repurposed.
As we discussed earlier, I also need to consistently clean out the contents of my backpack. If,
for instance, I left all of my empty jars of peanut butter in my pack and never got rid of them,
my food bag within my backpack wouldn’t have room for anything else.

7
 Tri-Color Mark and Sweep

Marking

This marking phase is most straightforward to understand if we imagine all of the objects in
our program to be a directed graph with root nodes. All of the nodes in the graphs are RValues.
All of the edges in the graph are references from one RValue to another. We’ll learn, through
an example, more about what references are.

EXERCISE:
Let’s create an array with a single String in it. As long as our program can access the array, it
must also be able to access the String. Put another way, if the String was garbage collected
while the array was still in use, we’d have a problem!
We know then that the array must reference the String. We can validate this assertion using
Ruby’s ObjectSpace module, which gives us a view into what exists in the Ruby Heap.
ObjectSpace.dump_all gives us a JSON representation of all of the objects it contains. Ob-
jectSpace.dump (which takes an object as a parameter) gives us a JSON representation of a
specific object.
Relevant to our current use case, the hash returned by ObjectSpace.dump has an "address"
key which tells us the memory locations of the object itself, and a "references" key which
tells us the addresses of objects it references:

require "json"
require "objspace"

8
 Tri-Color Mark and Sweep

string = "string"
array = [string]

string_address = JSON.parse(ObjectSpace.dump(string))["address"]
array_references = JSON.parse(ObjectSpace.dump(array))["references"]

string_address == array_references.first
# => true

When you try executing this snippet, play around with multiple references, and even with
references which themselves have references. Soon enough, the image of the Object Space
as a directed graph will make sense!
To return to our backpacking analogy, it’s a bit of a long story, but I was once backpacking
and accidentally lost a single hiking shoe. It was somewhere deep in the woods, and unless I
spent roughly five hours retracing my steps, I was not going to find it.
When I lost it, it dawned on me that it made no sense to keep the other shoe without its partner.
In a sense, these shoes held references to each other. One is only useful in the presence of the
other, so I got rid of the remaining shoe.
Or, in a less extreme, less ”how could this possibly have happened?!” example, I always carry
a spare set of batteries for my headlamp (the flashlight I wear on my head at night). If I’m
not planning on using my headlamp though, I also don’t need the spare set of batteries. The
headlamp has a reference to the spare batteries, and without the headlamp, the batteries
serve no purpose, so it would be wasteful (and unnecessarily heavy) to carry them around.
Earlier, we asked about possible solutions to the problem of memory management. One con-
ceivable idea might have been a concept called Reference Counting. This isn’t a solution Ruby
uses, but it is used by other programming languages. In Reference Counting, each object
keeps its own count of how many other objects reference it. When the count becomes zero,
this means there is no longer any object which references it. At this point, the object can indi-
cate that its space in memory can be used for a different object.
In Ruby though, the reason it’s useful to think of the Object Space as a directed graph is be-
cause Ruby’s garbage collector traces this graph in the marking phase. It starts at the root
nodes of this graph and traces every edge (reference) it can access from these root nodes,
marking every RValue it sees through this process. At the end, any RValue which was not
traced, and therefore not accessible from a root node, will have its slot reallocated.

Tri-Color

Tri-Color is a model we can use to understand how Ruby’s garbage collector tracks its progress
through the marking process. The three colors in the Tri-Color algorithm (three shades, really)
are white, black and grey.

9
 Tri-Color Mark and Sweep

At the beginning of the garbage collection process, every slot in the Ruby Heap, Ruby’s mem-
ory space, is white. Then, as part of the initial setup, all slots which contain root RValues are
marked as grey. Root RValues are all of the RValues that a Ruby program knows it will need
to run. A few concrete examples of roots are global variables, the Ruby virtual machine itself
and any references directly attached to the VM.
EXERCISE: We can see information about root objects again by using the ObjectSpace mod-
ule. After require "objspace", run ObjectSpace.reachable_objects_from_root. It’ll return
a hash where the keys are String representations of categories of objects, and the values are
arrays containing all of the objects reachable from roots within those categories. The cate-
gories are ["vm", "machine_context", "global_list", "global_tbl"].
Back to marking. With all root slots grey, and all other slots white, we then get to the crux of
the algorithm:

while (!grey_slots.empty?)
current_slot = grey_slots.pop
grey_slots += current_slot.referenced_slots
black_slots << current_slot
end

Ruby iterates over all grey slots, coloring them black, and coloring the slots that their RValues
reference grey. The algorithm continues until there are no grey slots left. At this point, Ruby
has traced all accessible RValues. So any black slots contain RValues which were reachable
by the root RValues. Any white slots contain RValues which were not reachable from the root
RValues. Concretely, this means that our programs no longer have references to these white
RValues. They are completely inaccessible. The white RValues can therefore be swept away;
their slots can be reused by other RValues!
It turns out that when I’m preparing for a backpacking trip and lay out all of my gear, I do a
similar thing. I’ll gather initial objects I absolutely know I need first, and then follow them
through to find everything else I need. For instance, if I’m going to cook ramen noodles one
night for dinner on the trail, I’ll need a stove and a small pot. For the stove to work, I’ll also
need a gas canister and a lighter. In order for me to hold the pot without burning myself, I’ll
need a small bandana. I go object by object determining exactly what I need for the next one
to work. I can leave anything that I haven’t marked through this process at home.
Here’s what the algorithm is doing in images:

10
 Tri-Color Mark and Sweep

References

There is one detail which needs further explanation here: how does an RValue know which
other RValues it references? We learned in an earlier exercise that, using ObjectSpace.dump
we can see a list of the references from an object. But how does Ruby actually know this list?
It depends on the type of object. Ruby built-ins (Arrays, Hashes, etc) have details about how
to trace their references within the garbage collector code itself. For example, to find all ref-
erences from an array RValue, the garbage collector iterates over each element in the array
and finds its references. For a hash, it will do this for both the keys and the values. This all
happens in the garbage collector’s mark_children method.

11
 Tri-Color Mark and Sweep

We mentioned earlier that Ruby is mostly written in C. Ruby has APIs in C which allow develop-
ers to also write Ruby gems, or other code, in C itself. These are called C extensions. Examples
of gems which use C extensions are bcrypt and puma. When custom objects are defined by
C extensions, the C extension itself is responsible for marking all referenced objects. Forget-
ting to do that will have catastrophic results, potentially even leading to accessible values
accidentally being garbage collected. Peter Zhu is writing a great series about C extensions:
A Rubyist’s Walk Along the C-Side. It is definitely worth a read if you’re interested in learning
more here.
In the hiking world, if I’m testing out a new piece of gear that I’m unfamiliar with, I’ll rely on an
instruction manual to tell me exactly what I need. For instance: a new water filtration system
might have a few different parts, and the instruction manual tells me which parts I actually
need to carry with me and which parts are extra packaging, or cleaning supplies I can leave
at home. If I don’t read this instruction manual carefully, and say, leave a part of the filtration
system at home, I might (not speaking from experience or anything) be in a position where I’m
unable to filter my water. Similarly, when developers write C extensions with details of new
Ruby types, these C extensions must mark referenced objects so that Ruby’s garbage collector
can continue to run smoothly.
Now that we understand how we find all accessible objects, we need to learn how to sweep
all inaccessible objects.

Sweeping

After learning about the mechanisms behind marking Ruby objects (and their various refer-
ences) for garbage collection, we can turn our attention to the second part of the algorithm:
sweeping. At this point, we have two sets of slots: black slots and white slots. Internally,
these are represented as a marked bitmap - remember bitmaps, from earlier? Every page on
the Ruby Heap has its own marked bitmap with one bit per slot. Bits can take the values of 0
or 1. A 1 bit means the slot is accessible, or black in our Tri-Color scheme. A 0 bit means that
the slot is no longer accessible, or white in our Tri-Color scheme.
In addition to holding this marked bitmap, each page also has a freelist which is a linked list
of slots on that page which do not have accessible objects. The garbage collector iterates over
all pages, finding all slots which are not marked. Where applicable, the garbage collector then
adds the unmarked slots to each page’s freelist. If the RValues which were occupying these
slots are also taking up space in the operating system heap (because they needed more space
than the 40 bytes allowed), it also frees this OS memory.
Once pages have been swept, there might be pages which are now completely unallocated
and have no slots which contain RValues. These pages are called Tomb Pages. Tomb Pages
can have their memory returned to the operating system heap. This can be helpful for mem-
ory management. It means that sweeping can result in freeing memory, or diminishing the
overall size of the Ruby Heap.

12
 Tri-Color Mark and Sweep

I was recently backpacking for only one warm summer night, and so didn’t need any extra
layers. I have a little stuff sack that I usually use for all of my extra clothing, but it was empty
for this trip (a Tomb Page, if you will). Instead of carrying the extra empty stuff sack, I simply
left it at home.
Conversely, any pages with at least one occupied slot are called Eden Pages. The sweeping
phase might reduce the number of occupied slots in an Eden Page. The garbage collector will
use the freelists from Eden Pages for future object allocations. If we instantiate an object, the
garbage collector will look for one of these free slots in an Eden Page and place the RValue
representing our object into that Eden Page.
Okay, so I didn’t have any extra layers with me on that recent short backpacking trip, but I did
still have a spare pair of socks. It seemed silly to bring along my whole extra clothing stuff
sack just for one pair of socks. Instead, I put my socks in the stuff sack with my sunscreen and
bug spray, which had a little extra space. In this analogy, my sunscreen stuff sack (Eden Page)
had some extra space (free slots in the free list) and so I was able to utilize those instead of
bringing a whole new stuff sack (allocating an extra page).

There is one more part of the sweeping phase, in some cases. As of Ruby 3, if auto-compaction
is enabled, compaction will actually happen as part of the sweeping phase. We’ll learn more
about this in the compaction section.

13
Generational Garbage Collection

The Tri-Color Mark and Sweep algorithm we just learned about is the base algorithm Ruby’s
GC uses. As new Ruby versions have been released over the years, some of them have added
different strategies onto this algorithm. In 2013, Ruby 2.1 introduced generational garbage
collection.
Generational garbage collection is predicated on the Weak Generational Hypothesis: most
objects die young. In other words, most objects will not have active references to them, and
so are available for collection soon after creation. The weak generational hypothesis also says
that those objects which don’t die young tend to live for a long time. If they aren’t pretty
immediately available for collection, they likely won’t be available for collection for a while.
We can look at a Rails example of the Weak Generational Hypothesis. To generate a webpage
for a client request, a Rails application will create many new Ruby objects. Once the page
has been returned to the client, all of these objects are no longer needed and their space in
memory can be reclaimed. However, there are some objects which need to live between all
requests, like controllers, configuration data, user session data, and so on. These objects will
live for a long, long time.
We can also look into my backpack to see another example of the Weak Generational Hypoth-
esis. I love my tent. It has been with me through thick and thin; through snowstorms, rain-
storms, and hot, humid nights. It is definitely what one would call ”old.” Inevitably, at some
point in the far future, my tent will break down and I’ll have to get a new one. I hope this date
is decades away. Contrastingly, many newer items in my backpack are constantly being re-
placed. I’ll use up a new canister of gas or bottle of bug spray on a trip, and then never need
it again.

Major and Minor GCs

Generational GC takes advantage of the Weak Generational Hypothesis. It concentrates more

frequent garbage collection efforts on young, newer objects.
Ruby actually has two different types of garbage collection: minor GCs and major GCs. Minor
GCs happen more frequently, and mostly look at young objects. (There’s an edge case here
which we’ll cover in a bit.) Major GCs happen less frequently and look at all objects, young and
old. Minor GCs are faster than major GCs because they’re looking through fewer objects.

14
 Generational Garbage Collection

”Minor GCs” happen during backpacking trips for me. Sometimes as I’m backpacking, I’ll
come to areas where a road crosses the trail and there is a garbage can. I gather any gra-
nola bar wrappers and throw them out. In this analogy, these granola bar wrappers are ”new
objects” whereas something like hiking shoes are ”old objects”. Hiking shoes can get a little
ripped and worn during a trip, but I would absolutely never consider throwing them out in
one of these smaller ”minor” garbage cans. However, between trips, I’ll do a thorough, ”ma-
jor GC.” I’ll look at every piece of my gear and determine which I don’t need anymore.

Old and Young Objects

How does Ruby determine which generation an object belongs to – whether an object is old
or young? When objects are created, they are young. Any object which has survived three
garbage collections (major or minor) is classified as old.
EXERCISE:
We can see this with code snippets. We’ll use ObjectSpace.dump again, this time looking at
the "flags" key, which itself is a hash giving us an "old" => true if the object is old, and
giving us no "old" key if the object is young. (Experiment with this yourself!)

require "json"
require "objspace"

def old?(obj)
!!JSON.parse(ObjectSpace.dump(obj))["flags"]["old"]
end

We can use this old? method to figure out how many GCs it takes Ruby to mark an object as
old:

# We disable any automatic GC runs to ensure that GC is

# only happening when we call it manually
GC.disable

# full_mark: true is a major gc

# full_mark: false is a minor gc
def count_gc_until_old(full_mark)
gc_count = 0
obj = Object.new

while !old?(obj)
GC.start(full_mark: full_mark)
gc_count += 1

15
 Generational Garbage Collection

end

gc_count
end

puts count_gc_until_old(true) # Major GCs

# => 3

puts count_gc_until_old(false) # Minor GCs

# => 3

We’ve confirmed that running 3 garbage collections will age a young object into an old one,
regardless of whether those three GCs are major or minor!

What triggers minor vs major GCs?

Minor GCs are triggered when the Ruby Heap does not have any free slots left. It runs a minor
garbage collection in an attempt to find new free slots into which it can allocate objects. We
can also manually trigger a minor GC by running GC.start(full_mark: false).
Major GCs can be triggered in a few ways. If there are still no free slots after a minor GC, a
major GC will happen. Major GCs are also triggered if we cross the internal limit of old objects
that can be stored. This limit increases as the size of the Ruby Heap increases, and we can see
it by looking at GC.stat[:old_objects_limit]. We’ll learn more about GC.stat below. For a
quick example:

GC.stat[:old_objects_limit]
# => 67450

objs = 100_000.times.map { Object.new }

GC.stat[:old_objects_limit]
# => 187494

We can see that if we allocate 100_000 objects, our old_objects_limit will increase, in this
case from 67450 objects to 187494 objects. (The numeric values you’ll see when running this
are expected to be slightly different, as our GCs won’t happen at exactly the same times and
frequencies.)
When backpacking, as I mentioned earlier, ”minor GCs” can be triggered just by seeing a
garbage can. They can also be triggered when I need space for new objects. For instance,
while on longer backpacking trips, every few days I need to hitchhike to a grocery store off
the trail to replenish my food supply. Before I do one of these grocery store runs, I do a quick

16
 Generational Garbage Collection

scan of any trash I might have accumulated to make room for the new food. This is the exact
same as Ruby GC. If new objects are coming into the Ruby Heap, and there’s not room, Ruby
will do a minor GC to try clear enough space. However, I always look through all of my stuff in
between trips or on rest days. These ”major GCs” are where I take everything out of my bag
and re-evaluate even my older gear.
We can manually trigger a major GC by running GC.start(full_mark: true), or just GC.start.
Compaction, which we’ll learn more about later, can also trigger a major GC.

Write barriers

You might have noticed a problem in the algorithm above with old and new objects. This
works if new objects reference old objects, but what about the other way around? What if we
have some RValue in an old generation and we create a new RValue referenced from that old
RValue?

As this diagram illustrates, we’ll run into a problem where the garbage collector is marking
all new objects in a minor GC, doesn’t see any references to this new object (because the

17
 Generational Garbage Collection

reference is from an old object) and so collects it even though it is referenced by an RValue
which is reachable from the root. Uh-oh.
In my backpacking example, this would mean I would accumulate something new (say, spare
batteries) for something old (say, my GPS system). If I was looking only at the new objects to
try find stuff to get rid of, I’d see the batteries, without realizing that the GPS system needed
them.
Fear not, the authors of Ruby’s garbage collection algorithm implemented a solution to this
problem using write barriers. As the name suggests, write barriers are pieces of code that are
executed whenever an object is written to. Ruby uses write barriers to indicate when there’s
a new reference from an old object. The garbage collector puts these old objects which have
references to new objects in a ”remembered set.” Thankfully, my GPS system would go into
my remembered set.
This leaves us with the final step in minor GCs, and the edge case we referenced earlier. Minor
GCs look at the remembered set as well as new objects. This means my GPS system would be
safe!

We are therefore guaranteed that all objects which are not young and not in the remembered
set will not have any young references. This means the problem we noticed earlier in this

18
 Generational Garbage Collection

section has disappeared completely, and we can proceed knowing our generational garbage
collector looks at all objects which it needs to.
Most of us won’t have to worry about this, but it is also worth noting for any developers who
work directly on Ruby source code, that within Ruby source code write barriers are not gener-
ated automatically and instead must be manually added. Forgetting to add these write bar-
riers can have unintended consequences, sometimes even causing Ruby programs to crash.
If you’re interested, Alan Wu wrote a blog post about a missing write barrier (now fixed) on
Hash#transform_values! which elaborates on the necessity of write barriers.

19
Incremental Garbage Collection

When we learned about the Tri-Color Mark and Sweep algorithm, we didn’t actually discuss
why it’s Tri-Color. Why not only two colors, one for marked and one for unmarked?
Interestingly enough, before Ruby 2.2, Ruby was using a standard Mark and Sweep algorithm,
not a Tri-Color one. The mark phase was simple: Ruby’s GC traversed all RValues, starting at
the root, and marked any RValue it encountered. However, Ruby 2.2 introduced incremental
GC, another strategy to make garbage collection more efficient.

Stop-the-world

Ruby uses what’s called a stop-the-world garbage collector. The world is really just the ex-
ecution of our program. Each time Ruby’s GC runs, the execution of our program is paused
completely. This is okay for most minor GCs, but could be cumbersome for major GCs. It
would be especially cumbersome if these pauses happen at inopportune times.
Imagine a world where a user is loading a webpage that usually takes a hundred milliseconds
– but, it just so happens that a big major GC runs at the time of their page load.

Now seemingly out of nowhere, their page load is paused for the garbage collector to run
and their page takes way longer to run than normal with no explanation to them. Clearly this
would not be desired behavior.

20
 Incremental Garbage Collection

The same applies for backpacking. If I’m climbing up a tough incline, and suddenly stop to
look through all my gear, I would lose all my momentum. I would also be a hazard to anyone
trying to pass with my stuff scattered on the trail, but that seems less relevant to garbage
collection.

Incremental Pauses

The three colors (Tri-Color) allow us to pause garbage collection. Specifically, we can thank
the grey color for this ability. If we look at a snapshot of RValues and their references mid-
garbage collection like this, we can clearly see what the garbage collector has to do next:

We know it can pick any one of the grey RValues and continue to follow its algorithm of finding
references, marking them grey, and then marking the initial RValue black. We know exactly
which RValues the garbage collector has already looked at, and which ones it still must inspect.
The grey RValues store our work in progress.
Contrast this with the idea of a plain old Mark and Sweep algorithm. If we paused a non-Tri-
Color Mark and Sweep in the middle of its execution of the mark phase, we wouldn’t know
what should happen next. It wouldn’t be clear which part of the traversal we were on. Even
if we kept a reference to the current RValue we were looking at, it wouldn’t be clear which
other black RValues had references which were already traversed, and which still needed to
be traversed.
If we interrupted a non-Tri-Color Mark and Sweep in the middle of its execution, we would
have to start all over. And here is the real genius of the Tri-Color Mark and Sweep algorithm!

21
 Incremental Garbage Collection

Sure, it introduces slightly more complexity than its predecessor. But in return it allows
garbage collection to pause and not have to begin all over again.

This means that we can incrementally run the garbage collector. Or, put another way, it means
we can run a little bit of our mark phase at a time. Instead of risking a long stop-the-world
pause at an inopportune time, incremental GC allows us to do a little bit of marking inter-
leaved with a little bit of program execution.
Okay, I’ll admit it: I don’t use a tri-color scheme to figure out what stuff I can remove from
my backpack. But I definitely do it incrementally. See the note above, if I did it all at once at
inopportune times, I’d lose momentum and be a hazard to anyone around me.

Write Barriers, again!

There is one crucial detail we haven’t accounted for – yet. What if references change mid-
way through this incremental mark phase, during program execution? Critically, what if we
do some marking, let the program run, and an RValue we had already marked black now ref-
erences a new white RValue. The garbage collector needs to know about this! Otherwise it
would think it had already marked all references from the black RValue, never see this new
white RValue, and sweep it away even though we have a live reference to it.

22
 Incremental Garbage Collection

Write barriers to the rescue! As we learned with generational GC, write barriers allow us to exe-
cute pieces of code whenever we write to an object. Can you see how this solves our problem?
The garbage collector can use write barriers to its advantage in this case.
Whenever a black RValue’s references change while the incremental marking is on one of its
pauses, the garbage collector can use a write barrier to re-color the black RValue grey. This
will force the garbage collector to again look at all of the RValues that the now-grey RValue is
referencing. Critically, this will catch the case where the execution of our program interleaved
with GC introduces a white RValue referenced by a black RValue.

Write Barrier Unprotected Objects

Some objects are not protected by write barriers. This may seem like a flaw in our above
strategy. But, it’s actually not a huge problem at all. The garbage collector simply looks at all
write barrier unprotected objects again at the very end of its incremental mark.
EXERCISE: We can again use our handy ObjectSpace.dump to see an object’s write barrier pro-
tected status. This can be interesting to play around with:

require "json"
require "objspace"

def write_barrier_protected?(obj)
JSON.parse(ObjectSpace.dump(obj))["flags"]["wb_protected"]

23
 Incremental Garbage Collection

end

write_barrier_protected?("some string")
# => true

Additional work

One other point worth noting about the write barrier solution is that it introduces slightly
more work for the garbage collector. In the non-Tri-Color Mark and Sweep algorithm, the
garbage collector only had to mark and trace references of each RValue once. Now, it has to
repeat the mark step for some RValues. This will add to the total time spent garbage collecting:
the garbage collector is doing more work.
The garbage collector is now also never stopping the execution of the program for too long.
The benefits outweigh the costs. It is more effective for the program overall to have these
incremental marks interleaved with program execution even if this increases the total time
spent marking.

24
Compaction
We’ve now learned about two strategies which improved on the initial Mark and Sweep algo-
rithm: generational GC and incremental GC. There is also a more recently released strategy to
improve Ruby’s GC: compaction. Part of it was released in Ruby 2.7 in 2019, and another part
was released in Ruby 3.0 in 2020.

Fragmentation

Compaction only makes sense in the context of fragmentation. Fragmentation is the term we
use to describe memory when it’s allocated non-contiguously. This means that there are gaps
in memory between where there is meaningful information, and where there isn’t meaningful
information.
More concretely, in the Ruby Heap, fragmentation is when there are free, unallocated slots
(without RValues) in between allocated slots (with RValues). This diagram shows us an ex-
treme example of fragmentation:

Fragmentation in our backpacking metaphor is when I have many pockets, or stuff sacks, with
only a few items in each one of them.

25
 Compaction

Why compact?

Compaction is the solution to fragmentation. But, what’s wrong with fragmentation? What is
compaction solving?
The most obvious problem is that a fragmented heap will take up more overall memory than
a compacted heap. If we look again at our extreme example from above, all of those RValues
could have fit into just one page, instead of five. As we’ve discussed, memory can be a limited
resource, so it’s beneficial to utilize it efficiently. If my backpack is fragmented, it’s likely I’ll
be using extra pockets which I could instead detach from the pack completely.

There are other reasons to compact, too.

CPU Cache Hits

The operating system usually loads small chunks of memory into a cache which is quicker to
access than the rest of its memory. It will take less time to access an RValue already in the
cache than it will to access an RValue not in the cache.
It benefits us to have as many RValues as possible in each chunk of memory that the OS might
load into the cache. If the Ruby Heap is fragmented, however, then for each chunk of pages
that the OS loads into its cache, there are potentially many free slots which aren’t giving us
more efficient access to any RValue. But if we compact the Heap, then each chunk in the cache
will be packed with RValues.

26
 Compaction

I have pockets on the hip straps of my backpack. I can access whatever is in these pockets
incredibly easily, so at the beginning of every day, I fill them with stuff I might need for the
day: things like granola bars or a map. If these hip pockets aren’t as full as they could be, it’s
likely that I’d need to take off my backpack, and unpack it to find things that I need while I’m
hiking. Obviously, this is slow and inefficient.

Copy-on-Write

Another motivation for compaction is to increase the efficiency of copy-on-write. In Ruby,

when processes are forked, a child process’s memory points to the parent process’s mem-
ory.
However, if the child process wants to write into memory, it can no longer point to the parent
process’s memory. Instead, the memory where the child process wants to write is copied
into the child process’s memory itself. It turns out, though, that the CPU copies memory in
chunks which are the sizes of operating system pages. OS pages are analogous to Ruby Heap
pages, except much bigger than the small bit of memory that a child process may want to
write into.
In a fragmented heap, this might mean that most of the memory copied down is actually al-
ready allocated, or already contains RValues. In these cases, the OS needs to keep copying
more memory each time it wants to write into memory.
In a compacted heap, most of the memory copied down in this chunk would be unallocated,
free slots. This means that if the child process continues to write to memory, the OS won’t
need to keep copying over more chunks.
As an interesting aside, information about an RValue’s age is stored in a two-bit header on
the RValue itself. Ruby can count how many garbage collections an RValue has survived by
increasing the value of these bits. The maximum value that two bits can take is three (11).
This is exactly how many garbage collections it takes to convert an object from young to old.
After surviving three garbage collections, the age bits will never change.
Why is this relevant to Copy-on-Write? Since the age bits are header information on the
RValues themselves, changing them will require writing into memory. Critically, if they are
changed after a fork, the child process will need to copy down an entire memory chunk.
Koichi Sasada implemented the nakayoshi_fork gem, which solves this problem by running
four garbage collections before forks, to force all objects to become old.
Returning to our backpacking example, let’s say I was backpacking with a friend and they
were going to use some of my stuff sacks to efficiently store their own belongings too. If I kept
giving them half-filled stuff sacks, they’d keep needing more. If I gave them an empty stuff
sack though, they could fill that up completely before needing another one. This is the same
concept: we’d rather copy over mostly empty memory than keep copying over partially filled
memory.

27
 Compaction

Efficient Memory Usage

This last motive for compaction isn’t actively relevant to Ruby quite yet, but previews a section
about what’s coming in Ruby’s GC.
Another reason often cited for compaction is efficient memory usage. As we know by now,
each RValue is exactly 40 bytes. In some memory management systems in other programming
languages, objects aren’t all the exact same size.
In these systems, we can imagine that there could be cases where the total memory available
is more than enough for a new object, but it’s been structured in a way that simply doesn’t
have room.

If we compact this fragmented memory space, we would have room:

This is often the primary reason cited for compaction. Except like I noted, it doesn’t yet apply
to Ruby GC as of Ruby 3.0 because each Rvalue is exactly the same size.

28
 Compaction

Two Finger Compaction

Anyway, enough about why Ruby introduced compaction. Let’s discuss how Ruby compaction
works. The algorithm Ruby uses for compaction is called a two-finger compaction algorithm. I
know, I know, tri-color, two-finger... I’m also excited to see which one-prefixed strategy Ruby’s
GC employs in the future!
This algorithm was actually first written about in ”The Programming Language LISP: Its Op-
eration and Applications” by Edmund C. Berkeley and Daniel G. Bobrow in 1964. It’s quite
incredible that this is the algorithm Ruby uses today (57 years later!), so I wanted to share
some of the original text they wrote:

Two pointers are set, one to the top of free storage and one to the bottom. The top
pointer scans words, advancing downward, looking for one not marked. When
one is found, the bottom pointer scans words, advancing upward, looking for a
marked word. When one is found, it is moved into the location identified by the
other pointer. A pointer is left at the location the word was moved from, pointed
to whether it was moved to. The top pointer is then advanced as before. The
process terminates when the two pointers meet.

Okay, now to decipher this text. This snippet is actually all discussing the first part of two-
finger compaction, which is moving objects.

Move Objects

The two pointers are the two ”fingers” in the algorithm. One starts at the beginning of the
heap and the other at the end. The gist of the strategy is that these two pointers are going
to converge, incrementing from the beginning and decrementing from the end, filling in free
slots from the beginning with RValues in slots from the end.
We can write this as a small Ruby snippet:

top = 0
bottom = heap.size - 1

while top < bottom

if heap[top].empty?
unless heap[bottom].empty?
swap(heap[top], heap[bottom])
end
end

top += 1 while !heap[top].empty?

29
 Compaction

bottom -= 1 while heap[bottom].empty?

end

Update references

As we know, RValues can reference other RValues. We’ll use an array containing a String as an
example again. If, while compaction is moving objects around, it moves the String, it needs
to ensure that the array knows about this new location for the String. In place of the String’s
RValue that has been moved, Ruby’s GC will leave a forwarding address. The forwarding ad-
dress is the new location of the String’s RValue.
This brings us to our second phase of the Two-Finger Compaction algorithm: updating refer-
ences. Once Ruby’s GC has moved RValues and left forwarding addresses, it needs to actually
update the references and clear the forwarding addresses. If it didn’t update the references,
then those forwarding addresses would need to stay in perpetuity, making the newly empty
slots useless.
This process is fairly straightforward. Ruby’s GC iterates over every slot in the Heap. If the slot
is empty, it moves on. If the slot is occupied by an RValue, it looks at any references from that
RValue. For each reference, it looks at what is in memory for the current address it has, and if
there’s a forwarding address, it will update the reference to point to the forwarding address.

Caveat: C extensions

There is one big caveat in the reference updating step. It assumes that Ruby’s GC knows how
to read an RValue’s references. For built-in Ruby objects, this is fairly straightforward. But,
as we learned when discussing references, Ruby also allows objects to be defined through C
extensions.
Some of these C extensions indicate to Ruby how they store their references and so can be
updated. But others don’t. In these cases, the RValues can’t be moved in compaction. Instead,
they are ”pinned” in place and not moved. This is a small percentage of objects, so it doesn’t
drastically interfere with the goals defined earlier.

Current state of compaction

It’s important to also note that as of Ruby 3.0, compaction is still under development and ac-
tually currently degrades performance on most apps. It’s therefore not automatically turned
on. It is still possible to turn it on manually using GC.auto_compact=(true), but as the docu-
mentation notes, ”Enabling compaction will degrade performance on major collections.”

30
Object IDs

In Ruby, the changing nature of object_ids through different versions can tell us another
story of compaction. We’ll take a quick detour from GC strategies to examine the implications
of these strategies on object_ids.
Every Ruby object gives us access to an object_id as a unique identifier for a specific instance
of an object. If we read the Ruby docs, we can see that Object#object_id guarantees unique-
ness and consistency of object_ids across objects. Explicitly, the docs say, ”The same num-
ber will be returned on all calls to object_id for a given object, and no two active objects will
share an id.”

Special Objects

In Ruby there are certain types of objects which are special cases of Object#object_id. Exam-
ples of these are true, false, nil and Integers. We’re not going to discuss Object#object_id
calls for these special cases in this section because they’re not relevant. But... they are inter-
esting.
EXERCISE: If you’re curious, look for the pattern in Object#object_id on Integers.

Before Ruby 2.7

Back on topic. Prior to Ruby 2.7, Object#object_id was derived from an object’s address in
memory. This seems simple enough - each object has a unique memory address referring
to the slot that only it occupies - Ruby can use this memory address to derive a unique ob-
ject_id.

EXERCISE: In Ruby versions below 2.7, object_id is derived by shifting the memory address
to the right by one bit. We can actually see this! In an IRB console in Ruby 2.6.3, we can run
the following code:

obj = Object.new
# => #<Object:0x00007fb8240a8ca8>

address = obj.inspect.match(/0x([0-9a-f]+)/)[1]
# => "00007fb8240a8ca8"

31
 Object IDs

# The address is in hexadecimal so we use

# String#to_i(16) to convert it to decimal
obj.object_id == address.to_i(16) >> 1
# => true

And we’ve confirmed that shifting the memory address to the right by one bit gives us the
object_id.

Ruby 2.7 Onwards

Ruby 2.7 introduced a big change to Object#object_id. Why? Compaction was introduced in
Ruby 2.7.
As we know from the compaction section, compaction can change the memory addresses of
objects. So if we were to keep deriving Object#object_id from memory addresses, we would
be stuck. What would happen when an object moved, and a new one occupied its former
address? And, what would happen to the object_id of the moved object? How would Ruby
keep the consistency guarantee of an object_id?
Instead, from Ruby 2.7 onwards, each object is only assigned an object_id at the moment
that Object#object_id is called instead of at creation. Ruby simply increments the value of
the last assigned object_id whenever Object#object_id is called on a new object. This is
how Ruby ensures that each object_id will still be unique.
Ruby also keeps a map of memory addresses to object_ids. After the Ruby Heap is com-
pacted, this map is updated based on any new memory locations. So instead of having ob-
ject_ids tied to addresses in memory, from Ruby 2.7 onwards object_ids are provided by a
monotonically increasing counter.
EXERCISE: We can again see this in action! If we run a little Ruby snippet in an IRB console, we
can see that on each Object#object_id call, we get an object_id which increases by 20:

3.times.map { Object.new.object_id }
# => [260, 280, 300]

In the same console, we can then create a new object without calling Object#object_id on
it:

obj = Object.new
# => #<Object:0x00007fb5b9090d00>

We’ll then see that our next call to Object#object_id will get the next object_id in the se-
quence from above: 300 + 20 == 320:

32
 Object IDs

Object.new.object_id
# => 320

If we now call Object#object_id on obj (our previously created object), we’ll get the next
number in the sequence, 340, even though it was initialized before the object with object_id
== 320.

obj.object_id
# => 340

Pretty neat, huh?

Compaction and object_ids

We can also look at the effect of compaction on object_ids. (Hint: we should see none!) Com-
pacting a heap should not interfere with the object_ids since Ruby guarantees us that they
will be unique and specific to a single object.
To test this, we’re going to create an array with many objects, and then one extra object af-
terwards. We’ll then set the array to nil, clearing out the many slots occupied by the array’s
elements in the heap. If we compact the heap, we should see the specific object change ad-
dress due to all the space in memory which is vacated by setting the array to nil. (We can see
the address using Object#inspect.) But, what we’re really looking for here is that the object
will keep its initial object_id.
EXERCISE: Enough words, I’ll let code clarify (using Ruby 3.0):

array = 100_000.times.map { Object.new }

obj = Object.new
# => #<Object:0x00007f9863aa81d0>
obj.object_id
# => 260

array = nil
GC.compact

# New memory address (7f9863aa81d0 != 7f9864049e40)

obj.inspect
# => "#<Object:0x00007f9864049e40>"

# Same object_id (260 == 260)

33
 Object IDs

obj.object_id
# => 260

Phew, this change to how Object#object_id works in Ruby 2.7+ still gives us the same guar-
antees on object_ids, even if the objects themselves can change memory addresses.

34
GC.stat

We’ve covered many parts of Ruby garbage collection strategies so far, including generational
GC, incremental GC, and compaction. What we haven’t yet described in detail is how to see
information Ruby exposes about what the garbage collector has already done. If you’ve ever
run GC.stat before, you’ve likely seen output that looks something like this:

{
:count=>3025,
:heap_allocated_pages=>347,
:heap_sorted_length=>4239,
:heap_allocatable_pages=>1,
:heap_available_slots=>141784,
:heap_live_slots=>71343,
:heap_free_slots=>70441,
:heap_final_slots=>0,
:heap_marked_slots=>49297,
:heap_eden_pages=>346,
:heap_tomb_pages=>1,
:total_allocated_pages=>4239,
:total_freed_pages=>3892,
:total_allocated_objects=>153587485,
:total_freed_objects=>153516142,
:malloc_increase_bytes=>191488,
:malloc_increase_bytes_limit=>16777216,
:minor_gc_count=>2993,
:major_gc_count=>32,
:compact_count=>11,
:read_barrier_faults=>0,
:total_moved_objects=>11025,
:remembered_wb_unprotected_objects=>216,
:remembered_wb_unprotected_objects_limit=>432,
:old_objects=>49065,
:old_objects_limit=>98130,
:oldmalloc_increase_bytes=>191488,
:oldmalloc_increase_bytes_limit=>18384822
}

35
 GC.stat

Ruby exposes so much information about what its garbage collector has done through
GC.stat. Reading over all of the key names above, we’ll see that many of these terms will be
familiar now! If you’re running Ruby in production applications, it can be helpful to periodi-
cally log the output of GC.stat. This can help establish baseline garbage collection behavior
for your application, and can be incredibly useful to have if changes to the application affect
garbage collection.
Nate Berkopec and I recently paired on a PR to add more documentation to GC.stat, which
will appear in the next Ruby release. In the meantime, I wanted to highlight a few key / value
pairs from GC.stat which can provide helpful insight into what work the garbage collector has
done:

:heap_allocated_pages

The number of pages currently in the Ruby Heap. GC.stat[:heap_available_slots].to_f /

GC.stat[:heap_allocated_pages] will be between 408 and 409. And GC.stat[:heap_allocated_pages]
== GC.stat[:heap_eden_pages] + GC.stat[:heap_tomb_pages].

:heap_available_slots

The total number of slots in the Ruby Heap. We can watch this number grow if we create (and
keep a way to reference) many new objects. Try something like objects = 100_000.times.map
{ Object.new } in a console, and watch this number increase as Ruby asks the OS for more
pages (and slots!) to store the RValues for these new objects.

:heap_live_slots

The number of slots in the heap which store RValues that we can access. If you’re consistently
logging statistics about garbage collection and notice that after certain code changes, this
value spikes significantly higher than usual, it’s likely you’re keeping references to many more
objects than you previously were. It can be worth double checking whether it’s necessary to
keep these references around.

:heap_free_slots

The number of slots in the heap which don’t have RValues we can access. If it’s extremely high
(more than a few hundred thousand), this can be indicative of memory bloat. It means it’s
likely that something allocated a huge number of objects and then didn’t need them, bloating
the memory that a program is consuming. Conversely, if it’s extremely low, it’s likely that the
GC will run soon to try find some more slots Ruby can use before requesting new memory
from the OS.

36
 GC.stat

:total_freed_pages

Number of freed pages over the lifespan of the application. GC.stat[:total_freed_pages] +

GC.stat[:heap_allocated_pages] == GC.stat[:total_allocated_pages]. The Ruby code-
base even has a test which verifies this property.

:remembered_wb_unprotected_objects

Number of objects which aren’t protected by write barriers. Remember from when we
discussed incremental GC that Ruby’s garbage collector re-examines all write barrier unpro-
tected objects at the end of marking since it can’t be certain that their references haven’t
changed throughout marking.

:remembered_wb_unprotected_objects_limit

When :remembered_wb_unprotected_objects crosses this limit, a major GC is triggered.

EXERCISE: Take a look yourself at the output of GC.stat (in a console or in a running appli-
cation) and try see what you can deduce about garbage collection, knowing what you now
know!

37
Future of Ruby GC

Programming, like backpacking, is a continuous march forward. The world of Ruby GC is not
standing still, and excitingly, there is currently in progress work to continue improving Ruby
garbage collection. Peter Zhu and Matt Valentine-House have given a few talks about the work
they’re doing on Variable Width Allocation.

Variable Width Allocation

As we know very well by now, Ruby’s memory is laid out in such a way that each RValue is the
exact same size – 40 bytes. In cases where the actual content of an object does not fit in the
40 byte RValue, Ruby holds a pointer to somewhere on the OS Heap which contains the rest
of the object.
When we first discussed the size of RValues, we talked about one of the benefits of fixed size
RValues: it’s straightforward for Ruby to find where one RValue ends and another starts, with-
out storing any additional information. We also discussed a drawback: if an object needs
more space than an RValue allows, some of it will be stored elsewhere. In the compaction
section, we discussed even more drawbacks to fixed size RValues, including poor cache local-
ity, inefficient copy on write behavior, and inefficient memory usage.
There is currently work in progress to implement variable width RValues within Ruby. Except
like we said, variable width RValues could make it more difficult for Ruby to easily scan pages
and determine where RValues start and end. Instead of implementing the solution in this way
and forcing each RValue to store information about its size, when Ruby introduces variable
width RValues, it will do so using a concept called size pools. There will be different size RVal-
ues, but fixed different sizes. For the initial implementation, these sizes will be 40 * (powers
of 2) bytes, so 40, 80, 160, 320 and so on. A page will only contain RValues of a specific
size. All pages of a certain size will together be referred to as a size pool. This is the best of
both worlds! It allows RValues to be different sizes, but still ensures that, for a given page,
it’s clear where RValues begin and end without requiring RValues themselves to store that
information.
The Variable Width Allocation project is actively ongoing and gives us insight into what the
future of Ruby GC might hold. My hope is that we’re now all well equipped to follow along as
Ruby garbage collection continues to develop.

38
Thank You

Before concluding, I want to give a tremendous thank you to Ufuk Kayserilioglu, Clara Mor-
geneyer and Danny for your thoughtful revisions of drafts of this ebook.

39
Additional Resources

If, after reading this ebook, you’re looking to learn more about Ruby garbage collection, I rec-
ommend the following talks:
A People’s History of the Ruby Garbage Collector by Nate Berkopec, FOSDEM 2017
Analyzing and Reducing Ruby Memory Usage by Aaron Patterson, GORUCO 2018
Automatic GC Compaction in MRI by Aaron Patterson, RubyConf 2020
Building a Compacting GC for MRI by Aaron Patterson, RubyConf 2017
Compacting GC in Ruby 2.7 by Aaron Patterson, Pivorak 2019
Compacting Heaps in Ruby 2.7 by Aaron Patterson, RubyConf 2019
Halve Your Memory Usage with these 12 Weird Tricks by Nate Berokopec, RubyConf 2016
Incremental GC for Ruby Interpreter by Koichi Sasada, RubyConf 2014
Methods of Memory Management in MRI by Aaron Patterson, RubyConf 2016
Optimizing Ruby’s Memory Layout by Peter Zhu and Matt Valentine-House, Euruko 2021
Parallel Ruby: Managing the Memory Monster by Kevin Miller, RubyConf 2019
Pointers for Eliminating Heaps of Memory by Aaron Patterson, RubyConf 2018
The Bug that Forced Me to Understand Memory Compaction by Emily Giurleo, RubyConf 2020
The Hitchhiker’s Guide to Ruby GC by Eric Weinstein, RubyConf 2015
Trash Talk: A Garbage Collection Choose-Your-Own-Adventure by Colin Fulton, RubyConf
2018
Under the Hood of Ruby’s Generational Garbage Collector by Hemant Kumar, Rocky Mountain
Ruby 2014
Variable Width Allocation: Optimizing Ruby’s Memory Layout by Peter Zhu and Matt Valentine-
House, RubyKaigi 2021
What Causes Ruby Memory Bloat by Hongli Lai, Joyful Bikeshedding 2019

40
Glossary

• Compaction: The process of grouping allocated memory together.

• Eden Page: A page in the Ruby Heap which contains at least one slot with a live RValue.
(See Tomb Page).
• Fragmentation: When memory is allocated non-contiguously.
• Freelist: A linked list per Heap Page of slots without live RValues.
• Generational GC: A strategy to do more frequent GCs on newer objects.
• Heap: Ruby’s Object Space, or memory. Where Ruby stores all of its pages.
• Incremental GC: A strategy to interleave marking with program execution.
• Major GC: GC which iterates over all objects.
• Minor GC: GC which only iterates over young objects and objects in the remembered
set.
• Old Objects: Objects which have survived three GCs and are therefore only marked and
swept in major GCs.
• Page: How Ruby segments its Heap. Heaps contain pages. Pages are ~16KB and contain
at most 409 slots.
• RValue (40 bytes): Ruby’s C representation of objects. Either contains the value of the
object, or a pointer to where the object lives in the OS heap.
• Remembered Set: Old objects which have references to new objects.
• Slot (40 bytes): A space on a Page where an RValue is stored.
• Stop-the-world: Refers to pausing the execution of our program to run garbage collec-
tion.
• Tomb page: A page which contains only empty slots.
• Two-finger compaction: The algorithm Ruby uses for compaction.
• Weak Generational Hypothesis: Most objects die young, impetus for generational GC.
• Write Barriers: Callbacks which Ruby uses to determine when a new object references
an old object.
• Write Barrier Protected: When objects have write barriers and so the garbage collector
knows if references have changed after marking.
• Write Barrier Unprotected: When objects don’t have write barriers and so the garbage
collector is unaware if references have changed after marking.
• Young (new) Objects: Objects which have been around for fewer than three GCs.

41