Perché Clojure è molto più veloce di mit-scheme per funzioni equivalenti?

Question

Ho trovato questo codice in Clojure al setaccio fuori primi N numeri primi:

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

Poi ho scritto l'equivalente (credo) il codice nello Schema (io uso 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)))) 

Il risultati temporizzazione sono: Per Clojure:

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

Per mit-schema:

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

Qualcuno può dirmi perché mit-scheme è più di 20 volte più lento?

Answer 1

Le moderne incarnazioni della Java Virtual Machine hanno prestazioni estremamente buone rispetto alle lingue interpretate. Una quantità significativa di risorse ingegneristiche è entrata nella JVM, in particolare il compilatore JIT di hotspot, la garbage collection altamente sintonizzata e così via.

Sospetto che la differenza che si sta vedendo sia principalmente dovuta a questo. Ad esempio, se si guarda Are the Java programs faster? è possibile vedere un confronto tra java e ruby ​​che mostra che java supera di un fattore 220 su uno dei benchmark.

Non si dice quali siano le opzioni JVM con cui si sta eseguendo il benchmark del clojure. Prova a eseguire java con il flag -Xint che viene eseguito in pura modalità interpretata e vedere qual è la differenza.

Inoltre, è possibile che il tuo esempio sia troppo piccolo per riscaldare davvero il compilatore JIT. L'utilizzo di un esempio più ampio potrebbe comportare una differenza di prestazioni ancora maggiore.

Per darti un'idea di quanto Hotspot ti sta aiutando. Ho fatto funzionare il codice sul mio MBP 2011 (Quad Core 2.2Ghz), utilizzando Java 1.6.0_31 con opta default (-server hotspot) e la modalità interpretato (-Xint) e vedere una grande differenza

; 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

Per quanto riguarda il confronto Schema e codice Clojure, c'erano alcune cose da semplificare alla fine Clojure:

• non riassociare la matrice mutabile nei loop;
• rimuovere molte di quelle esplicite coercizioni primitive, nessun cambiamento nelle prestazioni. A partire da Clojure 1.3 i letterali in funzione richiamano le primitive se tale firma di funzione è disponibile, e generalmente la differenza di prestazioni è così piccola che viene rapidamente annegata da qualsiasi altra operazione che si verifica in un ciclo;
• aggiunge una primitiva annotazione lunga nella firma fn, eliminando in tal modo la rebinding di n;
• call to Math/floor non è necessario - la coercizione int ha la stessa semantica.

Codice:

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