{ tinou bao }

It's All Garbage

Amazon.com says I bought Programming Ruby (2nd edition) on November 4, 2004.  Seven short years of Java later I'm finally putting it to use.  One immediate question is, how does garbage collection work in Ruby?  Is it a tracing or reference counting collector?  Is it generational, and if so, how many generations?  These questions eventually led me to an interesting paper by David Bacon, Perry Cheng and VT Rajan on A Unified Theory of Garbage Collection.

Universally, garbage collectors are viewed as either tracing or reference counting.  The Sun HotSpot VM, for example, is a tracing collector.  It traverses the object graph from the roots, finding reachable live objects and reclaiming unreachable dead objects.  PHP, on the other hand, uses reference counting to decide which objects can be safely garbage collected.  This table summarizes the typical characterization of each collector type,

	Tracing	Reference Counting
Collection Style	Batch	Incremental
Cost per Mutation	None	High
Throughput	High	Low
Pause Times	Long	Short
Real Time	No	Yes
Collects Cycles	Yes	No

The first observation is, once optimizations are added to the basic tracing and reference counting collectors, they begin to converge.  For example, with deferred reference counting there is a periodic scanning of stack references to reduce per-mutation cost.  A generational tracing collector, on the other hand, imposes a per-mutation overhead but gains shorter pause times.  So even though collectors are typically described as one or the other, we should really view them as hybrids.

The second interesting observation is, tracing algorithms are the duals of the reference counting algorithms.  Both types of algorithms share the same structure.

	Tracing	Reference Counting
Starting Point	Roots	Anti-Roots
Graph Traversal	Forward from roots	Forward from anti-roots
Objects Traversed	Live	Dead
Initial Reference Count	Low (0)	High
Reference Count Reconstruction	Addition	Subtraction
Extra Iteration	Sweep Phase	Trial Deletion

Tracing collectors start at the root, traverse foward, finding live objects.  Initially all reference counts are zero (an underestimate) but live objects have their reference count incremented to their true value (keeping a bit flag is just an optimization of actual count).  Reference counting collectors start from non-root objects, traversing forward to find dead objects.  Reference counts are initially high (an overestimation that includes references from dead objects) but decremented until the true reference count is obtained.  Ultimately, the difference is just the initial value (an underestimate or overestimate) and whether we increment or decrement to obtain the true reference count.

So that was interesting, but lets return my the original question about Ruby garbage collection and add a few other languages in for fun.  Here's a quick summary.  Don't quote me on it, corrections appreciated. 

Language	Garbage Collection (for reference/popular implementation - others may be available)
Erlang	tracing - per process (very small processes), compacting then generational optimization
Haskell	tracing - generational (3), 512KB nursery
Java	tracing - generational (2), serial, concurrent, concurrent + incremental
Perl	reference counting - does not handle cycles
PHP	reference countng  - 5.3 handles cycles w/ "on the fly" cycle detector, prior versions did not
Python	reference counting - handles cycles w/ tracing cycle detector
Ruby	tracing - non-generational
Scala	see Java

Fail Fast, Debugging and Systems that Never Stop

If you're a Java guy you're probably familiar with the phrase "fail fucking fast" in the context of Iterators (I added the fucking part).  But fail fast is much more than just iterators, it's a general design principle--and a very important one at that. 

Jim Gray on fail fast: "it [the process] should either function correctly or it should detect the fault, signal failure and stop operating."  You can replace "the process" with component, class, etc.  Whatever you designate as your logical unit, the fail fast principle remains.  What you absolutely don't want to do is detect the fault, don't signal failure and continue.  This is why swallowing exceptions is one of my all time pet peeves.  Fail fast is often described in terms of fault detection latency, the time between initial error detection and the fault.  You want your latency to be small. 

There are two advantages to failing fast. First, easier debugging and analysis.  It complicates things greatly if your code detects errors but continues.  Eventually something will go wrong but now you can't easily track down the root cause.  I recently worked with a component (one that shall remain nameless) that doesn't follow the fail fast principle.  During initialization the component knew it was missing a configuration file but instead of halting it continued on.  When the component was finally invoked things obviously did not work, but the root cause was not obvious.  Ended up wasting two days tracking down the root cause, when it really should have taken 30 seconds. 

Second, ability to build "systems that never stop".  Failing fast is so important to building highly available systems that Joe Armstrong talks about it at great lengths in his presentation on "systems that never stop (and Erlang)."  In this presentation he presents 6 laws,

1. Isolation
2. Concurrency
3. Failure Detection
4. Fault Identification
5. Live Code Upgrade
6. Stable Storage

Without failure detection you can't fail fast, and if you can't fail fast you can't achieve isolation.  Real world example: Amazon S3's massive outage last year.  A huge embarrassment to Amazon's otherwise great cloud stack.  Their code didn't have adequate failure detection, allowing a single corrupt bit to propagate throughout the system.  The result was hours of downtime while engineers scrambled.  If Amazon had been able to detect the single corrupt bit then they could have isolated the failing component instead of letting the error bring down the entire system.

Few of us will be coding S3 like systems, but it doesn't mean we can't follow the fail fast approach.  It will make debugging easier and just might prevent similar embarrassments.  I think some programmers don't like to fail fast because they worry they'll be blamed for the failure, so just pretend things are good and pray nothing bad happens downstream.  I suppose it depends on how much you believe in God. 

The Expression Problem and Other Mysteries of Life

The "expression problem" or the "extensibility problem" is closely related to the Open-Closed Principle (OCP).  OCP states that software should be open for extension but closed to modification.  The expression problem observes that for the two fundamental dimensions found in programs, data types and operations, OCP is only achieved for one but not both.

Take, for example, an application involving vehicles.  There two kinds of vehicles, automobiles and trucks.  All vehicles can accelerate.  It is easy to extend our application to include space ships. 

The problem arises when we realize that vehicles should also be able to brake.  To add a brake operation we will need to modify vehicle, automobile and truck; violating OCP.

We can attempt to approach things from a more operational point of view.  Using something like the visitor pattern we can build our application to handle new operations without the need to modify existing source code.  Here we simply add a new brake operation visitor.

But now the problem becomes how do we add a new vehicle to our application without violating OCP.  It is not hard to add a truck vehicle but all of our existing operations must be aware of truck.

Mind you, we want to achieve everything discussed so far with type safety, and static type safety at that, because, as Bertrand Meyer would argue, run time is a little late to find out whether you have a landing gear.  Incidentally, if you're wondering what the mysteries of life title is all about, it from this Meyer's article.  I find his style amusing.

So how can we solve this expression problem and the goals of Open-Closed?  Don't ask me, I'm just a guy with a blog who likes to use OmniGraffle.  But from what I've been able to gather there's no easy, straightforward solution.  We can use generics and "F-bounds" but the code then looks like

interface FooBar<C extends FooBar<C>> extends Bar<C> {...}

Quick, anybody knows what this means, because I sure have a hard time keeping track of recursive types.  The Scala guys say you can solve the problem with abstract types, self types and mixins.  But there seems to be a lot of scaffolding involved--lots of redefinition.  Maybe it's not so bad if I really knew Scala beyond a cursory level.  Some people argue these techniques only work if you have the foresight--you have to parameterized your design from the beginning; you have to declare types as abstract types from the start; etc.  Multi-dispath/multi-methods can help, but I don't think any mainstream languages support those constructs. 

In conclusion, I have no idea what I'm talking about.  But I do find it interesting--and a bit sad--that such a seemingly fundamental problem, the expression problem, is pretty involved to solve.  You would think by now some brilliant language designer would have figured things out in a simple, elegant way.