Почему в Clojure вложенный цикл / повторение медленны?

Question

Один цикл / рекурс в Clojure выполняется так же быстро, как и Java для эквивалента цикла

Версия Clojure:

(defn singel-loop [i-count]
  (loop [i 0]
    (if (= i i-count)
      i
      (recur (inc i)))))

(time (loop-test 100101))
"Elapsed time: 0.8857 msecs"

Версия Java:

long s = System.currentTimeMillis();
for (i = 0; i < 100000; i++) {
}
System.out.println("Time: " + (System.currentTimeMillis() - s));

Время: ~ 1 мс

Однако, если вы добавите внутреннюю loop/recur, производительность абсолютно упадет с обрыва!

Clojure:

(defn double-loop [i-count j-count]
  (loop [i 0]
    (loop [j 0]
      (if (= j j-count)
        j
        (recur (inc j))))
      (if (= i i-count)
        i
        (recur (inc i)))))

(time (double-loop 100000 100000))
"Elapsed time: 70673.9189 msecs"

Java версия:

long s = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    for (int j = 0; j < 100000; j++) {
    }
}
System.out.println((System.currentTimeMillis() - s));

Время: ~ 3 мс

Почему производительность версии Clojureтанк в комичной степени, тогда как версия Java остается постоянной?

Answer 1

Вы заставили его выполнять в 100 000 раз больше работы, а теперь это занимает в 100 000 раз больше времени. Это не очень удивительно, и я бы не назвал это «падением с обрыва». Вы можете спросить, почему для выполнения Java-версии требуется в 3 раза больше времени, чем в 100 000 раз больше работы, но на данный момент вопрос о том, как в целом выполняется цикл / повторение, не имеет значения. Вместо этого вопрос в том, какое чудо JIT может осуществить с помощью кода Java.

Answer 2

Я думаю, это в первую очередь из-за того, что Java-код более открыт для оптимизации.

Согласно здесь :

Бесконечный цикл с пустымтело потребляет циклы процессора, но ничего не делает. Оптимизирующим компиляторам и системам «точно в срок» (JIT) разрешено (возможно, неожиданно) удалить такой цикл. Следовательно, программы не должны содержать бесконечные циклы с пустыми телами.

Хотя я не могу подтвердить такое утверждение. Код здесь также не включает бесконечные циклы, но пустые циклы независимо от условия выхода одинаково бесполезны. Во всяком случае, конечный цикл выглядит как более вероятная цель оптимизации, поскольку, по крайней мере, бесконечный цикл имеет потенциальную цель (блокировать на неопределенный срок).

Лучшим сравнением будет попытка устранить любую такую ​​оптимизацию. Я решил использовать System.out.flush, поскольку println может быть довольно дорогим и непоследовательным, и я не думаю, что что-то, что напрямую влияет на System.out., будет оптимизировано.

Вот результаты:

(defn double-loop [i-count j-count]
  (loop [i 0]
    (loop [j 0]
      (if (= j j-count)
        j
        (do
          (.flush System/out)
          (recur (inc j)))))

    (if (= i i-count)
      i

      (recur (inc i)))))

(time (double-loop 1000 10000))  ; "Elapsed time: 1194.718969 msecs"

---

public class HelloWorld {

     public static void main(String []args){
        long s = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < 10000; j++) {
                System.out.flush();
            }
        }

        System.out.println((System.currentTimeMillis() - s));  // 1097
     }
}

1194,718969 мс против 1097 мс

Таким образом, возможно, что Clojure не сможет скомпилировать в легко оптимизируемый код.

примечание:

• Я провел эти тесты на Tutorials Point , а не в реальной среде. IntelliJ был совершенно непригоден для меня со времени последнего обновления, и я, честно говоря, не испытывал желания создавать проект для Clojure и возиться с javac для Java.

• Почему именно этиномера? Потому что я работаю в плохой среде и не хочу, чтобы сайт душил меня или делал что-то подобное. По какой-то причине с тестом Clojure 10000x10000 зависало бесконечно (или, по крайней мере, превзошло мое терпение). Мне пришлось сбросить его до 10000x1000, чтобы оно закончилось.

• Как я заметил в комментариях к этому вопросу, это все еще ужасный способ для сравнения языков, которые работают на JVM, так какдело показывает красиво. Смотрите здесь почему. Я использую Критерий для Clojure. Это отличноОн запускает код перед тестами, чтобы все прогреть, и пытается обработать такие вещи, как сборка мусора.

Answer 3

Это должно поднять красные флажки для вас, если, как упоминалось ранее, версия с вложенным циклом Java, которая появляется из исходного кода и требует в 10 000 раз больше времени, чем не вложенный цикл, только в 3 раза больше времени. (~ 3 мс для вложенного цикла Java, против ~ 1 мс для не вложенного цикла). Я не знаю, почему это происходит, но есть несколько вариантов:

(a) JITM-компиляция JVM еще не запущена для вашей более короткой версии, так что все или большая часть временипотратил на интерпретацию байтового кода или выполнение менее оптимизированной версии машинного кода JIT по сравнению с версией вложенного цикла

(b) JIT JVM каким-то образом определяет, что ваши циклы не нужно запускать, потому чтоне возвращает значение, поэтому тот же эффект происходит независимо от того, запущены циклы или нет. В целом, я бы порекомендовал выполнить хотя бы немного вычислений в каждом внутреннем цикле (например, добавить два числа, например, к промежуточному итогу), и иметь возвращаемое значение, которое зависит от того, что происходит это вычисление.

Iздесь были созданы версии Clojure и Java с аналогичным временем выполнения, которые вы можете посмотреть, и записаны результаты измерений, которые я получил, используя библиотеку Criterium , которая много раз запускает один и тот же код, чтобы "прогреть"Сначала JIT, а затем измеряет его много раз после этого, сообщая о результатах только на основе выполнений после прогрева.

Java-код: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/java/JavaLoops.java

Код Clojure: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/clojure_loops.clj

Код измерения для обоих, с результатами в комментариях: https://github.com/jafingerhut/leeuwenhoek/blob/master/src/leeuwenhoek/measure_loops.clj