Nikos D.

This week I've been playing with charlie (a Genetic Algorithms library) and I've been rewriting the TSP example that's included with it so I can have a very very simple "prototype" for the GRuVeR project. I must say that I kind of left it incomplete and that's because I wanted to test on which RVMs it's running properly and after fixing it for the ones that it didn't, what's the performance on each of them.

Compatibility:
It turned out that it was running just fine to all of them except Rubinius. I managed to figure out what the problem was and after fixing it I jumped right away to the testing part :)

Comparisons:
Okay, I must say that I was expecting quite the opposite results (ok, almost the opposite). And why's that? Let's take a look:

Let's start with Ruby 1.8 (MRI):
$ time ruby tsp_solver.rb
real 0m34.940s
user 0m34.398s
sys 0m0.125s

Ruby 1.9 :
$ time ruby19 tsp_solver.rb
real 0m21.533s
user 0m20.736s
sys 0m0.119s

Let's move to the alternatives now.

First JRuby 1.1:
$ time jruby tsp_solver.rb
real 0m57.815s
user 0m48.651s
sys 0m0.751s

JRuby 1.1 with -J-server flag:
$ time jruby -J-server tsp_solver.rb
real 0m34.834s
user 0m37.714s
sys 0m0.667s

And finally Rubinius:
$ time rbx tsp_solver.rb
real 12m29.830s
user 12m20.105s
sys 0m4.219s

Graphics are always better:

Wow! There's quite some difference amongst them! To be honest, I really expected the vanilla Ruby to be the slowest (at least I hoped so) but no-no! It may be slower than 1.9 but it's faster than the rest of them. Obviously, Rubinius is out of the competition for this one. I believe that this specific code I tested is really an edge; the time required for rubinius to finish is practically infinite. After all it's the only VM that hasn't reached a 1.0 milestone yet so a lot of things will eventually get way better.

Update: Charles told me that running this example with JRuby and Java 1.6 results in much faster execution, faster or close to Ruby 1.9 to be exact. Quoting his words: "ok...and if it's not as fast as YARV, file a bug for me :) " . Heh, so I guess he is probably right. I will try to test it as soon as I set up Java 6 in my machine (off-topic: it's a shame that Leopard doesn't ship with Java 1.6 included...). And also thanks a lot Vladimir for letting me know about the -J-server flag (I'm not that familiar with Java).

Now, for those who want more info on the code and the machine (updated to include more details):
The machine is a MacBook Pro with 2.2GHz Intel Core 2 Duo and 2GB Ram running Mac OS X Leopard 10.5.2. The source code for the tsp_solver.rb can be found here and it requires the charlie gem (of course you can grab the code from the repository and pack it under a lib folder or something and require that instead in the tsp_solver).

Now, the exact RVMs versions:

• $ ruby -v
  ruby 1.8.6 (2007-09-24 patchlevel 111) [universal-darwin9.0]
• rbx -v
  rubinius 0.8.0 (ruby 1.8.6 compatible) (bbe450f22) (04/15/2008) [i686-apple-darwin9.2.2]
• $ ruby19 -v
  ruby 1.9.0 (2007-12-25 revision 14709) [i686-darwin9.2.2]
• $ jruby -v
  ruby 1.8.6 (2008-03-28 rev 6360) [i386-jruby1.1]
  And: $ java -version
  java version "1.5.0_13"
  Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_13-b05-237)
  Java HotSpot(TM) Client VM (build 1.5.0_13-119, mixed mode, sharing)
  

Please, please, please keep in mind that this code, although it has to do with an almost real-life situation, is really specific and targeted! Don't take this comparison as a measure of speed between different Ruby implementations! I did it because I was curious to see the results and I will do it again a) when new versions of these VMs come out and b) with most of the code that I'm going to write for this project.

Later today (or probably tomorrow) I'm also going to post the results of the profiler for each VM for those of you who are curious but lazy to run it on your machine :) In case someone wants to run it, the integer parameters of this call can be minimized (so you can reduce the time required for the code to finish) :

population = Population.new(@genotype,100).evolve_silent(1000)

The first one is about the size of the population of each generation and the second the number of the generations that it is required to be generated. The smaller, the faster but the bigger, the better results (as this algorithm finds an estimation and not the exact solution for the *randomly created* Traveling Salesman Problem). Another parameter that could be reduced is the number of cities/stops which is the parameter of TSPSolver::by_example with a default value of 100. Try to reduce them altogether for better balance ;)

Have fun!

This year is the last that I'm going to be a student, at least a bachelor one, since i've already completed (almost) my thesis and pretty soon I will be saying bye-bye to my University. I haven't really had the chance to participate in Google Summer of Code partially because I had never really heard of it (in time) and also because I didn't believe that I was able to contribute something really good (lack of confidence here :) ). But this year and after messing around with others' people code (heh) and some of my own (including my thesis) and with the help/ideas given by some friends I did finally sent a proposal.

The main concept is to implement a library for solving Vehicle Routing Problems in Ruby. How is this going to happen? The ground basis will be the beautiful Charlie library, written by Sander Land, which makes it really easy to write programs with Genetic Algorithms built in and really fast (in terms of time required to write the code :D). James also pointed out Gecode/R which is frontend to Gecode and uses another technique, Constraint Programming and I'm trying to think if and how this can also be used (a discussion can be found on the Gecode/R mailing list). I'm not going to get into details here; if anyone is interested a part of the proposal can be found in the Ruby mailing list and the full version is available as pdf here. Feel free to send in any thoughts :).

I'm really waiting for the ranking results and I reeeeeally hope that it will get accepted even though it's a really specific and targeted project when compared with others like contributing to the alternative VMs, refactoring RDoc (although version 2 is out) and such. The good thing with implementing this, is that it will produce some really nice benchmarks between the different VMs and also create some feedback with suggestions/patches/fixes (here are some examples from this Monday's experiments I was doing). Regardless though of whether or not it gets accepted, I believe that I will finally write this thing cause after a chat I had with Sander, which by the way is my potential mentor to the project, he also seems interested in this and willing to help.

So, stay tuned for updates on this - later this day I'm going to post some benchmark results between almost all current Ruby VMs (Ruby 1.8, Ruby 1.9, JRuby 1.1 and Rubinius)* after running some example code I wrote for the Traveling Salesman Problem.

* I'm missing the C# implementation of Ruby here but I thought that it won't be able to run on my Mac so I didn't bother to try it. If I'm wrong please let me know and I will also set it up right away!

P.S.: Do you have a better name in mind for the project??? I'm not sure I like "GRuVeR". Wouldn't something like "delivery" sound better?