Разве хвостовая рекурсия не должна быть быстрее?

У меня есть следующий код Clojure для вычисления числа с определенным «факторизуемым» свойством. (что именно делает код - вторично).

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (factor-9 (quot n 10))))))

Теперь я в TCO и понимаю, что Clojure может обеспечить хвостовую рекурсию только в том случае, если это явно указано с помощью ключевого слова recur. Поэтому я переписал код для этого (заменив factor-9 на recur, являющимся единственным отличием):

(defn factor-9
  ([]
    (let [digits (take 9 (iterate #(inc %) 1))
          nums (map (fn [x] ,(Integer. (apply str x))) (permutations digits))]
      (some (fn [x] (and (factor-9 x) x)) nums)))
  ([n]
      (or
        (= 1 (count (str n)))
        (and (divisible-by-length n) (recur (quot n 10))))))

Насколько мне известно, TCO имеет двойную выгоду. Во-первых, он не использует стек так сильно, как вызов без хвостовой рекурсии, и, следовательно, не разрушает его при больших рекурсиях. Во-вторых, я думаю, что, следовательно, это быстрее, поскольку его можно преобразовать в цикл.

Теперь я сделал очень грубый тест и не увидел никакой разницы между двумя реализациями. Я ошибаюсь в своем втором предположении или это как-то связано с работой на JVM (у которой нет автоматической TCO) и recur с использованием трюка для ее достижения?

Спасибо.


clojure tail-recursion tail-call-optimization
person Balint Erdi    schedule 09.01.2011    source источник

Ответы (4)


arrow_upward
6
arrow_downward

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

Я бы также предложил использовать что-то вроде критерия при бенчмаркинге. (Переполнение стека не позволит мне опубликовать более одной ссылки, так как у меня нет репутации, о которой можно было бы говорить, поэтому вам придется погуглить, может быть, «критерий clojure»)

По причинам форматирования я поместил тесты и результаты в этот суть.

Вкратце, для относительного сравнения, если рекурсивный тест равен 1, то циклический тест составляет около 0,45, а тесты TCO — около 0,87, а абсолютная разница между рекурсивным тестом и тестом TCO составляет около 3 нс.

Разумеется, применимы все предостережения относительно сравнительного анализа.

person hutch    schedule 09.01.2011
comment
Это интересно, я настроил критерий для измерения коэффициента 9 и получил, что версия TCO на самом деле несколько медленнее, чем неоптимизированная версия. См. gist.github.com/773060. - person Balint Erdi; 10.01.2011
comment
Удивительно (по крайней мере, для меня :)) существует огромная разница при сравнении двух версий для простого вычисления Фибоначчи: gist.github.com/773068 - person Balint Erdi; 10.01.2011
comment
Это довольно драматично, не так ли? Радости ориентиров. По крайней мере, у вас есть убедительный аргумент, что совокупная стоимость владения имеет большое значение :-) - person hutch; 11.01.2011
comment
Подожди! Хотя они сильно отличаются, они не являются одним и тем же алгоритмом. Если вы замените «recur» на «fib» в fibo-toc, вы получите что-то намного более близкое по производительности. Рекурсивная версия ~1.37us, версия TCO ~1.32us. Как я уже сказал… радости бенчмаркинга :-) - person hutch; 11.01.2011
comment
Что ж, да, но если я заменю recur на fib, это больше не будет хвостовой рекурсией, поскольку в Clojure TCO активизируется явным указанием на это путем написания recur вместо имени функции. - person Balint Erdi; 13.01.2011
comment
Да это правильно. Проблема, на которую я плохо указал, заключается в том, что ваши fibo и fibo-toc реализуют два очень разных алгоритма. Если скопировать всю функцию fibo-toc, скажем, в fibo2, а затем заменить recur на fibo2 (в fibo2), то fibo2 больше не будет хвостовым вызовом, но разница в алгоритме между fibo-toc и fibo2 будет сведена к минимуму. Это делает их более сопоставимыми — единственное реальное различие теперь заключается в оптимизации хвостового вызова. И при использовании Criterium разница в производительности больше соответствует результатам, которые я впервые опубликовал. - person hutch; 13.01.2011

