간단한 루프 대 Java에서 Clojure 성능이 매우 낮습니다

Question

Spoiler 경고, 이것이 Project Euler의 문제 5입니다.

나는 Clojure를 배우려고하고 문제 5를 해결하려고 시도하고 있지만, Clojure의 경우 Java에서 1515ms 대 169932ms보다 느리다. 나는 타입 힌팅, 검사되지 않은 수학 연산, 그리고 아무 것도없는 모든 함수를 인라이닝하려고했습니다.

왜 Clojure 코드가 그렇게 느린 거죠?

의 Clojure 코드 :

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

자바 코드 :

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

일부 성능 문제 다음 (range 2 20) 호출 i의 모든 증가를 위해 숫자의 새로운 게으른 목록을 작성한다

• . 이것은 비용이 많이 들고 불필요한 GC가 많이 발생합니다.
• 당신은 함수 호출을 통과하여 많은 권투를하고 있습니다. (iterate inc 1)조차도 모든 증분에서 복싱/언 박싱을하고 있습니다.
• 일련의 제수를 순회 중입니다. 이것은 똑 바른 반복 루프보다 느립니다.
• mod은 현재 Clojure에서 실제로 매우 잘 최적화 된 함수가 아닙니다.

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

  당신은 루프/RECUR와 두 번째 문제를 해결 할 수 있습니다 : 당신은 당신이 한 번만 범위를 정의하는 let 문을 사용하여 첫 번째 문제를 해결할 수 rem

을 개시 훨씬 더 나은

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

넌 가능한 제수 통해 반복 루프를 사용하여 세 번째 문제를 해결할 수

,691,363 (210)

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

당신은 당신이 볼 수 있듯이 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" 

사용하여 최종 문제를 해결할 수 있습니다, 지금은 Java 버전 경쟁력이다.

일반적으로 일반적으로 Clojure는 Java만큼 빠르게 작업 할 수 있습니다. 주요 트릭은 대개 다음과 같습니다.

• 게으른 기능을 피하십시오. 그것들은 멋지지만 저수준의 계산 집약적 인 코드에서 문제가되는 오버 헤드를 추가합니다.
• 를 사용하여 원시/체크되지 않은 수학
• 사용 루프/
• 당신이 자바 객체에 어떤 반사를 수행하지 않는 확인합니다 (예 : (set! *warn-on-reflection* true)을하고 찾을 모든 경고 제거)

Answer 2

내가하지 않은를 순서보다는 재발 1500ms 성능을 재현 할 수있었습니다.Clojure 코드는 uberjar 컴파일 후 실제로 Java 버전보다 두 배 빠릅니다.

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

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

나는 심지어 자바 클래스는 빠른 속도의 재생되지 않는 명령 행에

(time (prn (HasAllDivisors/findMinimumWithAllDivisors))) 

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

Clojure의

에

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

} 

그리고 HasAllDivisors.java

/자원 자바 클래스를 넣어.

$ time java HasAllDivisors 
    232792560 
Elapsed time 4398 

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