Tower of Hanoi Performance

May 27, 2009 at 6:16 pm (Programming)

For who doesn’t know, Tower of Hanoi is a interesting puzzle, for more information see http://en.wikipedia.org/wiki/Tower_of_Hanoi, the resolution of this game has exponential complexity, more specifically 2n – 1 where n is the number of disks, this mean that for 3 disks you need 23 - 1 or 7 movements to move the disks to another rod. Now we will see recursive implementation of Tower of Hanoi resolution in three different languages running on JVM. The languages are Java, Clojure (a lisp dialect) and Ruby using JRuby. The JVM is so powerful and there is an active and interesting work to run other languages, with that, allow us to use several implementations JVM based, and too to possibility interoperability in different languages. This post will show performance of each language with the same situation. My goal here isn’t show what language is better or faster, but just make a reflection about performance, is important to analyze that the projects like Jruby and Clojure has much to evolve, they’re relative newer projects.

Test 1 – Clojure: Clojure test performance delight me a lot, we have to considerate that it’s an interpreted language.

Implementation:

;;hanoi.clj
(defn hanoi [n from to via]
       (when (not= n 1)
         (do (hanoi (- n 1) from via to) (recur (- n 1) via to from))))

(time (hanoi 30 "left" "middle" "right"))

Execuction and Performance:

java -server -Xmx1024m -XX:+AggressiveOpts -XX:+UseParallelOldGC -XX:+UseParallelGC -cp /opt/clojure/clojure.jar clojure.lang.Script hanoi.clj

Runtime: 56.714 sec

Test 2 – Jruby: This test disappoints me slightly, this is a great project and ruby is a great language.

Implementation:

#hanoi.rb
def hanoi n,a='left',b='middle',c='right'
    return if n==0
    hanoi (n-1),a,c,b
    hanoi (n-1),c,b,a
end
hanoi 30

Execution and Performance:

jruby -b --server --fast hanoi.rb
Runtime: 188.684 secs

Test 3 – Java: This test is a reference for the other languages. Show us how the other languages JVM based have to grow up.

Implementation

//Hanoi.java
public class Hanoi{
    public void move(int n, String from, String to, String via) {
        if (n != 1) {
            move(n - 1, from, via, to);
            move(1, from, to, via);
            move(n - 1, via, to, from);
        }
    }

    public static void main(String args[]){
        Long start = System.nanoTime();
        new Hanoi().move(30,"left","middle","right");
        System.out.println(System.nanoTime() - start);
    }
}

Execution and Performance:

java -server -Xmx1024m -XX:+AggressiveOpts -XX:+UseParallelOldGC -XX:+UseParallelGC Hanoi
Runtime: 4.83 secs

How you can see, the tests were executed in optimized mode on JVM, and after this analyze, I have opinion that these JVM based languages will be the future.

About these ads

1 Comment

  1. Leonardo said,

    Real.. intendi bulhufas !!!!! hahah

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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: