Funcall Speed-Up

[boyer@rascal.ics.UTEXAS.EDU (Bob Boyer)]

Appropriate declarations and proclamations can definitely increase
execution speed in KCL and AKCL.

In the case of function calls, in AKCL, it is important, for maximum
efficiency, where possible, to PROCLAIM that a function returns a
single value.  Typically, this results in ordinary Lisp function calls
becoming ordinary C function calls, which is perhaps as fast as one
could expect to go.  (Of course there is still an extra memory
reference in the typical Lisp case because Lisp functions can be
dynamically redefined.)

Bill Schelter has recently improved the execution of FUNCALL for a
special, but important, case (in AKCL Version 1.236).  There are two
conditions that must both be met to obtain the higher speed funcall.
First, the funcall must be of a function that has been proclaimed to
be a function that returns a single value.  Second, the textual
occurrence of the funcall must reveal that the funcall does not return
multiple values by satisfying one of three conditions: (i) the value
of the funcall is ignored, e.g., it is a nonfinal member of a progn,
(ii) the funcall occurs as the second arg of a SETQ, or (iii) the
funcall occurs as the second arg of a THE whose first arg is (VALUES
T), declaring that only one value is returned.

The following piece of code can be executed in any Common Lisp, and
will print out, when you invoke (report 1000000), timing information
for (a) going around the timing DO loop a million times (b) a million
calls to an ordinary function of one argument that returns one
value, and (c) a million calls to that same function via funcall.
Below the code are a few examples run on a Sun-3/280.  You can see
that the difference between AKCL and KCL is quite large, a drop down
to about 3 microseconds for a funcall from 17 in KCL.  I have no
idea whether the Lucid and Allegro times could be substantially
improved by declarations of some sort or whether more recent releases
of those implementations would produce different results.

;  Here is the code.

;  Proclaim that function foo takes one value and returns one.
(proclaim '(function foo (t) t))

(defun foo (x) x)

(defun do-cost (n)
  (do ((i n (1- i))) ((= i 0))
      (declare (fixnum i))
      nil))  ; Do nothing.
      
(defun regular-call-cost (n)
  (declare (fixnum n))
  (do ((i n (1- i))) ((= i 0))
      (declare (fixnum i))
      (foo t)))  ;  Call foo in the ordinary way.

(defun funcall-cost (n fn)
  (declare (fixnum n))
  (do ((i n (1- i))) ((= i 0))
      (declare (fixnum i))
      (funcall fn t)))   ;  The value of the funcall is ignored. 

(defun report (n)
  (format t "do-cost")
  (time (do-cost n))
  (format t "regular-call-cost")
  (time (regular-call-cost n))
  (format t "funcall-cost")
  (time (funcall-cost n #'foo)))
				  
;  End of the code.  Here are some example runs, all produced by
;  invoking (report 1000000).  I have deleted the lines that involve
;  compiling, loading, etc.  All of the compilation was done with
;  safety=0 and speed=3.

AKCL (Austin Kyoto Common Lisp)  Version(1.236) Wed Oct 18 16:36:24 CDT 1989

do-cost
real time : 0.733 secs
run time  : 0.700 secs

regular-call-cost
real time : 3.000 secs
run time  : 2.850 secs

funcall-cost
real time : 5.550 secs
run time  : 3.633 secs

KCl (Kyoto Common Lisp)  June 3, 1987

do-cost
real time : 1.450 secs
run time  : 1.417 secs

regular-call-cost
real time : 4.133 secs
run time  : 3.983 secs

funcall-cost
real time : 19.100 secs
run time  : 17.600 secs
NIL


;;; Sun Common Lisp, Development Environment 3.0.2, 2 August 1988

do-cost
Elapsed Real Time = 1.04 seconds
Total Run Time    = 0.72 seconds
User Run Time     = 0.70 seconds
System Run Time   = 0.02 seconds
Dynamic Bytes Consed = 0

regular-call-cost
Elapsed Real Time = 6.36 seconds
Total Run Time    = 5.44 seconds
User Run Time     = 5.40 seconds
System Run Time   = 0.04 seconds
Dynamic Bytes Consed = 0

funcall-cost
Elapsed Real Time = 6.28 seconds
Total Run Time    = 6.26 seconds
User Run Time     = 6.24 seconds
System Run Time   = 0.02 seconds
Dynamic Bytes Consed = 0

Allegro CL 3.1.beta.22 [Sun3] (6/7/89)

do-cost
cpu time (non-gc) 1850 msec user, 16 msec system
cpu time (gc)     0 msec user, 0 msec system
cpu time (total)  1850 msec user, 16 msec system
real time  2480 msec

regular-call-cost
cpu time (non-gc) 5850 msec user, 67 msec system
cpu time (gc)     0 msec user, 0 msec system
cpu time (total)  5850 msec user, 67 msec system
real time  6780 msec

funcall-costcpu
time (non-gc) 9367 msec user, 83 msec system
cpu time (gc)     0 msec user, 0 msec system
cpu time (total)  9367 msec user, 83 msec system
real time  10420 msec