¿Por qué Clojure es mucho más rápido que mit-scheme para funciones equivalentes?

Question

me encontré con este código en Clojure a cribar primeros n números primos:

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

Entonces escribí el equivalente (creo) el código en el esquema (I utilizará MIT-esquema)

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

El de temporización resultados son: Para Clojure:

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

Para mit-esquema:

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

¿Alguien puede decirme por qué mit-scheme es más de 20 veces más lento?

Answer 1

Las encarnaciones modernas de la Máquina Virtual de Java tienen un rendimiento extremadamente bueno en comparación con los idiomas interpretados. Se ha ingresado una cantidad significativa de recursos de ingeniería en la JVM, en particular el compilador JIT del punto de conexión, la recolección de basura altamente ajustada, y así sucesivamente.

Sospecho que la diferencia que está viendo se debe principalmente a eso. Por ejemplo, si mira Are the Java programs faster?, puede ver una comparación de java vs ruby ​​que muestra que java tiene un rendimiento superior a 220 en uno de los puntos de referencia.

No dice con qué opciones de JVM está ejecutando su benchmark clojure. Intente ejecutar java con el indicador -Xint que se ejecuta en modo interpretado puro y vea cuál es la diferencia.

Además, es posible que su ejemplo sea demasiado pequeño para realmente calentar el compilador JIT. Usar un ejemplo más grande puede producir una diferencia de rendimiento aún mayor.

Para hacerte una idea de la cantidad de Hotspot que te está ayudando. Me encontré con su código en mi MBP 2011 (Quad Core 2.2Ghz), el uso de Java 1.6.0_31 con opta por defecto (punto de acceso) y -server modo interpretado (-Xint) y ver una gran diferencia

; 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 

Answer 2

En cuanto a la comparación de Código Scheme y Clojure, hubo algunas cosas para simplificar en el extremo de Clojure:

• No vuelva a enlazar la matriz mutable en bucles;
• eliminan muchas de esas coacciones primitivas explícitas, sin cambios en el rendimiento. A partir de Clojure 1.3 los literales en las llamadas a funciones compilan primitivas si dicha firma de función está disponible, y generalmente la diferencia en el rendimiento es tan pequeña que se ahoga rápidamente por cualquier otra operación que ocurra en un ciclo;
• agrega una anotación larga primitiva en la firma fn, eliminando así la reenlace de n;
• no es necesario llamar a Matemáticas/piso - la coerción int tiene la misma semántica.

Código:

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