Why is Clojure much faster than mit-scheme for equivalent functions?

Question

I found this code in Clojure to sieve out first n prime numbers:

(defn sieve [n]
  (let [n (int n)]
    "Returns a list of all primes from 2 to n"
    (let [root (int (Math/round (Math/floor (Math/sqrt n))))]
      (loop [i (int 3)
             a (int-array n)
             result (list 2)]
        (if (>= i n)
          (reverse result)
          (recur (+ i (int 2))
                 (if (< i root)
                   (loop [arr a
                          inc (+ i i)
                          j (* i i)]
                     (if (>= j n)
                       arr
                       (recur (do (aset arr j (int 1)) arr)
                              inc
                              (+ j inc))))
                   a)
                 (if (zero? (aget a i))
                   (conj result i)
                   result)))))))

Then I wrote the equivalent (I think) code in Scheme (I use mit-scheme)

(define (sieve n)
  (let ((root (round (sqrt n)))
        (a (make-vector n)))
    (define (cross-out t to dt)
      (cond ((> t to) 0)
            (else
             (vector-set! a t #t)
             (cross-out (+ t dt) to dt)
             )))
    (define (iter i result)
      (cond ((>= i n) (reverse result))
            (else
             (if (< i root)
                 (cross-out (* i i) (- n 1) (+ i i)))
             (iter (+ i 2) (if (vector-ref a i)
                               result
                               (cons i result))))))
    (iter 3 (list 2))))

The timing results are: For Clojure:

(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 168.01169 msecs"

For mit-scheme:

(time (fold + 0 (sieve 5000000)))
"Elapsed time: 3990 msecs"

Can anyone tell me why mit-scheme is more than 20 times slower?

update: "the difference was in iterpreted/compiled mode. After I compiled the mit-scheme code, it was running comparably fast. – abo-abo Apr 30 '12 at 15:43"

Beefcake

Thanks for doing this kind of comparison. I believe it helps both languages. – Alane

I think your Scheme code is incorrect. In particular, make-vector will fill the vector with 0, which is treated as true in Scheme. Changing it to (make-vector n #f) produces much more sensible results. – Virginity

(make-vector n) is filled with #f in mit-scheme. – Beefcake

Answer 1

Modern incarnations of the Java Virtual Machine have extremely good performance when compared to interpreted languages. A significant amount of engineering resource has gone into the JVM, in particular the hotspot JIT compiler, highly tuned garbage collection and so on.

I suspect the difference you are seeing is primarily down to that. For example if you look Are the Java programs faster? you can see a comparison of java vs ruby which shows that java outperforms by a factor of 220 on one of the benchmarks.

You don't say what JVM options you are running your clojure benchmark with. Try running java with the -Xint flag which runs in pure interpreted mode and see what the difference is.

Also, it's possible that your example is too small to really warm-up the JIT compiler. Using a larger example may yield an even larger performance difference.

To give you an idea of how much Hotspot is helping you. I ran your code on my MBP 2011 (quad core 2.2Ghz), using java 1.6.0_31 with default opts (-server hotspot) and interpreted mode (-Xint) and see a large difference

; with -server hotspot (best of 10 runs)
>(time (reduce + 0 (sieve 5000000)))
"Elapsed time: 282.322 msecs"
838596693108

; in interpreted mode using -Xint cmdline arg
> (time (reduce + 0 (sieve 5000000)))
"Elapsed time: 3268.823 msecs"
838596693108

Autobahn

also, the clojure code is more specific about types. int-array is an array of ints, while scheme is stuck using tagged values, i imagine (i suspect that means that the scheme code supports larger values btw). but what struck me here is how much nicer the scheme code looks :o( - it would be nice to see if the clojure looked better once separate functions were pulled out. – Sukkah

@andrewcooke agreed - the clojure looks ugly here! – Autobahn

You're right, the difference was in iterpreted/compiled mode. After I compiled the mit-scheme code, it was running comparably fast. – Beefcake

Answer 2

As to comparing Scheme and Clojure code, there were a few things to simplify at the Clojure end:

• don't rebind the mutable array in loops;
• remove many of those explicit primitive coercions, no change in performance. As of Clojure 1.3 literals in function calls compile to primitives if such a function signature is available, and generally the difference in performance is so small that it gets quickly drowned by any other operations happening in a loop;
• add a primitive long annotation into the fn signature, thus removing the rebinding of n;
• call to Math/floor is not needed -- the int coercion has the same semantics.

Code:

(defn sieve [^long n]
 (let [root (int (Math/sqrt n))
       a (int-array n)]
   (loop [i 3, result (list 2)]
     (if (>= i n)
       (reverse result)
       (do
         (when (< i root)
           (loop [inc (+ i i), j (* i i)]
             (when (>= j n) (aset a j 1) (recur inc (+ j inc)))))
         (recur (+ i 2) (if (zero? (aget a i))
                          (conj result i)
                          result)))))))

Selfconfidence