Pourquoi Clojure est-il beaucoup plus rapide que mit-scheme pour des fonctions équivalentes ?

Question

J'ai trouvé ce code dans Clojure pour trier en premier lieu n des nombres premiers :

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

J'ai ensuite écrit le code équivalent (je pense) en Scheme (j'utilise 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))))

Les résultats du chronométrage sont : Pour Clojure :

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

Pour mit-scheme :

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

Quelqu'un peut-il me dire pourquoi mit-scheme est plus de 20 fois plus lent ?

mise à jour : "la différence était en mode iterprété/compilé. Après avoir compilé le code de mit-scheme, il s'exécutait à une vitesse comparable. - abo-abo 30 avr. 12 à 15:43 "

Answer 1

Les incarnations modernes de la machine virtuelle Java ont des performances extrêmement bonnes par rapport aux langages interprétés. Une quantité importante de ressources d'ingénierie a été consacrée à la JVM, en particulier le compilateur JIT très performant, la collecte de déchets hautement optimisée, etc.

Je pense que la différence que vous constatez est principalement due à cela. Par exemple, si vous regardez Les programmes Java sont-ils plus rapides ? vous pouvez voir une comparaison entre java et ruby qui montre que java surpasse par un facteur de 220 sur l'un des benchmarks.

Vous ne dites pas avec quelles options JVM vous exécutez votre benchmark clojure. Essayez d'exécuter java avec l'option -Xint qui s'exécute en mode interprété pur et voir quelle est la différence.

De plus, il est possible que votre exemple soit trop petit pour que le compilateur JIT puisse vraiment s'échauffer. L'utilisation d'un exemple plus grand peut produire une différence de performance encore plus grande.

Pour vous donner une idée de l'aide que vous apporte Hotspot. J'ai exécuté votre code sur mon MBP 2011 (quad core 2.2Ghz), en utilisant java 1.6.0_31 avec les options par défaut (-server hotspot) et le mode interprété (-Xint) et je vois une grande différence.

; 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

Pour ce qui est de la comparaison des codes Scheme et Clojure, il y avait quelques éléments à simplifier du côté de Clojure :

• ne pas relier le tableau mutable dans les boucles ;
• supprimer un grand nombre de ces coercitions primitives explicites, aucun changement dans les performances. Depuis Clojure 1.3, les littéraux dans les appels de fonction sont compilés en primitives si une telle signature de fonction est disponible, et généralement la différence de performance est si faible qu'elle est rapidement noyée par toute autre opération se produisant dans une boucle ;
• ajouter une annotation primitive longue dans la signature de fn, supprimant ainsi la ré-liaison de n ;
• L'appel à Math/floor n'est pas nécessaire -- la coercition int a la même sémantique.

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