Compacting Heaps in Ruby 2.7

by Aaron Patterson

In this video from RubyConf 2019, Aaron Patterson presents the topic of manual heap compaction in Ruby 2.7, discussing its integration with the garbage collector (GC). The presentation covers important concepts of Ruby's memory management, the necessity and benefits of heap compaction, and the algorithms behind this implementation. As Patterson explains, compaction is intended to rearrange allocated and free memory for improved efficiency, similar to defragmenting a hard drive. The motivations for implementing compaction are outlined as follows:

Efficient Memory Usage: By compacting memory, fragmentation issues are reduced, allowing for the allocation of new chunks of memory without the drawbacks of intertwined free and allocated spaces.
Improved CPU Cache Utilization: Keeping related data together optimizes data retrieval through the CPU cache, reducing the need for slower accesses to the RAM.
Copy-on-Write Friendliness: Compaction makes memory usage more effective by reducing overhead in processes like those used in web servers where memory sharing is crucial.

Patterson explains the two types of heaps managed in Ruby: the malloc heap and Ruby’s object heap, focusing primarily on how fragmentation occurs in the object heap. He presents a new algorithm – the 2-finger compaction algorithm, which uses two pointers that operate to rearrange memory, leading to more contiguous free spaces.

Challenges encountered include the complexity of updating references during the garbage collection process, particularly with the involvement of C extensions that require careful management to avoid crashes. Patterson emphasizes that about 80% of the implementation patch was devoted to reference updates, a task made challenging by the need for careful handling of object identifiers. Switching from memory address-based IDs to unique identifiers significantly minimized issues during compaction.

In conclusion, Patterson shares that the new heap compactor decreased heap size by approximately 10%, showcasing the efficiency improvements achieved through this process. Looking to the future, he hints at plans for automatic compaction in Ruby 3.0, aiming to enhance performance and memory efficiency further. With this insightful presentation, Patterson highlights the continuous advancement of Ruby through dedicated efforts from the Ruby Core team.

00:00:23.720 I'm really excited to be here today. I have a 40-minute Ignite-style presentation, which was the slide I planned to put up, but my tethering is too slow. So instead of putting the joke in slide form, just imagine that there was an Ignite slide here.

00:00:37.499 I'm wearing this hamburger hat today because I heard I needed to dress up in my formal attire. However, I’m going to take this off now because I feel it might be bad for the recording. I don't want my face to get all dark. So, hello everybody! Hamburger hat off, and let's get started!

00:00:58.289 Today, we're going to discuss a compacting garbage collector for MRI in Ruby 2.7. I apologize if this presentation feels a bit technical, as it is the end of the third day of the conference. My name is Aaron Patterson, but you can also call me Tenderlove.

00:01:20.600 If you don’t recognize me, let me introduce myself properly. I have two cats. One is named Gorbachev Puff-Puff Thunderhorse, the most famous of my cats. I have stickers of him—please come say hello if you want one! My other cat’s name is SeaTac Airport Facebook YouTube Instagram.

00:01:43.470 I have to admit, I'm extremely nervous in front of all of you today. I have been a committer on the Rails Core team since 2009, and my first commit was in 2009. I have been on the Ruby core team since 2011, and my very first commit to the Ruby core was ten years ago in October. So, this is my ten-year anniversary on the Ruby core team!

00:02:21.640 This presentation does not mean that I know everything about this topic, so please lower your expectations a little, then lower them just a bit more. I got onto the Ruby core team because I was able to crash Ruby many times, which led to segmentation faults and produced Ruby core files.

00:02:40.840 Today, I will be talking about compacting GC for MRI. However, before that, I want to touch on some controversial features in Ruby 2.7 that Matz mentioned. The first one is the pipeline operator, which, unfortunately, got removed. But I want to discuss it a little anyway. This operator caused quite a bit of controversy, as many people opposed this implementation.

00:03:10.330 In my own work, I proposed changing the pipeline operator into a smile operator because Ruby is designed for developer happiness, as Matz says. Unfortunately, that pull request was rejected.

00:03:40.840 Another feature I want to bring up is typed Ruby. Many of you seem excited about getting types integrated into Ruby, but I must admit, I thought we already had types in Ruby. I understand that some might copy and paste from Stack Overflow, but typically we do type things.

00:04:01.780 Now let’s discuss the real topic of today’s presentation: manual heap compaction for MRI. This work took me about three years to complete, and I must confess that I've never worked on a project so challenging in my life.

00:04:40.010 However, during this journey, I experienced a level of difficulty that I did not expect. I usually don't come up with many new ideas, but I finally had one for this work. Chris Seaton from the Truffle team called it a novel solution for not moving objects' references from C.

00:05:00.850 Before we dive into more technical aspects, I want to express my gratitude to a few people, specifically Cochise and Alison McMillan. When I first considered implementing compaction in MRI, I thought it was impossible. I shared my concerns with Cochise three years ago, and he encouraged me to rethink my stance.

00:05:44.659 Additionally, when I was feeling stalled and somewhat discouraged, Alison reached out to me and offered to work with me on this project. Every week, we would pair up, making the process more manageable for me.

00:06:10.300 Today, I will cover several key topics: Ruby's heap, the compaction algorithm, implementation details, results, and, if we have time, some debugging techniques. Not many people discuss debugging garbage collectors, but I think it’s an essential topic.

