为什么Clojure在执行相同函数时比mit-scheme更快？

Question

我在Clojure中找到了以下代码，用于筛选出前n个质数：

(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)))))))

接着，我用 Scheme（使用 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))))

定时结果如下： 对于Clojure：

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

对于mit-scheme：

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

有人可以告诉我为什么mit-scheme慢20多倍吗？

更新：“差异在于解释器/编译模式。在我编译 mit-scheme 代码后，它的运行速度相当快。- abo-abo Apr 30 '12 at 15:43”

- abo-abo

---

感谢您进行这种比较。我相信它有助于两种语言的发展。 - octopusgrabbus

我认为你的Scheme代码有误。特别是，make-vector将使用0填充向量，而在Scheme中它被视为true。将其更改为(make-vector n #f)会产生更合理的结果。 - Sam Tobin-Hochstadt

在MIT-Scheme中，(make-vector n)被填充为#f。 - abo-abo

Answer 1

现代版的Java虚拟机在性能上比解释性语言表现更好。许多工程资源都投入到了JVM中，尤其是优化的热点JIT编译器，高度调整的垃圾收集等等。

我认为你看到的差异主要是由此引起的。例如，如果你看一下Java和Ruby的比较Are the Java programs faster? ，你可以看到Java在其中的一个基准测试中超过了Ruby 220倍。

你没有说明你使用的Clojure基准测试的JVM选项是什么。尝试使用-Xint标志运行Java，这将以纯解释模式运行，并查看差异是什么。

另外，你的示例可能太小，无法真正启动JIT编译器。使用更大的示例可能会产生更大的性能差异。

让你了解Hotspot有多大帮助。我在我的MBP 2011（四核2.2Ghz）上运行了你的代码，使用java 1.6.0_31默认opts（-server hotspot）和解释模式（-Xint），并看到了很大的差异。

; 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

- sw1nn

---

另外，Clojure 代码更加特定于类型。 int-array 是一个整数数组，而 Scheme 使用标记值，我想象（我怀疑这意味着 Scheme 代码支持更大的值）。但是，让我印象深刻的是 Scheme 代码看起来更加清晰美观 :o( - 如果分离函数后 Clojure 代码看起来更好，那就太好了。 - andrew cooke

@andrewcooke同意 - 这里的Clojure看起来很丑！ - sw1nn

没错，区别在于解释器/编译器模式。我将mit-scheme代码编译后，运行速度相当快。 - abo-abo

Answer 2

关于比较Scheme和Clojure代码，Clojure端需要简化以下几点：

• 不要在循环中重新绑定可变数组；
• 删除许多显式原始类型强制转换，性能不受影响。从Clojure 1.3开始，如果函数签名可用，则函数调用中的字面量编译为原始类型，通常性能差异很小，会很快被循环中发生的任何其他操作所淹没；
• 在fn签名中添加一个原始long注释，从而消除了对n的重新绑定；
• 不需要调用Math/floor -- int强制转换具有相同的语义。

代码：

(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)))))))

- Marko Topolnik