Clojure производительность очень плохая в простых циклах против Java

Предупреждение о спойлере, это проблема 5 Project Euler.

Я пытаюсь изучить Clojure и решить проблему 5, но на пару порядков медленнее (1515 мс в Java против 169932 мс в Clojure). Я даже пробовал использовать намеки типа, непроверенные математические операции и встроенные функции для всех.

Почему мой 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))))

Код 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;
  }
}

Ответы

Ответ 1

Некоторые проблемы с производительностью:

  • Вызов (range 2 20) создает новый ленивый список чисел для каждого приращения i. Это дорого, и вызывает много ненужного GC.
  • Вы делаете много бокса, проходя через вызовы функций. Даже (iterate inc 1) делает бокс/распаковку с каждым шагом.
  • Вы проходите последовательность делителей. Это медленнее, чем прямой итеративный цикл
  • mod на самом деле не очень хорошо оптимизированная функция в Clojure. Вам гораздо лучше использовать rem

Вы можете решить первую проблему, используя оператор let для определения диапазона только один раз:

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

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

Вы можете решить третью проблему, используя итеративный цикл над возможными делителями:

(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, с небольшим усилием. Основные трюки обычно:

  • Избегайте ленивых функциональных возможностей. Они приятны, но добавляют некоторые накладные расходы, что может быть проблематичным в низкоуровневом вычислительном коде.
  • Использовать примитивную/непроверенную математику
  • Используйте цикл /recur, а не последовательности
  • Убедитесь, что вы не делаете никакого отражения на объектах Java (т.е. (set! *warn-on-reflection* true) и устраняете все предупреждения, которые вы находите)

Ответ 2

Я не смог воспроизвести производительность 1500 мс. Код Clojure кажется в два раза быстрее, чем версия Java после компиляции в uberjar.

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

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

Я помещаю класс java в ресурсы /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));
    }

}

И в 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))))))

Даже в командной строке класс java не воспроизводит быструю скорость.

$ time java HasAllDivisors
  232792560
Elapsed time 4398

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