Clojure wydajność naprawdę źle na prostej pętli versus Java

Question

Alert spoiler, jest to problem 5 Project Euler.

Próbuję nauczyć się Clojure i rozwiązać problem 5, ale jest to kilka rzędów wielkości wolniejsze (1515 ms w Javie w porównaniu z 169932 ms w Clojure). Próbowałem nawet używać podpowiedzi typu, niezaznaczonych operacji matematycznych i funkcji inliningowych na nic.

Dlaczego mój kod Clojure jest znacznie wolniejszy? Kod

Clojure:

kod

(set! *unchecked-math* true) 
(defn divides? [^long number ^long divisor] (zero? (mod number divisor))) 

(defn has-all-divisors [divisors ^long num] 
    (if (every? (fn [i] (divides? num i)) divisors) num false)) 

(time (prn (some (fn [^long i] (has-all-divisors (range 2 20) i)) (iterate inc 1)))) 

Java:

public class Problem5 { 
    public static void main(String[] args) { 
    long start = System.currentTimeMillis(); 
    int i = 1; 
    while(!hasAllDivisors(i, 2, 20)) { 
     i++; 
    } 
    long end = System.currentTimeMillis(); 
    System.out.println(i); 
    System.out.println("Elapsed time " + (end - start)); 
    } 

    public static boolean hasAllDivisors(int num, int startDivisor, int stopDivisor) { 
    for(int divisor=startDivisor; divisor<=stopDivisor; divisor++) { 
     if(!divides(num, divisor)) return false; 
    } 
    return true; 
    } 

    public static boolean divides(int num, int divisor) { 
    return num % divisor == 0; 
    } 
} 

Answer 1

Niektóre problemy z wydajnością:

• (range 2 20) połączenia jest stworzenie nowego leniwe listę numerów dla każdego przyrostu i . Jest to kosztowne i powoduje dużo niepotrzebnego GC.
• Wykonujesz wiele boksów, przechodząc przez wywołania funkcji. Nawet (iterate inc 1) wykonuje boksowanie/rozpakowywanie z każdym przyrostem.
• Przechodzisz przez sekwencję dzielników. Jest wolniejszy niż prosta iteracyjna pętla, która obecnie nie jest właściwie dobrze zoptymalizowaną funkcją w Clojure. Jesteś o wiele lepiej wyłączyć za pomocą rem

można rozwiązać pierwszy problem za pomocą let oświadczenie określić zakres tylko raz:

(time (let [rng (range 2 20)] 
    (prn (some (fn [^long i] (has-all-divisors rng i)) (iterate inc 1))))) 
=> "Elapsed time: 48863.801522 msecs" 

można rozwiązać drugi problem z pętli/nawrotu:

(time (let [rng (range 2 20) 
      f (fn [^long i] (has-all-divisors rng i))] 
     (prn (loop [i 1] 
       (if (f i) 
       i 
       (recur (inc i))))))) 
=> "Elapsed time: 32757.594957 msecs" 

można rozwiązać trzeci problem, korzystając z pętli iteracyjnej nad możliwych dzielników:

(defn has-all-divisors [^long num] 
    (loop [d (long 2)] 
    (if (zero? (mod num d)) 
     (if (>= d 20) true (recur (inc d))) 
     false))) 

(time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i)))))) 
=> "Elapsed time: 13369.525651 msecs" 

można rozwiązać problemu przy użyciu ostatecznej rem

(defn has-all-divisors [^long num] 
    (loop [d (long 2)] 
    (if (== 0 (rem num d)) 
     (if (>= d 20) true (recur (inc d))) 
     false))) 

(time (prn (loop [i (long 1)] (if (has-all-divisors i) i (recur (inc i)))))) 
=> "Elapsed time: 2423.195407 msecs" 

Jak widać, jest obecnie konkurencyjna w stosunku do wersji Java.

Ogólnie rzecz biorąc, zazwyczaj można zrobić Clojure prawie tak szybko, jak Java przy odrobinie wysiłku. Główne triki to zazwyczaj:

• Unikaj leniwych funkcji funkcjonalnych. Są ładne, ale dodają trochę narzutów, co może być problematyczne w przypadku kodu wymagającego wysokiego poziomu obliczeń.
• Stosować prymitywne/niesprawdzonych matematyka
• Zastosowanie pętli/powtarzać zamiast sekwencji
• Upewnić się, że nie robią żadnej refleksji na obiektach Javy (tj (set! *warn-on-reflection* true) i wyeliminować wszystkie ostrzeżenia Państwo znaleźć)

Answer 2

nie mam udało się odtworzyć wydajność 1500 ms.Kod Clojure wydaje się faktycznie dwa razy szybszy niż wersja Java po kompilacji do uberjar.

Now timing Java version 
    232792560 
"Elapsed time: 4385.205 msecs" 

Now timing Clojure version 
    232792560 
"Elapsed time: 2511.916 msecs" 

kładę klasy Javy w zasobach/HasAllDivisors.java

public class HasAllDivisors { 

    public static long findMinimumWithAllDivisors() { 
     long i = 1; 
     while(!hasAllDivisors(i,2,20)) i++; 
     return i; 
    } 

    public static boolean hasAllDivisors(long num, int startDivisor, int stopDivisor) { 
     for(int divisor = startDivisor; divisor <= stopDivisor; divisor++) { 
      if(num % divisor > 0) return false; 
     } 
     return true; 
    } 

    public static void main(String[] args){ 
     long start = System.currentTimeMillis(); 
     long i = findMinimumWithAllDivisors(); 
     long end = System.currentTimeMillis(); 
     System.out.println(i); 
     System.out.println("Elapsed time " + (end - start)); 
    } 

} 

A w Clojure

(time (prn (HasAllDivisors/findMinimumWithAllDivisors))) 

(println "Now timing Clojure version") 
(time 
    (prn 
     (loop [i (long 1)] 
      (if (has-all-divisors i) 
       i 
       (recur (inc i)))))) 

Nawet w wierszu poleceń klasy Javy nie jest odtwarzającego szybkosci.

$ time java HasAllDivisors 
    232792560 
Elapsed time 4398 

real 0m4.563s 
user 0m4.597s 
sys 0m0.029s