Почему рекурсивная функция работает лучше, чем итеративная функция в elisp?

В качестве теста для одного из моих классов наш учитель попросил нас протестировать рекурсивный и нерекурсивный подход к известному евклидову алгоритму:

Итерационный

(defun gcdi (a b)
  (let ((x a) (y b) r)
    (while (not (zerop y))
      (setq r (mod x y) x y y r))
     x))

Рекурсивный

(defun gcdr (a b)
  (if (zerop b)
     a
     (gcdr b (mod a b))))

И затем я проверил тест:

(defun test-iterative ()
(setq start (float-time))
   (loop for x from 1 to 100000
     do (gcdi 14472334024676221 8944394323791464)) ; Fibonacci Numbers close to 2^64 >:)
 (- (float-time) start))

(defun test-recursive ()
(setq start (float-time))
   (loop for x from 1 to 100000
     do (gcdr 14472334024676221 8944394323791464)) ; Fibonacci Numbers close to 2^64 >:)
 (- (float-time) start))

И затем я запустил таймеры:

(test-recursive)

: 1.359128475189209

(test-iterative)

: 1.7059495449066162

Итак, мой вопрос в том, почему рекурсивный тест выполнялся быстрее, чем итеративный тест? Не итеративно ли почти всегда лучше рекурсии? Является ли elisp исключением?

Ответы

Ответ 1

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

Тем не менее, дизассемблирование функции раскрывают правду:

byte code for gcdi:
  args: (a b)
0       varref    a
1       varref    b
2       constant  nil
3       varbind   r
4       varbind   y
5       varbind   x
6       varref    y
7:1     constant  0
8       eqlsign   
9       goto-if-not-nil 2
12      constant  mod
13      varref    x
14      varref    y
15      call      2
16      varset    r
17      varref    y
18      varset    x
19      varref    r
20      dup       
21      varset    y
22      goto      1
25:2    varref    x
26      unbind    3
27      return

против

byte code for gcdr:
  args: (a b)
0       varref    b
1       constant  0
2       eqlsign   
3       goto-if-nil 1
6       varref    a
7       return    
8:1     constant  gcdr
9       varref    b
10      constant  mod
11      varref    a
12      varref    b
13      call      2
14      call      2
15      return

Вы можете видеть, что gcdr имеет почти наполовину столько инструкций, но содержит инструкции two call, что означает, что ELisp выполняет не, по-видимому, преобразовать хвостовой рекурсивный вызов в итерацию. Однако вызовы функций в ELisp относительно дешевы и поэтому рекурсивная версия выполняется быстрее.

PS. Хотя вопрос имеет смысл, и ответ на самом деле вообще применим (например, такой же подход применим для Python и CLISP, inter alia), следует знать, что выбор правильного алгоритма (например, linearithmic merge-sort вместо квадратичного пузырька -sort) гораздо важнее, чем "микро-оптимизации" реализации.

Ответ 2

Хм... действительно, это странно, так как реализация функций Emacs (и, следовательно, рекурсия) не очень эффективна.

Я просто оценил код ниже:

(defun sm-gcdi (a b)
  (let ((x a) (y b) r)
    (while (not (zerop y))
      (setq r (mod x y) x y y r))
    x))
(defun sm-gcdr (a b)
  (if (zerop b)
      a
    (sm-gcdr b (mod a b))))

(defun sm-test-iterative ()
  (let ((start (float-time)))
    (dotimes (_ 100000)
      (sm-gcdi 14472334024676221 8944394323791464))
    (- (float-time) start)))

(defun sm-test-recursive ()
  (let ((start (float-time)))
    (dotimes (_ 100000)
      (sm-gcdr 14472334024676221 8944394323791464))
    (- (float-time) start)))

а затем попробовали M-: (sm-test-recursive) и M-: (sm-test-iterative) и, конечно же, итеративная версия для меня быстрее. Затем я сделал M-: (byte-compile 'sm-gcdi) и M-: (byte-compile 'sm-gcdr) и попытался снова, а разность скоростей была еще больше.

Итак, ваши измерения стали для меня неожиданностью: они не соответствуют моим ожиданиям и не соответствуют моим тестам.