It’s been 8 years since the first just-in-time compiler was introduced in Ruby. However, throughout this time, the garbage collector has been a black box to the JIT compilers. This meant that JIT compilers were not able to optimize any object allocations and instead had to perform function calls. This has all changed now that we have integration of the GC fastpath into ZJIT. In this article, we’ll be looking at how object allocations work in the GC, what it means to inline the GC fastpath into ZJIT, and the performance implications.

Object Allocation

In Ruby’s default GC, object allocations previously used a free list based allocator. The free list allocator keeps a linked list of all of the empty slots. When it allocates an object, it allocates it at the head of the free list and moves to the next element. We can see an animation of the free list allocator:

Animation showing how the free list allocator works.
Animation showing how the free list allocator works.

In Ruby pseudocode, it looks like this:

def allocate_from_freelist
  obj = @freelist
  if obj # If we are able to allocate at the head of free list
    @freelist = obj.next # Move to next element of free list
    obj # Return allocated object
  else # Free list is empty
    gc_slowpath # Allocate more memory or run GC
  end
end

In contrast, a bump pointer allocator keeps a cursor and a limit. It allocates objects at the cursor and increments, or “bumps”, the cursor by the size of the object. If the allocation pushes the cursor past the limit, then the allocation would not succeed because we do not have enough memory for the allocation. Here’s an animation showing the bump pointer allocator:

Animation showing how the bump pointer allocator works.
Animation showing how the bump pointer allocator works.

In Ruby pseudocode, it looks like this:

def allocate_from_bump_pointer(size)
  obj = @cursor
  @cursor += size # Increment cursor by size of object
  if @cursor <= @limit # Enough space for allocation
    obj # Return allocated object
  else # Not enough space for allocation
    gc_slowpath # Allocate more memory or run GC
  end
end

If you compare the pseudocode of the free list allocator and the bump pointer allocator, it seems like they should both perform roughly the same right? There is one critical difference. A free list allocator calls obj.next, which requires reading from the slot that it has allocated. This extra memory read has significant performance penalties compared to the simple addition of the bump pointer allocator.

This was one of the main reasons why we switched Ruby’s default GC to use a bump pointer allocator from a free list allocator. However, we note that, due to technical limitations, the bump pointer allocator in Ruby’s default GC is not quite a canonical bump pointer allocator as it does not allow the allocation of truly dynamic object sizes. It still maintains several heaps each with their own fixed slot sizes. Each bump pointer is only allowed to bump by a certain fixed size.

Another GC implementation that we’re working on is MMTk. MMTk natively supports bump pointer allocators and the bump pointer allocator can allocate dynamic object sizes. We often use MMTk as a testbed for new techniques since it already has support for many advanced GC features.

GC Fastpath

Even with a bump pointer allocator, every object allocation requires a function call into the GC. This function call has significant overhead for object allocations. So how do we avoid this function call? The answer is for the JIT compiler to generate instructions to inline the fastpath of object allocations and we’ve built that into ZJIT.

But what is the “fastpath”? There are currently three possible paths an object allocation can take. Unsurprisingly, they’re called fast, medium, and slow paths:

  • Fastpath: the path shown above in the Object Allocation section. This tries to bump the pointer in the current block to allocate the object.
  • Medium path: if the fastpath fails to yield an object, it means that we have exhausted the memory of the block. We need to find the next block to allocate memory into and we can retry the fastpath.
  • Slow path: if we have no more blocks, then we are really out of memory. We have to either allocate more memory or trigger a new GC cycle. This will create blocks that are empty, and we can retry the medium path.

We only inline the fastpath in ZJIT. If it fails, we fall back to using a function call into the GC. Since the vast majority of the allocations will hit the fastpath, it will yield the most performance gains without dealing with the complexity of the medium and slow paths.

Implementation

The GC fastpath was introduced in Ruby PR #17277. There are several moving parts that together make it all work, and we’ll look at it piece by piece.

GC Implementations

Support for the GC fastpath starts at the GC implementations themselves. Since the introduction of the modular GC feature there are multiple GC implementations in Ruby. GC fastpath implementation for each GC is different and so we have a GC API function rb_gc_impl_zjit_new_obj_fastpath that is given information about an object that we want to allocate. It will then decide whether it can perform the allocation using the fastpath or not. If it can, it will also emit the data necessary for the allocation, such as which cursor and limit to use.

