Bill Burcham’s memeRocket

What started a few days ago as a little tinkering with a Google Code Jam practice problem (Big City Skyline) turned into a mini-benchmark of three Ruby VM’s on my MacBook Pro 2.2GHz. The program (a solution to the “Big City Skyline” problem) is an O( N log( N ) ) in-memory search with a little integer math.

Quickie findings: the in-development Ruby 1.9 VM performed best — beating 1.8.6 by a factor of two. For the numbers (comparing 1.8.6, 1.9 pre-release, and Rubinius pre-release) have a look at the spreadsheet and chart over on Google Docs. Also of note: the Ruby solution did beat the four minute time limit for N=10MM given in the problem statement. This was on random input. Worst-case performance would not be as good.

It makes me happy that the Ruby solution had adequate performance. Also it was interesting to see how the Ruby language fit for a problem you’d usually see done in LISP. I would have liked to have dynamic scope to do a cleaner implementation of @@largest_so_far. On the other hand, “memoization” is pretty natural in an OO language like Ruby — you create an instance (of Skyline) for each context and simply use instance variables to hold previous results.

update Nov 15, 2007: Reader Sumudu points out that version 5 neglects to reset the timer between pruning and non-pruning variations. Version 6 rectifies this error. With that change it’s apparent that the pruning has no positive effect. In fact non-pruning actually wins by a small amount for N=1 to N=100,000 on my MacBook Pro.

A few weeks ago I wrote about Unobtrusive JavaScript using the Prototype versus JQuery stacks. In that post I came down on the side of the JQuery stack. Something I didn’t analyze at the time, was: is it possible to use a little of each? For instance, say (hypothetically) that you have a big old Rails project that uses RJS all over the place and you’d like to continue using RJS — is there a way to leverage pieces of JQuery in that scenario.

In this pursuit I learned a few things. Firstly, plain old JQuery does not “do” UJS in the following sense: if you bind a behavior to an element (via a CSS selector), that binding will not be reapplied as the DOM is manipulated. For dynamic binding, or “live” binding that gets re-applied after every DOM update, you need Brandon Aaron’s livequery plugin for JQuery. Livequery is to JQuery as Dan Webb’s Low Pro is to Prototype — kind of. Difference being that livequery hooks each of JQuery’s DOM manipulation routines, whereas Low Pro hooks each of Prototype’s Ajax.Responders “onComplete” event — the event that happens when an XHR is complete.

What all this means is that you can use JQuery’s UJS (livequery) if you use JQuery for all your DOM manipulations, or you can use Prototypes UJS (Low Pro) if you use Prototype for all your Ajax calls. The unfortunate bit is that you cannot (yet) use livequery with Prototype Ajax calls, or Low Pro with JQuery DOM manipulations. Can’t we all just get along?

I wonder if a UJS package could remain stack agnostic. I think livequery is on to something by hooking DOM manipulation routines. That seems more robust (if potentially less performant) than hooking the Ajax returns. By hooking DOM manipulation it seems that you’ve plugged more holes and have a more general-purpose solution. Could the livequery approach (of watching for DOM manipulation) be done in a stack-agnostic fashion rather than by hooking JQuery routines? If we could do that then we’d have a UJS package we could use no matter which JavaScript base library we choose — or perhaps whichever library chooses us.