Recursion in Ruby

I recently took part in the RPCFN. Being that this month's challenge was a Shortest Path type challenge and I've done enough discrete maths papers to know that the best graph traversal Algorithm for this is Dijkstra's least cost path one I went away and implemented it in a couple of hours. Many others did exactly the same thing, often much more elegantly that me. What struck me was that the markers were quite obviously looking for people to imagine up their own method of finding the shortest path, and had a massive bias towards recursive algorithms.

Now the winning submission is a very nice piece of code, it's concise, easy to read, simple, well tested, and it clearly lays out it's goals, to find a recursive solution to the problem with disregard of performance. It performed ok, I did wonder however how the recursion would impact the performance on larger problem sets.

So I took Todd's code and refactored mine to work with his data structures. I also changed up my code to match his module's interface and packaged both implementations into their own classes so that there wouldn't be clashes while trying to test them. (modules are for adding abilities to classes, not for providing whole feature sets, if you see yourself including a module into main, you're doing it wrong...)

And here it is.

I ran benchmarks on a low end computer (Pentium 2.8) against 3 graphs, one with 2 nodes and 2 edges, the RPCFN example with 7 nodes and 10 edges, and a larger, more complicated one of 7 nodes and 21 edges, all of this is in the code linked above. Here's the results over 10000 iterations:

Simple Graph:
Iterative Approach took 1.54700second(s).
Recursive Approach took 0.95300second(s).
RPCFN Graph:
Iterative Approach took 6.37500second(s).
Recursive Approach took 20.62500second(s).
Large Graph:
Iterative Approach took 10.70300second(s).
Recursive Approach took 472.96200second(s).

The numbers speak for themselves, this approach doesn't scale at all well. In fact at first I thought I'd broken some of Todd's code and created an infinite loop of some sort. It's more than likely that the recursive function could be tweaked to get better performance, but short version is that if I were ever to need to implement graph traversal in Ruby for any production system, recursion would be the last approach I'd look at.

Final word
Todd's decision to use a recursive solution in this case was totally justified, readability and simplicity were massive factors in this event. That said I believe that outside of the smaller, more contrived problem scopes, recursion brings a lot of headaches and scaling issues than the iterative approaches.

Exception Errno::ENOENT in PhusionPassenger

As Passenger fails so rarely there's not much documentation on the error messages, so I'm posting this for the benefit of googlers everwhere... Scroll to the bottom for the Cliffs notes.

Passenger is a fantastic piece of software, I can't praise it highly enough. It's brought Ruby deployments from the complexity of reverse proxying to a mongrel cluster up to being on par of ease with PHP, a difficult and noteworthy achievement that can only increase the adoption of Rack based technologies in the future.

That said, in very rare cases the Passenger spawner blows up in spectacular ways that the old Mongrel deployments never even dreamed of. When this happens all of your current and future Rack instances running on Passenger will respond to every request with a 500 error, your only course of action being a full Apache restart, and since it's so rare there's usually nothing that can be found on the net to fix it.

Here's an example from one of my company's Sinatra services:

*** Exception Errno::ENOENT in PhusionPassenger::Rack::ApplicationSpawner (No such file or directory - /tmp/passenger.19250/backends/backend.Hoa3NPf9xWIsBy3D4sBZtTKE1DgjhTKjbSpdwSPWW6FakeTwddzh2hwteMo6qYecQC
zgV) (process 8942):
      from /opt/ruby-enterprise-1.8.6-20090610/lib/ruby/gems/1.8/gems/passenger-2.2.4/lib/phusion_passenger/abstract_request_handler.rb:279:in `initialize'
      from /opt/ruby-enterprise-1.8.6-20090610/lib/ruby/gems/1.8/gems/passenger-
...snip...
[ pid=725 file=ext/apache2/Hooks.cpp:688 time=2009-11-24 06:31:02.381 ]:
Unexpected error in mod_passenger: Cannot spawn application '/opt/number_service': The spawn server has exited unexpectedly.
Backtrace:
   in 'virtual boost::shared_ptr Passenger::ApplicationPoolServer::Client::get(const Passenger::PoolOptions&)' (ApplicationPoolServer.h:471)
   in 'int Hooks::handleRequest(request_rec*)' (Hooks.cpp:485)

The root cause here is actually this ticket - the /tmp/passenger.****/ folder will be almost empty because some temp watcher cleaned it out in a quiet period. The ticket has been closed but unless you feel like building from source you'll have to wait until the next release to fix the issue.

Our fix was to move the Passenger temp directory out of /tmp in the Apache httpd.conf to stop temp watchers from nuking our deployments. Instructions on setting this up are found in the fantastic Passenger documentation.