[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Efficiency of local fns and closures



   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:

Your questions can easily be answered by looking at some disassemblies and
a few simple timings with the TIME macro.

   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?

No, a local function that has identical source code to a global function
should compile to the same code.

   b) Does the presence of the lexically-apparent free reference to 'y'
      impact how a) is answered?
      If free ocurrence of 'y' slows down BAR, can that be avoided by
      passing 'y' to BAR as a second argument?

Yes.  Accessing a captured lexical variable requires indirecting through
the lexical environment, rather than accessing the stack directly.  A quick
test I just tried seemed to indicate that it takes about 4 microseconds
longer to access a lexical variable than a parameter variable; 5
microseconds rather than 1 microsecond per access.  There's also a few
extra instructions in FOO that set up the lexical environment.

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

Closures can't be compiled separately from the function that created them.
If you compile a function that contains internal functions, they will all
be compiled.

Closures can't be compiled by themselves when compiling to a file because
it is difficult to arrange for the appropriate lexical environment to be
used when the file is later loaded.  If two lexical closures in the same
environment were written to two different bin files, how would they know at
load time that they are supposed to be linked to the same lexical
environment?

For compiling to core, I can't think of a hard technical problem, and I
think the ANSI CL draft requires this to work.  Symbolics uses a different
format for lexical environments in compiled and interpreted closures, so
there is a problem if there were several interpreted closures in an
environment and only one were compiled, because its environment would have
to be of a different format yet be shared with the others.  It would be
feasible for compilation of a lexical closure to produce code that accesses
the interpreted environment format, but it wouldn't be as fast as accessing
the compiled environment format; accessing an interpreted lexical variable
requires groveling through a deeply nested list structure (it's a list of
alists), while a compiled environment is just a vector of values.

						barmar