Bounding Unicorns

Garbage Collection And Cycles In Python And Ruby

While working on PycURL I unintentionally came across how Python handles cycles.

Python reference counting

Ordinarily, objects in Python are reference counted. Reference counts are incremented by code working with objects and by container objects holding other objects. For container objects, the most common case is one of collections - a list increments reference count for an object placed in the list. Less obvious might be, for example, __dict__ - this is a dictionary of attributes present on most objects, and each object holds a reference to its attribute dictionary. When it comes to C extensions, an object that is implemented in C may hold a reference to a Python string object while the contents of the string is given to a C library to manipulate later.

The second part of reference counting is that code holds references to objects it manipulates. When an object is created, its reference count is 1 and the function that created the object is given that first reference. Suppose this function does not return the object and does not place it in a container; then at some point this function must decrement the reference count of the object, freeing the object, or the object will be leaked. If the function calls other functions operating on this object, it cannot decrement its own reference until those functions are finished. Alternatively, a function may return an object to its caller; if this happens, the caller owns the reference that the function owned.

Python cycles

Reference counting alone does not solve the cycles. To collect cyclic garbage, the runtime traverses all objects in existence via a special traversal method. On each object, the implementation of this method must iterate over all objects that the parent object holds a reference to. By traversing objects like this the runtime is able to determine if all of an object's references are reachable from the object itself - if so, this object can be garbage collected.

Ruby

Ruby does not do reference counting.

Instead Ruby uses a "mark and sweep" algorithm: first, it figures out which objects are currently reachable from the program, and then Ruby frees all remaining objects.

How does Ruby know which objects are reachable from the program? Again there are two parts to consider: code and data.

For code, according to this post the runtime traverses the entire stack, looking for pointer-sized values that match addresses of objects it allocated. More accurately, all stacks - one per Ruby thread.

For data, This post says Ruby walks the entire heap as well. I'm curious how Ruby knows what "heap" is. If a C library allocates memory using its own memory allocator, and a Ruby-C extension proceeds to store pointers to Ruby objects in that memory, how does Ruby know that that memory is, in fact, heap? Does Ruby just crawl the entire address space?

There is another difference between stacks and heaps. Deallocated memory is normally not overwritten until something else uses it. Until memory is reused it retains its old contents. So an object pointer that was placed in memory continues to be there, potentially for a long time, even after it is not really referenced. A stack has a stack pointer which separates the active part of the stack that is in use from the inactive part of the stack that is available for use, but not used. A runtime can know not to poke into the unused part of the stack. There is no similar mechanism for the heap - deallocated memory is indistinguishable from allocated memory for anything outside the allocator managing the heap.

I imagine the way Ruby GC works is by only traversing Ruby heap, and doing so by blocks currently allocated. This way pointers that remain in freed heap space do not prevent objects from being garbage collected, and reasonable performance is attained. It does however mean that C code can reference Ruby objects without Ruby realizing that.

Ruby - no register variables for objects

As important as collecting no longer referenced objects, a garbage collector must not collect objects which are still referenced. Code implementing C extensions for Ruby can run into trouble here because it may hold references to parts of a Ruby object but not to the object itself. As illustrated by this investigation, the code in question references the length and contents of a Ruby string but without a GC guard the address of the string object overall can be wiped out of memory and registers, leading the garbage collector to conclude it is unreferenced when that is not the case.

The workaround which must be meticulously considered in just about every function in a Ruby C extension is to ensure that addresses of all Ruby objects are saved either on the stack or in the Ruby heap whenever any Ruby VM function is invoked.

Python vs Ruby

Obviously, both approaches have benefits and drawbacks. Reference counts must be constantly incremented and decremented, whereas mark and sweep happens periodically. Is one better than the other?

I think in the particular case of the two languages in question, there is a clear winner. In my close to 10 years of using Python I have never heard that the language had "garbage collection issues". Garbage collection in Python must work pretty well. In contrast, I have heard about "Ruby garbage collection" for almost as long as I have been using Ruby. Before Ruby GC became a popular topic Rails simply leaked so much memory in pure Ruby code, nevermind C extensions, I imagine that garbage collection was not on anyone's radar.

Further reading