Cosa sta rallentando questa funzione Clojure?

Question

Sto lavorando su Project Euler problem 14 in Clojure. Ho quello che ritengo sia un buon algoritmo generale, e sto ottenendo il risultato corretto, ma sto facendo fatica a capire perché la mia funzione è così lenta rispetto a (quello che credo sia) una funzione equivalente in Java. Ecco la mia funzione di Clojure per ottenere la lunghezza della catena Collatz da un dato numero di partenza:

(defn collatz-length 
    [n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (even? x) 
       (/ x 2) 
       (inc (* 3 x))) 
      (inc acc))))) 

Ed ecco la mia funzione di Java per fare la stessa cosa:

public static int collatzLength(long x) { 
    int count = 0; 
    while (x > 1) { 
     if ((x % 2) == 0) { 
      x = x/2; 
     } else { 
      x = (x * 3) + 1; 
     } 
     count++; 
    } 
    return count; 
} 

Per tempo le prestazioni di queste funzioni , ho usato il seguente codice Clojure:

(time (dorun (map collatz-length (range 1 1000000)))) 

E il seguente codice Java:

long starttime = System.currentTimeMillis(); 

int[] nums = new int[1000000]; 
for (int i = 0; i < 1000000; i++) { 
    nums[i] = collatzLength(i+1); 
} 

System.out.println("Total time (ms) : " + (System.currentTimeMillis() - starttime)); 

Il codice Java viene eseguito nella macchina 304 ms, ma il codice Clojure richiede 4220 ms. Che cosa sta causando questo collo di bottiglia e come posso migliorare le prestazioni del mio codice Clojure?

Answer 1

Si sta utilizzando la matematica in box in modo che i numeri siano costantemente in box e unboxed. Provare qualcosa di simile:

(set! *unchecked-math* true) 
(defn collatz-length 
    ^long [^long n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (zero? (rem x 2)) 
       (quot x 2) 
       (inc (* 3 x))) 
      (inc acc))))) 
(time (dorun (loop [i 1] (when (< i 1000000) (collatz-length i) (recur (inc i)))))) 

Answer 2

in base alla risposta di Alex, è possibile accelerare le cose un po 'più da inlining la chiamata a even? (tale funzione non supporta numeri interi unboxed):

(defn collatz-length 
    ^long [^long n] 
    (loop [x n acc 1] 
    (if (= 1 x) 
     acc 
     (recur (if (zero? (bit-and x 1)) 
       (quot x 2) 
       (inc (* 3 x))) 
      (inc acc))))) 

Per riferimento , https://www.refheap.com/cfd421430653cf786177f3cfe è il bytecode prodotto dal metodo java (modificato per utilizzare long anziché int) e il bytecode prodotto dalla funzione clojure. Sembrano molto, molto simili, ad eccezione di una stanza introduttiva in cui la versione clojure copia l'argomento di input n in x, dove la versione java sovrascrive il n esistente.