Efficiency
**********

Slot access
===========

Structure object slot access
----------------------------

Structure slot accessors are efficient only if the compiler is able to open code them: compiling a call to a structure slot accessor before the structure is defined, declaring one notinline, or passing it as a functional argument to another function causes severe perfomance degradation.

Standard object slot access
---------------------------

The most efficient way to access a slot of a standard-object is by using slot-value with a constant slot name argument inside a defmethod body, where the variable holding the instance is a specializer parameter of the method and is never assigned to. The cost is roughly 1.6 times that of an open coded structure slot accessor.

Second most efficient way is to use a CLOS slot accessor, or slot-value with a constant slot name argument, but in circumstances other than specified above. This may be up to 3 times as slow as the method described above.

Example:

     (defclass foo () ((bar)))

     ;; Fast: specializer and never assigned to
     (defmethod quux ((foo foo) new)
       (let ((old (slot-value foo 'bar)))
         (setf (slot-value foo 'bar) new)
         old))

     ;; Slow: not a specializer
     (defmethod quux ((foo foo) new)
       (let* ((temp foo)
              (old (slot-value temp 'bar)))
         (setf (slot-value temp 'bar) new)
         old))

     ;; Slow: assignment to FOO
     (defmethod quux ((foo foo) new)
       (let ((old (slot-value foo 'bar)))
         (setf (slot-value foo 'bar) new)
         (setf foo new)
         old))

Note that when profiling code such as this, the first few calls to the generic function are not representative, as the dispatch mechanism is lazily set up during those calls.

Dynamic-extent allocation
=========================

SBCL has limited support for performing allocation on the stack when a variable is declared dynamic-extent. The dynamic-extent declarations are not verified, but are simply trusted as long as sb-ext:*stack-allocate-dynamic-extent* is true.

If dynamic extent constraints specified in the Common Lisp standard are violated, the best that can happen is for the program to have garbage in variables and return values; more commonly, the system will crash.

     [file var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo not included]

There are many cases when dynamic-extent declarations could be useful. At present, SBCL implements stack allocation for

  * &rest lists, when these are declared dynamic-extent.

  * cons, list, list*, and vector when the result is bound to a variable declared dynamic-extent.

  * simple forms of make-array, whose result is bound to a variable declared dynamic-extent: stack allocation is possible only if the resulting array is known to be both simple and one-dimensional, and has a constant :element-type.

     Note: stack space is limited, so allocation of a large vector may cause stack overflow. For this reason potentially large vectors, which might circumvent stack overflow detection, are stack allocated only in zero safety policies.

  * closures defined with flet or labels, with a bound dynamic-extent declaration. Closed-over variables, which are assigned to (either inside or outside the closure) are still allocated on the heap. Blocks and tags are also allocated on the heap, unless all non-local control transfers to them are compiled with zero safety.

  * user-defined structures when the structure constructor defined using defstruct has been declared inline and the result of the call to the constructor is bound to a variable declared dynamic-extent.

     Note: structures with ``raw'' slots can currently be stack-allocated only on x86 and x86-64.

  * all of the above when they appear as initial parts of another stack-allocated object.

Examples:

     ;;; Declaiming a structure constructor inline before definition makes
     ;;; stack allocation possible.
     (declaim (inline make-thing))
     (defstruct thing obj next)

     ;;; Stack allocation of various objects bound to DYNAMIC-EXTENT
     ;;; variables.
     (let* ((list (list 1 2 3))
            (nested (cons (list 1 2) (list* 3 4 (list 5))))
            (vector (make-array 3 :element-type 'single-float))
            (thing (make-thing :obj list
                               :next (make-thing :obj (make-array 3)))))
       (declare (dynamic-extent list nested vector thing))
       ...)

     ;;; Stack allocation of arguments to a local function is equivalent
     ;;; to stack allocation of local variable values.
     (flet ((f (x)
              (declare (dynamic-extent x))
              ...))
       ...
       (f (list 1 2 3))
       (f (cons (cons 1 2) (cons 3 4)))
       ...)

     ;;; Stack allocation of &REST lists
     (defun foo (&rest args)
       (declare (dynamic-extent args))
       ...)

Future plans include

  * Stack allocation of assigned-to closed-over variables, where these are declared dynamic-extent;

  * Automatic detection of the common idiom of applying a function to some defaults and a &rest list, even when this is not declared dynamic-extent;

  * Automatic detection of the common idiom of calling quantifiers with a closure, even when the closure is not declared dynamic-extent.

Modular arithmetic
==================

Some numeric functions have a property: N lower bits of the result depend only on N lower bits of (all or some) arguments. If the compiler sees an expression of form (logand EXP MASK), where EXP is a tree of such ``good'' functions and MASK is known to be of type (unsigned-byte W), where W is a ``good'' width, all intermediate results will be cut to W bits (but it is not done for variables and constants!). This often results in an ability to use simple machine instructions for the functions.

Consider an example.

     (defun i (x y)
       (declare (type (unsigned-byte 32) x y))
       (ldb (byte 32 0) (logxor x (lognot y))))

The result of (lognot y) will be negative and of type (signed-byte 33), so a naive implementation on a 32-bit platform is unable to use 32-bit arithmetic here. But modular arithmetic optimizer is able to do it: because the result is cut down to 32 bits, the compiler will replace logxor and lognot with versions cutting results to 32 bits, and because terminals (here---expressions x and y) are also of type (unsigned-byte 32), 32-bit machine arithmetic can be used.

As of SBCL 0.8.5 ``good'' functions are +, -; logand, logior, logxor, lognot and their combinations; and ash with the positive second argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and 64 on Alpha.  While it is possible to support smaller widths as well, currently this is not implemented.

Global and Always-Bound variables
=================================

     [file macro-sb-ext-defglobal.texinfo not included]

 -- Declaration: global

     Syntax: (sb-ext:global symbol*)

     Only valid as a global proclamation.

     Specifies that the named symbols cannot be proclaimed or locally declared special. Proclaiming an already special or constant variable name as global signal an error. Allows more efficient value lookup in threaded environments in addition to expressing programmer intention.

 -- Declaration: always-bound

     Syntax: (sb-ext:always-bound symbol*)

     Only valid as a global proclamation.

     Specifies that the named symbols is always bound. Inhibits makunbound of the named symbols. Proclaiming an unbound symbol as always-bound signals an error. Allows compiler to elide boundness checks from value lookups.

Miscellaneous Efficiency Issues
===============================

FIXME: The material in the CMUCL manual about getting good performance from the compiler should be reviewed, reformatted in Texinfo, lightly edited for SBCL, and substituted into this manual. In the meantime, the original CMUCL manual is still 95+% correct for the SBCL version of the Python compiler. See the sections

  * Advanced Compiler Use and Efficiency Hints

  * Advanced Compiler Introduction

  * More About Types in Python

  * Type Inference

  * Source Optimization

  * Tail Recursion

  * Local Call

  * Block Compilation

  * Inline Expansion

  * Object Representation

  * Numbers

  * General Efficiency Hints

  * Efficiency Notes

Besides this information from the CMUCL manual, there are a few other points to keep in mind.

  * The CMUCL manual doesn't seem to state it explicitly, but Python has a mental block about type inference when assignment is involved. Python is very aggressive and clever about inferring the types of values bound with let, let*, inline function call, and so forth. However, it's much more passive and dumb about inferring the types of values assigned with setq, setf, and friends. It would be nice to fix this, but in the meantime don't expect that just because it's very smart about types in most respects it will be smart about types involved in assignments.  (This doesn't affect its ability to benefit from explicit type declarations involving the assigned variables, only its ability to get by without explicit type declarations.)

  * Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has gotten a generational garbage collector. This means that there are some efficiency implications of various patterns of memory usage which aren't discussed in the CMUCL manual. (Some new material should be written about this.)

  * SBCL has some important known efficiency problems.  Perhaps the most important are

       - The garbage collector is not particularly efficient, at least on platforms without the generational collector (as of SBCL 0.8.9, all except x86).

       - Various aspects of the PCL implementation of CLOS are more inefficient than necessary.

Finally, note that Common Lisp defines many constructs which, in the infamous phrase, ``could be compiled efficiently by a sufficiently smart compiler''. The phrase is infamous because making a compiler which actually is sufficiently smart to find all these optimizations systematically is well beyond the state of the art of current compiler technology. Instead, they're optimized on a case-by-case basis by hand-written code, or not optimized at all if the appropriate case hasn't been hand-coded. Some cases where no such hand-coding has been done as of SBCL version 0.6.3 include

  * (reduce #'f x) where the type of x is known at compile time

  * various bit vector operations, e.g.  (position 0 some-bit-vector)

  * specialized sequence idioms, e.g.  (remove item list :count 1)

  * cases where local compilation policy does not require excessive type checking, e.g.  (locally (declare (safety 1)) (assoc item list)) (which currently performs safe endp checking internal to assoc).

If your system's performance is suffering because of some construct which could in principle be compiled efficiently, but which the SBCL compiler can't in practice compile efficiently, consider writing a patch to the compiler and submitting it for inclusion in the main sources. Such code is often reasonably straightforward to write; search the sources for the string ``deftransform'' to find many examples (some straightforward, some less so).