00:06:40.670 So, what is compaction? Compaction is essentially rearranging allocated and free memory. Imagine memory with allocated and free spaces interspersed. We can rearrange it so that all free spaces are contiguously combined, similar to defragmenting a hard drive, but this is done for data in memory instead.

00:07:15.650 You may wonder why we would want to do this. One benefit is efficient memory usage. For example, when you attempt to allocate a new chunk of memory, it might not fit due to fragmentation. However, if we compact the heap, we would have enough contiguous space to allocate the new chunk. This makes memory usage more efficient.

00:07:53.360 Another reason to compact is to ensure better utilization of CPU caches. When reading memory, data has to go through the CPU, and the CPU will read chunks of memory at a time. Reading from RAM is relatively slow, and the CPU has to access RAM, which involves cache.

00:08:40.080 Good locality refers to keeping related data close together, increasing the chance that all needed data will be processed from cache without needing to hop over to RAM. Another compelling reason for compaction is copy-on-write friendliness. For example, Unicorn, which we use as our web server at work, saves memory with a copy-on-write technique.

00:09:38.309 When a parent process creates child processes, unless modified, the memory stays linked to the parent process. However, when data is written to this shared memory, that connection gets broken, and the operating system copies the necessary data, potentially leading to memory waste by copying unnecessary data.

00:10:02.910 By eliminating fragmentation, the efficiency of memory allocation and overall memory usage is improved. Essentially, compaction solves the problem of fragmentation. In Ruby, we deal with two different kinds of heaps: the malloc heap and Ruby’s object heap.

00:10:52.030 Normally, we allocate memory from the system using malloc. However, when we allocate objects in Ruby using commands like `Object.new`, we’re drawing from Ruby’s object heap, which is where fragmentation can occur. Malloc can also lead to fragmentation.

00:11:39.700 To tackle this issue, we can use a new 2-finger compaction algorithm—a simple yet effective solution. The algorithm involves two pointers: a free pointer that moves to the right until it finds a free slot, and a scan pointer that moves to the left until it finds a filled slot.

00:12:08.000 When the free pointer finds a filled slot and the scan pointer finds a free slot, they swap the two locations and leave a forwarding address in the previous location of the moved object.

00:12:44.279 This process continues until the two pointers meet. Once they do, we update the references of each object in the heap, checking if they point to a forwarding address and modifying them accordingly. After all references are updated, we convert moved addresses into free slots and have successfully compacted the heap.

00:13:32.040 If I were to provide a code example, keep in mind that this is a Ruby conference, not a C conference. Here's how the algorithm would look: we loop until the two pointers meet, swapping locations and updating the references as necessary.

00:14:16.520 However, implementing the reference updating portion is where things become complicated as it involves determining how references are stored for various objects.

00:14:55.200 Efficiently updating these references across all Ruby data types can be a complex task, so it’s one of the more challenging aspects to implement. In fact, probably around 80% of the patch was just dedicated to reference updates.

00:15:43.660 Thus, this was the most complicated part of the patch; we must update references while also considering C extensions. This leads to needing a scheme that manages reference updates effectively.

00:16:08.790 In short, any C extension created needs to provide a marking function, which ensures that references are maintained during garbage collection. Every time something is marked, we make it impossible for it to be moved.

00:16:36.500 The idea is to have a separate bit table known as pin bits that mark which objects cannot be moved. When the scan pointer identifies a pinned object, it skips it during compaction. This way, the algorithm maintains references and prevents any moving of critical objects.

00:17:43.480 During the updating phase of references, if issues occur with C extensions, marking must be done leveraging the BGC mark function. Using this function ensures that the references will stay put and not lead to crashes.

00:18:01.320 I found this marking to be the most critical aspect of the project, as certain behaviors in libraries like the JSON parser needed to be considered to ensure stable reference management. We want to ensure pure Ruby code does not inadvertently cause crashes.

00:18:47.460 Object ID handling is another interesting issue to consider when implementing compaction. In older Ruby versions, the Object ID was based on the memory address of the object. However, this introduces complications when objects move during compaction.

00:19:10.740 So instead of replicating object IDs based on memory addresses, we shifted toward providing unique identifiers that do not rely on memory locations. This change drastically improved our management of object IDs and safety.

00:19:32.480 With the implementation of Ruby 2.7, Object IDs become monotonic; every call to Object ID ensures that it provides a unique, continuously increasing number, eliminating previous issues and enhancing reliability.

00:20:29.000 In terms of practical performance, implementing the compaction algorithm has resulted in reducing the heap size by around 10%, providing efficiency gains in memory allocation and utilization.

00:21:27.110 Looking ahead, my future plans for Ruby include addressing performance improvements in the compaction process, possibly transitioning to automatic compaction in Ruby 3.0. This means that users may not need to call for a manual compact at all.

00:22:14.190 The proposal includes adopting sliding compaction techniques for better memory locality and implementing variable width allocation to enhance memory efficiency.

00:23:00.960 In summary, I hope everyone recognizes the effort the Ruby Core team puts into improving Ruby. We are excited about the future of Ruby and what it has to offer! Thank you all for attending!

See Slides on speakerdeck.com