Ruby Performance on Various VM’s

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.

About these ads
This entry was posted in diversion, Ruby. Bookmark the permalink.

3 Responses to Ruby Performance on Various VM’s

  1. Bill says:

    I wonder what happened with the whole Google Code Jam thing. Anyone heard anything?

  2. Sumudu says:

    It is happening today, but it’s only a test run of their hosting system so it is “invite” only (in other words, not advertised).

    Also, your timing in the ruby program is slightly misleading — you never reset the timer between pruning and no-pruning. On my computer, there is very little difference between the two methods.

  3. Bill says:

    Good catch Sumudu. I created a revision that rectifies the profiling bug. (see update in body of post above).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s