Saturday, 12 November 2011

Real garbage collector characteristics

The trade-offs between tracing and reference counting garbage collectors are nicely demonstrated by systems like F# and Mathematica. F# inherits garbage collection from .NET which uses a conventional generational tracing garbage collector with three generations and a Large Object Heap (LOH). Mathematica uses reference counting with language semantics that make it impossible to create cycles in the heap.

The following Mathematica program creates a balanced binary tree 25 levels deep that contains 225 branches stores it in a variable and then mutates the variable back to the empty list:

Because Mathematica uses reference counting, the act of resetting the variable back to the empty list decrements the reference count for the root of our tree back to zero, causing an avalanche of reference counts in the branches down to the leaves also being decremented back to zero, reclaiming all of the space that was consumed by the tree that is now unreachable. Moreover, Mathematica is serial so all of this work is done on the main thread, blocking everything. Consequently, resetting the variable to the empty list takes a whopping 2.213s.

Surprisingly, although Mathematica has clearly done a lot of work that is presumably involved in releasing the space consumed by the tree it does not actually return any memory to the OS and continues to consume almost half of the entire 32-bit address space on this machine!

This program may be written as follows in F#:

type t = Leaf | Branch of t * t  let rec deepTree = function   | 0 -> Leaf   | n -> Branch(deepTree(n-1), deepTree(n-1))  let mutable t = deepTree 25  t <- Leaf  System.GC.Collect()

In this case, creating the tree takes 10.2s, resetting the tree takes a fraction of a millisecond and explicitly invoking the garbage collector (which actually returns all of the memory back to the OS) takes 0.44s.

This highlights some of the trade-offs involved both in using systems that provide garbage collection as a user and in creating such systems as a developer.


Jonathan Shore said...

I'm curious how this performs under mono. I assume you were using the MS .NET VM?

I've started using the mono VM, having moved away fro the JVM a while ago. The generational GC is still not production ready in that people are still finding bugs in its behavior.

When it does work (which is most of the time), found it to outperform a comparable C++ implementation using auto_ptr (reference counting) by 4x (if I recall correctly).

Flying Frog Consultancy Ltd. said...

@Jonathan: I haven't tested this under Mono but I wouldn't be surprised if smart pointers in C++ were a lot slower after I found this.