Comparison of recursive vs iterative performance in various Lisp family languages

recursive-iterative-performance.md

Comparison of recursive vs iterative performance in various Lisp family languages

WARNING: These are very crude tests. Note in particular that I should really average times over about fifty runs, because they do vary; and I have not done this.

common lisp (sbcl)

Recursive performance in Common Lisp is very good — better on this test than iterative performance, which surprises me. Note that the iterative algorithm takes about one third more processor cycles, and slightly more store.

(defun fact (n)
      "Compute the factorial of `n`, expected to be a natural number."
      (cond ((= n 1) 1)
        (t (* n (fact (- n 1))))))

(time (fact 1000))

; CL-USER[2]: (time (fact 1000))
; Evaluation took:
;   0.000 seconds of real time
;   0.000159 seconds of total run time (0.000131 user, 0.000028 system)
;   100.00% CPU
;   545,685 processor cycles
;   518,880 bytes consed

(time (apply #'* (alexandria:iota 1000 :start 1 :step 1)))

; CL-USER[5]: (time (apply #'* (alexandria:iota 1000 :start 1 :step 1)))
; Evaluation took:
;   0.000 seconds of real time
;   0.000259 seconds of total run time (0.000259 user, 0.000000 system)
;   100.00% CPU
;   899,360 processor cycles
;   552,544 bytes consed

clojure

Clojure depends on the JVM stack, which is typically configured very small, and thus easy to blow. Therefore, implementing recursive functions in Clojure is... not idiomatic.

However, if you have enough stack configured, the stack performance is not shabby.

(defn fact[x]
  (if (<= x 1) 1 
    (*' x  (fact (- x 1))  )))

(time (fact 1000))

; user=> (time (fact 1000))
; "Elapsed time: 2.348341 msecs"

(time (apply *' (range 1 1000)))

; user=> (time (apply *' (range 1 1000)))
; "Elapsed time: 1.70674 msecs"

PicoLisp

Not at all surprised to see that PicoLisp has excellent stack performance. Again, as with Common Lisp, it's better than its iterative performance (although I suspect this is within the margin of error).

(de fact (N)
      (if (=0 N)
         1
         (* N (fact (dec N))) ) )

(bench (fact 1000))

; : (bench (fact 1000))
; 0.001 sec

(bench (apply * (range 1 1000)))

; : (bench (apply * (range 1 1000)))
; 0.002 sec

MIT Scheme

Scheme doesn't have a convenient or easy to use timing function that I'm aware of — I suppose I could have written one — so this is a but clunky. Performance is within the margin of error, but at this scale iterative looks slightly better.

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

(with-timings
 (lambda () (fact 1000))
 (lambda (run-time gc-time real-time)
   (write (internal-time/ticks->seconds run-time))
   (write-char #\space)
   (write (internal-time/ticks->seconds gc-time))
   (write-char #\space)
   (write (internal-time/ticks->seconds real-time))
   (newline)))

; 1 ]=> (with-timings
;  (lambda () (fact 1000))
;  (lambda (run-time gc-time real-time)
;    (write (internal-time/ticks->seconds run-time))
;    (write-char #\space)
;    (write (internal-time/ticks->seconds gc-time))
;    (write-char #\space)
;    (write (internal-time/ticks->seconds real-time))
;    (newline)))
; .01 0. .003


(with-timings
 (lambda () (apply * (iota 1000 1)))
 (lambda (run-time gc-time real-time)
   (write (internal-time/ticks->seconds run-time))
   (write-char #\space)
   (write (internal-time/ticks->seconds gc-time))
   (write-char #\space)
   (write (internal-time/ticks->seconds real-time))
   (newline)))

; 1 ]=> (with-timings
;  (lambda () (apply * (iota 1000 1)))
;  (lambda (run-time gc-time real-time)
;    (write (internal-time/ticks->seconds run-time))
;    (write-char #\space)
;    (write (internal-time/ticks->seconds gc-time))
;    (write-char #\space)
;    (write (internal-time/ticks->seconds real-time))
;    (newline)))
; 0. 0. .001