eighty-twenty

Today, on a whim, I decided to “benchmark” a very old scheme-like interpreter I had lying around from almost a decade ago. The “benchmark” I chose was that old stalwart, the Fibonacci function. Since I have a PowerBook G4 1GHz (512MB RAM, MacOS X 10.3), I chose to investigate the runtime of (fib 29).

The results I got when comparing my lisp2’s runtimes against other Scheme implementations and other programming languages were somewhat surprising.

1. Java came top of the list!
2. Self, an insanely dynamic language, was a staggering 2/3 as fast as optimised C (1/2 as fast as Java). This was the real surprise. This result means (loosely) that for every two instructions the C compiler is emitting for microbenchmarks like this, the Self compiler is emitting three. Considering the amazing flexibility of Self, that seems a trivially small price to pay.

The “Ops/s” column contains a kind of BogoMips value I cooked up based on the instruction set of my ancient lisp2 interpreter.

For reference, the code for the various versions follows. Most of the Scheme implementations had a (time) macro for measuring execution time; I used gettimeofday() for the C code, System.currentTimeMillis() for the Java, and Time.now () for the SML. For the Squeak SmallTalk version I used the timeToRun method on class Block, and for Self I used the cpuTime method on traits Block.

Come to think of it, I could have written the timing algorithms to be a little more accurate, especially for the faster implementations, but for such a trivial microbenchmark it’s not really worth the bother. The timing I did is good enough for the ballpark figures I was after.

Here’s the code for the Scheme version:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

Here’s the core of the C version:

static unsigned long fib(int n) {
  if (n < 2) {
    return n;
  } else {
    return fib(n - 1) + fib(n - 2);
  }
}

Here’s the core of the Java version:

public static long fib(int n) {
    if (n < 2) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Here’s the core of the SML version:

fun fib 0 = 0
  | fib 1 = 1
  | fib n = (fib (n - 1)) + (fib (n - 2))

The Squeak version - this method was placed on class SmallInt:

self < 2 ifTrue: [^ self].
^ (self - 1) fibonacci + (self - 2) fibonacci

And finally, here’s the Self version. Note that the following code already existed in the image, on traits Integer:

<= 1 ifTrue: [ self ]
      False: [ predecessor fibonacci + (- 2) fibonacci ]

I should try coding up Doug Bagley’s Language Shootout benchmarks in Self, just to see where it places overall. I should also try all the above on Intel x86 CPUs.

What an achievement Self is!