13

As a test for one of my classes, our teacher asked us to test a recursive and non-recursive approach to the famous Euclidean Algorithm:

Iterative

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

Recursive

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

And then I ran a test:

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

And then I ran the timers:

(test-recursive)

: 1.359128475189209 

(test-iterative)

: 1.7059495449066162

So my question is this, why did the recursive test perform faster than the iterative test? Isn't iterative almost always better than recursion? Is elisp an exception to this?

Improve this question

2 Answers 2

Reset to default
11

The theoretical answer is that the recursive version is actually tail recursive and thus should compile to iteration.

However, disassembling the functions reveals the truth:

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

vs

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

You can see that the gcdr has almost half as many instructions, but contains two call instructions, which means that ELisp does not, apparently, convert the tail recursive call to iteration. However, function calls in ELisp are relatively cheap and thus the recursive version executes faster.

PS. While the question makes sense, and the answer is actually generally applicable (e.g., the same approach is valid for Python and CLISP, inter alia), one should be aware that choosing the right algorithm (e.g., linearithmic merge-sort instead of quadratic bubble-sort) is much more important than "micro-optimizations" of the implementation.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

@tbf: thanks, fixed. I actually stared at the two call lines and could not figure out what they mean :-(
Note that it's not faster because of tail-call elimination because there is no tail-call elimination here: you can see the recursive call in the byte-code (from 8 it is push 'gcdr on the stack, push b, push 'mod on the stack, push a, push b, call 2 arg fn (which is mod a b), call 2 arg fn (which is (gcdr b <result of (mod a b)>))). The reason it's fast is because there is much less code and function call in elisp is fast relative to other operations.
nuked my earlier comment but left one describing the byte code as I think that's worth knowing.
4

Hmm... indeed that's weird, since Emacs's implementation of function calls (and hence recursion) is not very efficient.

I just evaluated the code below:

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

and then tried M-: (sm-test-recursive) and M-: (sm-test-iterative) and sure enough the iterative version is faster for me. I then did M-: (byte-compile 'sm-gcdi) and M-: (byte-compile 'sm-gcdr) and tried again, and the speed difference was even larger.

So your measurements come as a surprise to me: they don't match my expectations, and don't match my tests either.

Improve this answer

1 Comment

I can replicate Cameron Fife's original results with your recipe as well -- the recursive version is quicker. GNU Emacs 25.2.1 (x86_64-unknown-linux-gnu, X toolkit, Xaw scroll bars) of 2017-02-07. emacs -Q plus (require 'cl) for the loop code.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.