A Little Language Shootout

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. </ol>

    Language Implementation Detail Time (per (fib 29) call, in milliseconds) Ops/s Ratio (opt. C) Ratio (unopt. C)
    Java JDK 1.4.2_05 38 576027000 0.70 0.335
    C gcc 3.3, -O3 56 401161000 1 0.478
    SML SML/NJ 110.44 67 335299000 1.20 0.574
    Self Self 4.2 84 267441000 1.5 0.718
    C gcc 3.3, without any optimisation flags 117 192009000 2.09 1
    SmallTalk-80 Squeak 3.8alpha 653 34403000 11.7 5.6
    Scheme Chicken 1.73, compiled, -O3 890 25241000 15.9 7.6
    Scheme MzScheme v206 compiled to C using "mzc --exe" 1425 15764000 25 12
    Scheme Chicken 1.73, compiled, without any optimisation flags 1907 11780000 34 16
    Scheme MzScheme v206 interpreter 3523 6376000 63 30
    Scheme Chicken 1.72 interpreter 3900 5760000 70 33
    Scheme lisp2, my ancient interpreter 6310 3560000 113 54
    Scheme TinyScheme v1.31 36681 612000 655 313

    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!