Aritmetica di numeri complessi veloci in Clojure

Question

Stavo implementando alcuni aritmetici di numeri complessi di base in Clojure e ho notato che era circa 10 volte più lento di un codice Java approssimativamente equivalente, anche con suggerimenti tipo.

Confronta:

(defn plus [[^double x1 ^double y1] [^double x2 ^double y2]] 
    [(+ x1 x2) (+ y1 y2)]) 

(defn times [[^double x1 ^double y1] [^double x2 ^double y2]] 
    [(- (* x1 x2) (* y1 y2)) (+ (* x1 y2) (* y1 x2))]) 

(time (dorun (repeatedly 100000 #(plus [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 

uscita:

"Elapsed time: 69.429796 msecs" 
"Elapsed time: 72.232479 msecs" 

con:

public static void main(String[] args) { 
    double[] z1 = new double[] { 1, 0 }; 
    double[] z2 = new double[] { 0, 1 }; 
    double[] z3 = null; 

    long l_StartTimeMillis = System.currentTimeMillis(); 
    for (int i = 0; i < 100000; i++) { 
    z3 = plus(z1, z2); // assign result to dummy var to stop compiler from optimising the loop away 
    } 
    long l_EndTimeMillis = System.currentTimeMillis(); 
    long l_TimeTakenMillis = l_EndTimeMillis - l_StartTimeMillis; 
    System.out.format("Time taken: %d millis\n", l_TimeTakenMillis); 


    l_StartTimeMillis = System.currentTimeMillis(); 
    for (int i = 0; i < 100000; i++) { 
    z3 = times(z1, z2); 
    } 
    l_EndTimeMillis = System.currentTimeMillis(); 
    l_TimeTakenMillis = l_EndTimeMillis - l_StartTimeMillis; 
    System.out.format("Time taken: %d millis\n", l_TimeTakenMillis); 

    doNothing(z3); 
} 

private static void doNothing(double[] z) { 

} 

public static double[] plus (double[] z1, double[] z2) { 
    return new double[] { z1[0] + z2[0], z1[1] + z2[1] }; 
} 

public static double[] times (double[] z1, double[] z2) { 
    return new double[] { z1[0]*z2[0] - z1[1]*z2[1], z1[0]*z2[1] + z1[1]*z2[0] }; 
} 

uscita:

Time taken: 6 millis 
Time taken: 6 millis 

In effetti, i suggerimenti tipo non sembrano fare la differenza: se li rimuovo ottengo circa lo stesso risultato. La cosa veramente strana è che se faccio funzionare lo scritto Clojure senza un REPL, ottengo risultati più lenti:

"Elapsed time: 137.337782 msecs" 
"Elapsed time: 214.213993 msecs" 

Quindi le mie domande sono: come posso ottenere vicino alle prestazioni del codice Java? E perché sulla Terra le espressioni impiegano più tempo per valutare quando si esegue il clojure senza un REPL?

UPDATE ==============

Grande, utilizzando deftype con tipo suggerimenti nel deftype e nelle defn s, e l'utilizzo di dotimes piuttosto che repeatedly offre prestazioni buone come o meglio della versione Java. Grazie a tutti e due.

(deftype complex [^double real ^double imag]) 

(defn plus [^complex z1 ^complex z2] 
    (let [x1 (double (.real z1)) 
     y1 (double (.imag z1)) 
     x2 (double (.real z2)) 
     y2 (double (.imag z2))] 
    (complex. (+ x1 x2) (+ y1 y2)))) 

(defn times [^complex z1 ^complex z2] 
    (let [x1 (double (.real z1)) 
     y1 (double (.imag z1)) 
     x2 (double (.real z2)) 
     y2 (double (.imag z2))] 
    (complex. (- (* x1 x2) (* y1 y2)) (+ (* x1 y2) (* y1 x2))))) 

(println "Warm up") 
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1))))) 

(println "Try with dorun") 
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1))))) 
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1))))) 

(println "Try with dotimes") 
(time (dotimes [_ 100000] 
     (plus (complex. 1 0) (complex. 0 1)))) 

(time (dotimes [_ 100000] 
     (times (complex. 1 0) (complex. 0 1)))) 

uscita:

Warm up 
"Elapsed time: 92.805664 msecs" 
"Elapsed time: 164.929421 msecs" 
"Elapsed time: 23.799012 msecs" 
"Elapsed time: 32.841624 msecs" 
"Elapsed time: 20.886101 msecs" 
"Elapsed time: 18.872783 msecs" 
Try with dorun 
"Elapsed time: 19.238403 msecs" 
"Elapsed time: 17.856938 msecs" 
Try with dotimes 
"Elapsed time: 5.165658 msecs" 
"Elapsed time: 5.209027 msecs" 

Answer 1

Le ragioni probabili per il vostro rallentamento delle prestazioni sono: vettori

• Clojure sono intrinsecamente strutture dati più pesanti di Java doppie [] array. Quindi hai un po 'di overhead in più nella creazione e nella lettura di vettori.
• La boxe funge da argomento per le tue funzioni e anche quando vengono inserite nei vettori. Boxing/Unboxing è relativamente costoso in questo tipo di codice numerico di basso livello.
• I tipi di suggerimenti (^double) non sono di aiuto: mentre è possibile avere suggerimenti di tipo primitivo sulle normali funzioni di Clojure, non funzioneranno sui vettori.

Vedere questo blog post on accelerating primitive arithmetic per ulteriori dettagli.

Se si vuole veramente i numeri complessi veloci in Clojure, si avrà probabilmente bisogno per la loro attuazione tramite deftype, qualcosa come:

(deftype Complex [^double real ^double imag]) 

E poi definire tutte le funzioni complesse che utilizzano questo tipo. Ciò consentirà di utilizzare l'aritmetica primitiva in tutto e dovrebbe essere approssimativamente equivalente alle prestazioni del codice Java ben scritto.

Answer 2

• Non so molto di test di benchmark, ma sembra che avete bisogno per riscaldarsi JVM quando si avvia test. Quindi quando lo fai in REPL è già scaldato. Quando si esegue come script non è ancora.

• In java si eseguono tutti i cicli all'interno di 1 metodo. Nessun altro metodo tranne plus e times viene chiamato. In Clojure crei una funzione anonima e chiami ripetutamente per chiamarla. Ci vuole un po 'di tempo. È possibile sostituirlo con dotimes.

Il mio tentativo:

(println "Warm up") 
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 

(println "Try with dorun") 
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1])))) 
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 

(println "Try with dotimes") 
(time (dotimes [_ 100000] 
     (plus [1 0] [0 1]))) 

(time (dotimes [_ 100000] 
     (times [1 0] [0 1]))) 

Risultati:

Warm up 
"Elapsed time: 367.569195 msecs" 
"Elapsed time: 493.547628 msecs" 
"Elapsed time: 116.832979 msecs" 
"Elapsed time: 46.862176 msecs" 
"Elapsed time: 27.805174 msecs" 
"Elapsed time: 28.584179 msecs" 
Try with dorun 
"Elapsed time: 26.540489 msecs" 
"Elapsed time: 27.64626 msecs" 
Try with dotimes 
"Elapsed time: 7.3792 msecs" 
"Elapsed time: 5.940705 msecs"