Need for Faster Function Calling

[Mark Stickel <STICKEL@WARBUCKS.AI.SRI.COM>]

	    On the Need for Faster Function Calling 

Function calling on the Symbolics 3600 is too slow for some
applications.  Each call to the function foo, defined by (defun foo ()
nil), costs in excess of 4 microseconds on a Symbolics 3600 with IFU
according to my timings.  In contrast, the JSR/RTS call/return
instruction pair on a 10MHz 68000 (outdated Sun-2 workstation
technology) costs less than 4 microseconds, and 25MHz 68020s and 68030s
are much faster.  This means that function calling can be much less
expensive on stock architectures in C or assembly language than in LISP,
even on a custom LISP processor.  This is a performance race that I
would not like to see LISP and LISP machines lose.  A goal should be for
LISP to be as fast as C if the LISP programmer provides type
declarations and specifies the use of especially fast but inflexible
optional function-calling operations (as we argue for here), etc.

The significance of relatively slow function calling is that certain
performance critical applications must be done with [macros expanded
into] in-line code rather than function calls.  This can substantially
increase object code size and compilation time.  An example is the
compilation of Prolog-like programs into LISP.  Some operations, such as
some cases of unification and undoing variable bindings, ought to be
functions rather than macros given their prevalence and size.

At over 4 microseconds per call, though, function calling is quite
expensive (for comparison, my (dotimes ...) timing loop was only 1.6
microseconds).  In implementing Prolog-like systems, function-calling
costs can limit performance severely.  At over 4 microseconds per call,
a single function call per inference would limit performance to less
than 250K inferences per second, two calls to less than 125K, ..., even
without any other code.

There are compensating benefits for the slowness: the ability to change
the function definition without recompiling the call, to view the
function call and its arguments in the debugger, etc.  These benefits
are very important during development and even for delivered
applications and are an argument for the use of LISP, but for certain
functions in certain performance critical applications, it would be nice
to be able to sacrifice these benefits (as we have to do with macros now
anyway) to have a very fast function call so that large amounts of
in-line code would not be necessary.  This is analogous to the old NOUUO
option in MacLISP:  UUOs for calling redefinable/traceable functions and
PUSHJs for calling functions quickly.
-------