Сравнение скорости вычисления факториала на Scheme и Common Lisp

Scheme

Рекурсивное вычисление факториала на Scheme:

(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))

(fact 20000)

Итеративное вычисление факториала на Scheme:

(define (fact n)
(fact-iter 1 n))

(define (fact-iter val counter)
(if (= counter 0)
val
(fact-iter (* val counter) (- counter 1))))

Теперь создаём две программы, в первой из которых определяется рекурсивный вариант функции вычисления факториала, а во второй - итеративный. Добавляем в каждый из файлов вычисление факториала 20000:

(= 1 (fact 20000))

Я намеренно добавил сравнение результата вычисления с единицей, дабы избежать потерь времени на перевод числа в десятичную систему и вывод результата на экран.

Запускаем обе программы следующим образом и получаем время выполнения каждой из них:

time mit-scheme < fact.scheme > /dev/null ; time mit-scheme < fact2.scheme > /dev/null

real    0m3.760s
user    0m3.712s
sys     0m0.048s

real    0m3.379s
user    0m3.344s
sys     0m0.036s

То было на MIT'овской реализации, а теперь попробуем на PLT:

time plt-r5rs < fact.scheme > /dev/null ; time plt-r5rs < fact2.scheme > /dev/null

real    0m1.363s
user    0m1.256s
sys     0m0.108s

real    0m1.235s
user    0m1.152s
sys     0m0.080s

Рекурсивный код оказался немного быстрее в обоих случаях. Реализация PLT обгоняет MIT'овскую на этой задаче.

Common Lisp

Рекурсивное вычисление факториала на Common Lisp:

(defun fact (n)
(if (eql n 0)
1
(* n (fact (- n 1)))))

(fact 20000)

Итеративное вычисление факториала в Common Lisp. Процесс вычисления факториала происходит итеративно за счёт применения в компиляторе оптимизации хвостовой рекурсии:

(defun fact (n)
(fact-iter 1 n))

(defun fact-iter (val counter)
(if (eql counter 0)
val
(fact-iter (* val counter) (- counter 1))))

(fact 20000)

Программа для сравнения рекурсивного и итеративного вариантов вычисления факториала:

;;; Итеративное вычисление факториала.
;;; Ожидается именно итеративное вычисление за счёт возможности
;;; применить хвостовую рекурсию
(defun fact (n)
(fact-iter 1 n))

(defun fact-iter (val counter)
(if (eql counter 0)
val
(fact-iter (* val counter) (- counter 1))))

;;; Рекурсивное вычисление факториала.
(defun fact2 (n)
(if (eql n 0)
1
(* n (fact2 (- n 1)))))

;;;; Пробуем сравнить оба варианта вычисления по идентичности полученного
;;;; результата и времени выполнения
(eql (time (fact 20000))
(time (fact2 20000)))

(quit)

Здесь сравнивая результаты вычисления между собой я одновременно выполняю правильность обеих функций и избегаю перевода результатов вычислений в десятичную систему и вывода результатов на экран.

Результат выполнения программы:

Evaluation took:
0.408 seconds of real time
0.408026 seconds of total run time (0.392025 user, 0.016001 system)
[ Run times consist of 0.040 seconds GC time, and 0.369 seconds non-GC time. ]
100.00% CPU
819,948,580 processor cycles
339,303,792 bytes consed
Evaluation took:
0.383 seconds of real time
0.380023 seconds of total run time (0.376023 user, 0.004000 system)
[ Run times consist of 0.072 seconds GC time, and 0.309 seconds non-GC time. ]
99.22% CPU
769,179,220 processor cycles
303,251,800 bytes consed
T

Рекурсивный вариант оказался немного быстрее. Код тестировался на реализации SBCL, которая компилирует программу в машинный код платформы x86. Есть ещё реализация CMUCL, являющаяся предком SBCL, она компилирует программу в код собственной виртуальной машины. Не стоит говорить, что SBCL оказался быстрее, чем CMUCL.

Какие из всего этого можно сделать выводы? Либо в этих компиляторах оптимизация хвостовой рекурсии не выполняется, и поэтому итеративные функции показывают сравнимое и даже большее время вычисления, либо оптимизация выполняется настолько качественно, что компилятору удаётся свести рекурсивные функции к итеративным.