Subject: Re: Lisp is *SLOW*
From: Erik Naggum <erik@naggum.no>
Date: 1997/07/16
Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
Message-ID: <3078042529703162@naggum.no>


* W. Daniel Axline
| Actually, I have been given to understand quite the opposite. Apparently
| whenver (during runtime) a function calls itself, it has to make another
| complete copy of itself to run. You can see how this would tend to take
| up much more in the way of resources than an iterative function.  I'm not
| sure what the exact effect on speed would be, but I imagine it would be
| slower. In my limited experience, iterative algorithms have not been that
| much larger than their recursive counterparts, just more difficult to
| divine.

I wonder what you mean by "a complete copy of itself".  it appears that you
think a copy of the actual function's _code_ is copied, and this is of
course not true.  however, a new stack frame is often created upon a
function call, with space for various registers, local variables, etc, etc.
this does consume resources.  languages that are made for or encourage
recursive function calls often offer "tail call merging" to handle the case
where a function returns simply what the function it is about to call would
return.  in such a case, the calling function's stack frame is undone
before the call (if necessary), and the called function returns to the
caller's caller, saving both time and memory.  (Scheme is "properly tail
recursive" because it requires an implementation to do tail calls as jumps,
not calls.  most Common Lisp implementations offer tail call merging.)

I previously made a serious mistake in believing that Lisp compilers were
so much faster than C compilers when the real difference was that the Lisp
compilers did tail call merging and the C compiler did not.  on a SPARC,
this translates to a very heavy penalty because of the way register windows
are saved on the stack, so the Lisp compilers won big, disproportionately.
(I haven't been able to compute the actual cost of a call so I could
discount it and get a better comparison.  for now, the GNU C compiler makes
recursion extremely costly on the SPARC.)

programmers who write recursive functions learn to use tail recursion soon
after they discover that each function call can take up hundreds of bytes
of memory.  e.g., the former of these two functions will use memory (stack
space) proportional to n, while the latter will use constant space if the
compiler merges tail calls.

(defun factorial (n)
  (if (plusp n)
    (* n (factorial (1- n)))
    1))

(defun factorial (n)
  (flet ((tail-factorial (n accumulator)
	   (if (plusp n)
	     (tail-factorial (1- n) (* n accumulator))
	     accumulator)))
    (tail-factorial n 1)))

let's hope this puts some needless worries about recursion to rest.

#\Erik
-- 
Microsoft Pencil 4.0 -- the only virtual pencil whose tip breaks.