arrow_upward
2
arrow_downward

При оптимизации любого кода хорошо начинать с потенциальных или реальных узких мест и оптимизировать их в первую очередь.

Мне кажется, что именно этот фрагмент кода съедает большую часть вашего процессорного времени:

 (map (fn [x] ,(Integer. (apply str x))) (permutations digits))

И это никак не зависит от TCO - выполняется точно так же. Итак, tail call в данном конкретном примере позволит вам не израсходовать весь стек, а для достижения большей производительности попробуйте это оптимизировать.

person Goran Jovic    schedule 09.01.2011
comment
Я не думаю, что ответ правильный. Во-первых, перестановки дают ленивую последовательность, так что оценка (некоторых...) запускает вычисление перестановок только по мере необходимости. Во-вторых, в зависимости от поведения фактора-9 во время выполнения это может иметь значение или нет. С другой стороны, ваш общий совет по анализу что оптимизировать является правильным. Если функциональный фактор-9 является узким местом, вопрос о совокупной стоимости владения или нет зависит только от размера стека и производительности во время выполнения. - person ordnungswidrig; 09.01.2011
comment
@ordnungswidrig: Вполне возможно. Не имея возможности запустить код, я просто выбрал самый подозрительный фрагмент. Я подожду отзыва от Балинта, а затем отредактирую его по мере необходимости. Совет по выявлению узких мест применим для любой проблемы оптимизации кода. - person Goran Jovic; 09.01.2011
comment
Горан, я думаю, что ordnungswidrig верен, перестановки будут извлекаться по мере необходимости, но знаете ли вы о профилировщике, который закрывает clojure, с помощью которого я могу проверить это предположение? - person Balint Erdi; 13.01.2011

arrow_upward
1
arrow_downward

просто нееврейское напоминание о том, что у clojure нет совокупной стоимости владения

person Arthur Ulfeldt    schedule 09.01.2011
comment
JVM, на которой работает Clojure, не имеет автоматической TCO, но ее можно заставить делать это для саморекурсии и при явном указании этого с помощью recur - person Balint Erdi; 10.01.2011
comment
нет, у него есть циклическая конструкция, называемая recur. синтаксически он напоминает хвостовой вызов, хотя это не так, потому что его можно использовать как для циклов, так и для функций. - person Arthur Ulfeldt; 10.01.2011
comment
+1 за то, что он единственный, кто указал на это. Я бы также добавил, что обсуждения здесь относятся к подмножеству хвостовых вызовов, которые recur может обрабатывать Clojure, и не применимы к оптимизации хвостовых вызовов в целом. - person J D; 14.04.2012

arrow_upward
-1
arrow_downward

После оценки factor-9 (quot n 10) необходимо оценить and и or, прежде чем функция сможет вернуться. Таким образом, это не хвостовая рекурсия.

person Oswald    schedule 09.01.2011
comment
Если только and и or в clojure не действуют иначе, чем в других lisps (в чем я сомневаюсь), это неправда. (and x y) должно быть эквивалентно (if x y false), а (or x y) — (if x true y), поэтому y в обоих случаях находится в хвостовой позиции. - person sepp2k; 09.01.2011
comment
@sepp2k sepp2k Это означает, что программу можно преобразовать в эквивалентную программу с хвостовой рекурсией. Но делает ли это саму программу хвостовой рекурсией? Если да, то как я могу проголосовать за свой ответ? - person Oswald; 09.01.2011
comment
Поскольку макрорасширение происходит во время компиляции и после макрорасширения у вас есть программа с хвостовой рекурсией, да, это делает программу хвостовой рекурсией. Кроме того: если вы используете recur в позиции, которая не является хвостом, вы фактически получите ошибку. Вы не можете понизить свой ответ, но вы можете удалить его, щелкнув ссылку «Удалить», которая находится между телом вашего ответа и комментариями. - person sepp2k; 09.01.2011