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 expected 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 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.

Ruby - no register variables for objects

Any Ruby object must be written to the stack, otherwise it can be freed by the garbage collector. Not only is this slow and takes up stack, it makes the garbage collector run slower because it has to look through more data on the stack.

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