Aritmética rápida de números complejos en Clojure

Question

Estaba implementando aritmética de números complejos básicos en Clojure, y noté que era aproximadamente 10 veces más lenta que el código Java aproximadamente equivalente, incluso con sugerencias de tipo.

Compare:

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

de salida:

"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] }; 
} 

de salida:

Time taken: 6 millis 
Time taken: 6 millis 

De hecho, los consejos de tipo no parecen marcar la diferencia: si los elimino obtengo aproximadamente el mismo resultado. Lo que es realmente extraño es que si se me acaba el guión Clojure sin un REPL, consigo resultados más lentos:

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

Así que mis preguntas son: ¿Cómo puedo obtener cerca del rendimiento del código de Java? ¿Y por qué en la Tierra las expresiones tardan más en evaluarse cuando se ejecuta clojure sin un REPL?

ACTUALIZACIÓN ==============

Grande, utilizando deftype con notas de tipo en la deftype y en las defn s, y el uso de dotimes en lugar de repeatedly da un rendimiento tan bueno como o mejor que la versión de Java. Gracias a los dos.

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

Salida:

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

Las razones probables para su bajo rendimiento son: vectores

• Clojure son intrínsecamente estructuras de datos de más peso del doble matrices Java []. Así que tienes un poco de sobrecarga adicional en la creación y lectura de vectores.
• Usted está boxeo dobles como argumentos para sus funciones y también cuando se ponen en vectores. El boxeo/unboxing es relativamente caro en este tipo de código numérico de bajo nivel.
• Las sugerencias de tipo (^double) no te ayudan: aunque puedes tener sugerencias de tipo primitivo sobre las funciones Clojure normales, no funcionarán en los vectores.

Consulte este blog post on accelerating primitive arithmetic para obtener más detalles.

Si realmente desea que los números complejos rápidos en Clojure, es probable que necesite para ponerlas en práctica usando deftype, algo así como:

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

y luego definir todas las funciones complejas que utilizan este tipo. Esto le permitirá utilizar la aritmética primitiva en todas partes, y debería ser más o menos equivalente al rendimiento del código Java bien escrito.

Answer 2

• No sé mucho acerca de las pruebas de referencia, pero parece que necesita para calentar JVM cuando se inicia la prueba. Entonces cuando lo haces en REPL ya está calentado. Cuando se ejecuta como script todavía no es.

• En java ejecuta todos los bucles dentro de 1 método. No se llama a ningún otro método excepto plus y times. En clojure crea una función anónima y llama repetidamente para llamarlo. Lleva algo de tiempo. Puede reemplazarlo por dotimes.

Mi intento:

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

Resultados:

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"