From: Jonathan King
Subject: FAQ and compiled-call optimization
Date: 
Message-ID: <SQUASH.91Aug26001528@poincare.math.ufl.edu>
Hello.  Is there an FAQ for Common Lisp?  If so, it has expired at my
site --could its maintainer repost it or mail it too me?

My question:  Suppose I have a function of the form

(defun recursive (var unchanging)
  (unless (test)
    (recursive (change var) unchanging) )
  (furthercomputation)  ; This does not affect UNCHANGING.
  )	


Since the variable UNCHANGING never changes, it seems a shame to keep
passing it, in compiled code.  Does proclaiming RECURSIVE to be
`inline' solve this problem?

If not, is the following solution (1) Correct?  (2) Acceptable
programming practice?

(defun recursive (var unchanging)
  (declare (special unchanging))
  (helper var) )

(defun helper (var)
  (unless (test)
    (helper (change var) unchanging) )
  (furthercomputation)  ; This does not affect UNCHANGING.
  )	



		Jonathan King  ······@math.ufl.edu
From: Peter Benson
Subject: Re: FAQ and compiled-call optimization
Date: 
Message-ID: <PAB.91Aug27152609@challenger.lucid.com>
In article <····················@poincare.math.ufl.edu> ······@math.ufl.edu (Jonathan King) writes:

   My question:  Suppose I have a function of the form

   (defun recursive (var unchanging)
     (unless (test)
       (recursive (change var) unchanging) )
     (furthercomputation)  ; This does not affect UNCHANGING.
     )	


   Since the variable UNCHANGING never changes, it seems a shame to keep
   passing it, in compiled code.  Does proclaiming RECURSIVE to be
   `inline' solve this problem?

   If not, is the following solution (1) Correct?  (2) Acceptable
   programming practice?

   (defun recursive (var unchanging)
     (declare (special unchanging))
     (helper var) )

   (defun helper (var)
     (unless (test)
       (helper (change var) unchanging) )
     (furthercomputation)  ; This does not affect UNCHANGING.
     )	

You want a slight change to helper.

 (defun helper (var)
   (locally declare (special unchanging) ; to avoid compiler warnings
     (unless (test)
       (helper (change var)) )  ; don't pass unchanging to helper
     (furthercomputation)  ; This does not affect UNCHANGING.
     ))	

I don't like this because stylistically I prefer not to use special
variables when it is not necessary.

This will do the trick by lexically closing over unchanging.

(defun recursive (var unchanging)
  (labels ((aux1 (var)
	     (unless (test)
	       (aux1 (change var)))
	     (furthercomputation-that-references-unchanging)))
    (aux1 var)))

If you are really concerned about actual efficiency I think your original
function is the best choice.
For the labels version above the compiler must use (or simulate) true
recursion since the function is not tail recursive (the value returned by
the recursive function is not from a call to the recursive function).
It can't be turned into a simple loop.  So each call to aux1 must be passed
a reference to unchanging somehow.  The usual way to do this is an
invisible argument is passed to aux1 that is a pointer to a stack location
holding unchanging.  Each reference to unchanging in the further
computation must make a double indirection to get to unchanging.
If the compiler is smart enough it can see that unchanging is never
modified and just pass the value for unchanging rather than the pointer to
the value on the stack.

In the special binding case you have the overhead for creating the special
binding once (likely not very significant) and the extra overhead for
special references to unchanging.  You also have a little less overhead
since you don't have to pass a second argument.  

In the normal recursive case unchanging could be passed in a register and
references to it would be very fast.

I personally think the intention is clearest in the original function too,
so that would be my personal choice unless and until I needed to squeeze
more speed out.  And then I would try to do some timings to see if my
analysis was really correct.

There are probably some other tricks a compiler could use, but I hope this
illustrates that it is not always obvious what the most efficient code will
be. 

Peter Benson
···@lucid.com