The implementation here differs depending on whether we are using the default GC or MMTk. In this article, we will focus on the default GC.

ZJIT GC Fastpath

Once rb_gc_impl_zjit_new_obj_fastpath determines if we can use the fastpath allocator and provides us with the necessary data to do so, we can emit ZJIT LIR instructions for the fastpath. This happens in the file zjit/src/codegen/gc_fastpath.rs which defines the functions emit_default_new_obj_fastpath and emit_mmtk_new_obj_fastpath which emits the ZJIT LIR for the default GC and MMTk, respectively.

ZJIT HIR Instructions

Implementing the GC fastpath doesn’t automatically give us any gains because no objects are allocated through it. To take advantage of the GC fastpath, we have to use it when generating LIR for various ZJIT HIR instructions that allocate. For example, PR #17717 implements the GC fastpath for the newhash instruction when the hash is empty. The most important code is in gen_new_hash. I have extracted the relevant code from that function and added some comments:

// Determine the size of the object.
let alloc_size = unsafe { rb_zjit_hash_new_size() };
// Flags for object metadata.
let flags = RUBY_T_HASH as u64;
// Class of the object.
let klass = unsafe { rb_cHash };

// Use the GC fastpath to allocate the object.
let hash = gc_fastpath::gc_fastpath_new_obj(jit, asm, alloc_size, flags, klass, |asm| {
    // Closure for a fallback that gets called when the GC fastpath is not
    // supported by the GC or when it is out of memory.
    // This calls rb_hash_new, which is a C function that allocates a new
    // empty hash.
    asm_ccall!(asm, rb_hash_new,)
});
// Set up the allocated hash with nil as the default value.
asm.store(Opnd::mem(VALUE_BITS, hash, RUBY_OFFSET_RHASH_IFNONE), Qnil.into());
// Return the allocated hash object.
hash

So far, we have implemented GC fastpath on the following instructions:

ZJIT HIR Instruction Description Fastpath Support
NewHash Hash literal. Empty hash or a small (less than or equal to 8 elements) hash with only symbols as keys.
NewRange / NewRangeFixnum Range literal. When either endpoint of the range is nil or both are fixnums (small integers).
ObjectAllocClass Creating a new instance of a class. When the class uses the default allocator.
StringCopy A string literal in a file without the frozen_string_literal: true magic comment. Strings of maximum allocation size by the GC (999 bytes for default GC, unlimited for MMTk).
ArrayDup An array literal with only compile time constants (e.g. integers, strings, symbols, etc.). When the array has less than or equal to 3 elements.
NewArray An array literal with dynamic values (e.g. values from variables). When the array has less than or equal to 3 elements.

Performance

Since the GC fastpath API is designed with a fallback closure when the fastpath is not able to allocate, we can easily turn off the fastpath by always executing the fallback. To clearly see the performance improvements, we can write small microbenchmarks that compare the allocation performance of various types. For example, the following benchmark allocates hashes with 3 elements in a loop.

def run(times)
  i = 0
  while i < times
    a = {a: 1, b: 2, c: 3}
    i += 1
  end
end

30.times { run(1) } # Warm up ZJIT
run(10_000_000) # Run the benchmark

We can see from the benchmark results below that the fastpath nearly doubles the performance of hash allocations. Note that this benchmark also includes interpreter and garbage collection overhead, which isn’t optimized by the GC fastpath:

Benchmark 1: fastpath
  Time (mean ± σ):      66.4 ms ±   1.4 ms    [User: 59.4 ms, System: 5.4 ms]
  Range (min … max):    64.7 ms …  73.1 ms    43 runs

Benchmark 2: no fastpath
  Time (mean ± σ):     117.2 ms ±   1.5 ms    [User: 113.1 ms, System: 2.9 ms]
  Range (min … max):   115.0 ms … 121.6 ms    25 runs

Summary
  fastpath ran
    1.77 ± 0.04 times faster than no fastpath

We can write similar benchmarks for other types and also see 2-3x performance gains.

Conclusion

For the first time, the garbage collector is no longer a black box to a Ruby JIT compiler. By having the GC hand ZJIT everything it needs to allocate an object ZJIT can inline the allocation fastpath and skip the C function call entirely. We’ve already brought this to hashes, ranges, arrays, strings, and object instances, with significant speedups seen in microbenchmarks.