The evolution of garbage collection in Ruby. Rgenc

Koichi: Ruby's garbage collector threshold is 8 MB. Why use such a small value?

Matz: Because 20 years ago I was working on a machine with 10 MB of memory.

The issue of performance has always been one of the most discussed and relevant in the Ruby community. Whether it is a high load web site or a simple data backup script, the speed of work is their most important characteristic. At the same time, knowledge of the possibilities and limitations of the development language is often an important source of ideas for optimization, it allows you to "squeeze" the maximum out of the system.



The article focuses on one of the most strongly influencing parts of the Ruby language — the garbage collector, the algorithms for its work, and the improvements made to its work in the latest versions of the language. It will be about the most common, “canonical” implementation of Ruby - the so-called MRI or CRuby.

The basics

Garbage collection (GC) in programming languages ​​is a mechanism for automatic memory management without programmer intervention. GC is not a specific feature of Ruby - a similar mechanism is used in a significant part of modern development languages: Java, Python, C #, and others. MRI uses the classic Mark-and-Sweep garbage collection algorithm developed back in the 1960s.



Ruby uses heaps to allocate memory for new objects. The process of creating objects is interrupted when one of two conditions malloc_limit : the program's memory has run out or a certain allocation threshold has been reached - the so-called malloc_limit . At this point, MRI starts garbage collection, more precisely its first, “mark” phase.



The garbage collector goes through a tree of objects in the program's memory, starting with the “root” objects - these are global variables or internal structures of the language. Running over the links of objects on each other, the garbage collector marks objects as used. All data not marked as used in the mark-phase - “junk” and the memory they occupy can be freed. The release of memory from the "garbage" occurs in the second, sweep-phase GC.

')

Optimization of the garbage collector. Ruby 1.9.3 and 2.0

The classic Mark-and-Sweep algorithm has several disadvantages. First of all, these are significant pauses in the program, during which the execution of useful user code stops and the garbage collector is running. The longer such “stop-the-world” pauses, the slower the program works from the end user's point of view. To reduce the length of pauses spent on garbage collection, the Lazy Sweep algorithm was implemented in Ruby 1.9.3. Starting with this version of MRI, the sweep-stage of garbage collection does not end with the complete freeing of memory from unnecessary objects, but only frees up the amount of memory that is necessary to continue the execution of the program — to create a new object. When creating the next object, some memory is released again, and so on.



In Ruby 2.0, another garbage collector improvement has been integrated - Bitmap Marking GC. This algorithm is aimed at Unix systems, which use the copy-on-write mechanism when creating child processes using fork . The child process is created quickly, because its memory is only a “mapping” of the memory of the corresponding parent process. The real separation of the memory of the parent and child process occurs after writing any data to the common memory area. Many popular Ruby libraries use fork , such as the popular Unicorn application server and the library for performing background tasks Resque. However, the classic garbage collector in MRI did not fit well with the fork semantics, because during the mark phase I set the “usability” flag on each object, thereby modifying a significant part of the heap, effectively leveling the advantages of the copy-on-write mechanism for Ruby processes. In Ruby 2.0, the flags, whether objects are used or not, were moved to a separate structure — a bit mask stored independently of the objects themselves. This made it possible to significantly increase the amount of memory shared by the processes when fork and it is better to use the advantages of copy-on-write semantics.

malloc_limit The problem is 8 MB.

The most important characteristic of the garbage collector is the malloc_limit parameter — the memory allocation threshold, after which the GC is started. However, the value of this characteristic by default was extremely small - 8 MB. In modern systems, processing a request on a website can result in a sample of tens of megabytes of data from the database or reading large files. In this case, garbage collection is performed too often, reducing the speed of the program.



Partly to solve this problem, application server developers attempted to make the garbage collector's behavior more predictable and minimize the impact of GC on the speed of processing HTTP requests. This has led to the emergence of technologies such as Unicorn OobGC and Passenger Out-of-Band Work . Both solutions disable garbage collection at the time of processing the request and force it to run after the request is processed by the server. Such a mechanism is also not without flaws: GC can be launched more often than needed, if the requests are “lightweight”, or, on the contrary, the process can “eat” too much memory.



The malloc_limit functionality was revised in Ruby 2.1 - the GC trigger threshold began to adapt to the behavior of the application, and the default value was increased to 16 MB. Now malloc_limit automatically changes with massive memory allocation, with the result that the garbage collector runs much less frequently.

Ruby 2.1. Object Generations

The release of Ruby 2.1 was marked by significant changes in the algorithm of the GC. The generation-based garbage collector has been integrated into the language. His work is based on the hypothesis that most of the objects created in the program are “die young”. Thus, the main activity of the garbage collector is associated with objects that have a short life cycle.



In Ruby, the memory is divided into 2 generations of objects - the generation of young objects and the older generation, which includes objects that have survived at least one garbage collection. In most cases, garbage collection is carried out only within the younger generation. Only at the moment when the memory runs out - complete garbage collection is performed with the participation of both generations.



An important problem with this approach are backlinks from the objects of the older generation to the objects of the younger generation.



If you do not take into account the possibility of the emergence of such links, minor GC - garbage collection within the younger generation can mark the actually used objects as garbage. To solve this problem, a special structure is used - Remember Set, in which problem links are remembered. To determine whether such links appear, the reading barrier in the Ruby interpreter is used. “Adult” objects from which references to objects of the younger generation are used as root for minor garbage collection.



A significant limitation of garbage collection in MRI is the need to maintain backward compatibility with all the many C extensions developed for the language. That is why the Ruby GC algorithm is called RGenGC - Restricted Generational GC. The “limitation” of garbage collection is that all objects are divided into 2 types: shady objects are objects that are used or can be potentially used in C-extensions. Accordingly, the garbage collector cannot safely move them between generations. If such an object falls into the older generation, it will not be protected by a reading barrier, since the former semantics of the language did not require C-extensions to use such barriers. As a result, there may be "problem" links described above.



Shady objects do not participate in garbage collection for generations, only normal objects migrate between generations. This solution made it possible to maintain compatibility with existing C-libraries and simplified the development of the garbage collector. However, in turn, it excludes a significant number of objects from the work of the new garbage collector. Nevertheless, according to the measurements of the RGenGC developers, the acceleration of the application performance when using the new garbage collector is about 10%.

Future plans

The garbage collector is one of the most dynamic parts of the language. In the near future - bringing the number of generations of the language to three. Of more global things, it is planned to introduce parallelism in the mark and sweep phases of garbage collection, which will make it possible to better use the capabilities of modern multi-core processors.

Additional sources of information

Presentation of Koichi Sasad at RubyConf 2013

The book Ruby Under a Microscope (2013)