Efficiency of local fns and closures

["Robert W. Kerns" <RWK%fuji.ila.dialnet.symbolics.com@RELAY.CS.NET>]

    Date: Thu, 19 Oct 89 16:10 EST
    From: GODDEN%gmr.com@relay.cs.net

    Consider:

    (defun foo (x y)
      (labels ((bar (z)
		(some-function y z)))		;free reference to y
	(bar (some-other-function x))))

    I have a two-part question regarding efficiency:

    a) In general, are local functions any slower w.r.t. a global fn definition
       that may do the same thing?  I.e. is there any reason to expect BAR
       to run faster if it were defined globally?

Actually, it's more likely to be the other way around, except, of course,
as you have defined it, it cannot be defined globally, because of the
free lexically-apparent reference to 'y'.

    b) Does the presence of the lexically-apparent free reference to 'y'
       impact how a) is answered?

Yes, in that it makes the question ill-formed.  It's not at all
clear what code you're trying to compare it against.

If you're asking 'are references to variables from an outer function's
lexical contour slower than references to variables belonging to the
current function's lexical contour' ... the answer is yes, usually,
a little bit slower.  Exactly how much depends on the implementation and
the capabilities of the hardware.  It may also depend on whether the
closure is downward (and can be stack-consed) or upward (and thus, cannot
be stack consed).

On the Symbolics machines, references to stack-consed ones should be a bit
faster than heap-consed closures.  I forget the details on the Ivory, so I
won't go into more detail.

However, to put things into perspective:  If we're talking abut a single
variable reference, the performance issues are much smaller than the
cost of even an ordinary function call.  A closure call is even more expensive.
Making a stack closure is pretty fast, although slower than a variable reference.
Making a heap closure is definitely something to try to avoid when high efficiency
is the goal.

It's worth noting that (at least the last time I looked) the Symbolics compiler
constructs closures whether you're going to call them or not, if you MIGHT call
them.  Thus:

(defun foo (x)
   (labels ((bar () (* x x)))
	(when (and (oddp x) (evenp x))
	  (bar))))

will create a stack closure, and 

(defun foo (x)
  (labels ((bar () (* x x)))
    (when (and (oddp x) (evenp x))
	    #'bar)))

will create a heap closure, even though you can prove that the
closures are never going to be used.

Even this:

(defun foo (x)
  (when (and (oddp x) (evenp x))
    (labels ((bar () (* x x)))
	    #'bar)))

will cons in the heap a lexical environment structure, even though the
LABELS will never be reacheed.  This is because it is very difficult for
a compiler to have one variable live in two different places.  (Such
techniques do exist, but they are more useful on register machines, where
you want to optimize the usage of a limited set of registers).  Consider
the difficulties with complex flows of control and side-effects on the
free variables, and you can see it gets complicated.

       If free ocurrence of 'y' slows down BAR, can that be avoided by
       passing 'y' to BAR as a second argument?

Yes, often it can.  Thi is more likely to be true if 'y' is referenced
many times inside BAR.

    Separate question (but related in some sense):
    c) I have read that closures cannot be compiled.  True? False?
       Implementation dependent?  (For extra credit: If true, why?)

Where did you read that?  The author must be part of the
education establishment that leads to many students thinking
they need a passport to visit New Mexico and Hawaii.  Or that
the earth is flat, and created in 6 days, plus a religious
holiday.

Closures are very definitely compilable.  This isn't exactly the
easiest part of a compiler to get right, especially if you want
optimal code, but the techniques are very widely known and
widely implemented.  In fact, I can't think of any
implementations of Common Lisp which don't, although I'm sure
one will come to mind after I send this.