@chapter Efficiency
@cindex Efficiency
+@menu
+* Dynamic-extent allocation::
+* Modular arithmetic::
+* Miscellaneous Efficiency Issues::
+@end menu
+
+@node Dynamic-extent allocation
+@comment node-name, next, previous, up
+@section Dynamic-extent allocation
+@cindex Dynamic-extent declaration
+
+SBCL has limited support for performing allocation on the stack when a
+variable is declared @code{dynamic-extent}. The @code{dynamic-extent}
+declarations are not verified, but are simply trusted as long as
+@code{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.
+
+@include var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo
+
+There are many cases when @code{dynamic-extent} declarations could be
+useful. At present, SBCL implements stack allocation for
+
+@itemize
+
+@item
+@code{&rest} lists, when these are declared @code{dynamic-extent}.
+
+@item
+@code{cons}, @code{list} and @code{list*}, when the result is bound to
+a variable declared @code{dynamic-extent}.
+
+@item
+simple forms of @code{make-array}, whose result is bound to a variable
+declared @code{dynamic-extent}: stack allocation is possible only if
+the resulting array is one-dimensional, and the call has no keyword
+arguments with the exception of @code{:element-type}.
+
+@strong{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 @code{safety} policies.
+
+@item
+closures defined with @code{flet} or @code{labels}, with a bound
+@code{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
+@code{safety}.
+
+@item
+user-defined structures when the structure constructor defined using
+@code{defstruct} has been declared @code{inline} and the result of the
+call to the constructor is bound to a variable declared
+@code{dynamic-extent}.
+
+@strong{Note:} structures with ``raw'' slots can currently be
+stack-allocated only on x86 and x86-64.
+
+@item
+all of the above when they appear as initial parts if another
+stack-allocated object.
+
+@end itemize
+
+Examples:
+
+@lisp
+;;; 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))
+ ...)
+@end lisp
+
+Future plans include
+
+@itemize
+
+@item
+Stack allocation of assigned-to closed-over variables, where these are
+declared @code{dynamic-extent};
+
+@item
+Automatic detection of the common idiom of applying a function to some
+defaults and a @code{&rest} list, even when this is not declared
+@code{dynamic-extent};
+
+@item
+Automatic detection of the common idiom of calling quantifiers with a
+closure, even when the closure is not declared @code{dynamic-extent}.
+
+@end itemize
+
+@node Modular arithmetic
+@comment node-name, next, previous, up
+@section Modular arithmetic
+@cindex Modular arithmetic
+@cindex Arithmetic, modular
+@cindex Arithmetic, hardware
+
+Some numeric functions have a property: @var{N} lower bits of the
+result depend only on @var{N} lower bits of (all or some)
+arguments. If the compiler sees an expression of form @code{(logand
+@var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
+functions and @var{mask} is known to be of type @code{(unsigned-byte
+@var{w})}, where @var{w} is a ``good'' width, all intermediate results
+will be cut to @var{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.
+
+@lisp
+(defun i (x y)
+ (declare (type (unsigned-byte 32) x y))
+ (ldb (byte 32 0) (logxor x (lognot y))))
+@end lisp
+
+The result of @code{(lognot y)} will be negative and of type
+@code{(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 @code{logxor} and @code{lognot}
+with versions cutting results to 32 bits, and because terminals
+(here---expressions @code{x} and @code{y}) are also of type
+@code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
+
+As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
+@code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
+combinations; and @code{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.
+
+@node Miscellaneous Efficiency Issues
+@comment node-name, next, previous, up
+@section 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
points to keep in mind.
@itemize
-
+
@item
The CMUCL manual doesn't seem to state it explicitly, but Python has a
mental block about type inference when assignment is involved. Python
@c <!-- FIXME: Python dislikes assignments, but not in type
@c inference. The real problems are loop induction, closed over
@c variables and aliases. -->
-
+
@item
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.)
-
+
@item
SBCL has some important known efficiency problems. Perhaps the most
important are
-
+
@itemize @minus
-
-@item
-There is only limited support for the ANSI @code{dynamic-extent}
-declaration. @xref{Dynamic-extent allocation}.
-
+
@item
The garbage collector is not particularly efficient, at least on
platforms without the generational collector (as of SBCL 0.8.9, all
except x86).
-
+
@item
Various aspects of the PCL implementation of CLOS are more inefficient
than necessary.
-
+
@end itemize
@end itemize
hand-coding has been done as of SBCL version 0.6.3 include
@itemize
-
+
@item
@code{(reduce #'f x)} where the type of @code{x} is known at compile
time
-
+
@item
various bit vector operations, e.g. @code{(position 0
some-bit-vector)}
sources. Such code is often reasonably straightforward to write;
search the sources for the string ``@code{deftransform}'' to find many
examples (some straightforward, some less so).
-
-@menu
-* Dynamic-extent allocation::
-* Modular arithmetic::
-@end menu
-
-@node Dynamic-extent allocation
-@comment node-name, next, previous, up
-@section Dynamic-extent allocation
-@cindex Dynamic-extent declaration
-
-SBCL has limited support for performing allocation on the stack when a
-variable is declared @code{dynamic-extent}. The @code{dynamic-extent}
-declarations are not verified, but are simply trusted; if the
-constraints 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.
-
-As a consequence of this, the condition for performing stack
-allocation is stringent: either of the @code{speed} or @code{space}
-optimization qualities must be higher than the maximum of
-@code{safety} and @code{debug} at the point of the allocation. For
-example:
-
-@lisp
-(locally
- (declare (optimize speed (safety 1) (debug 1)))
- (defun foo (&rest rest)
- (declare (dynamic-extent rest))
- (length rest)))
-@end lisp
-
-Here the @code{&rest} list will be allocated on the stack. Note that
-it would not be in the following situation:
-
-@lisp
-(defun foo (&rest rest)
- (declare (optimize speed (safety 1) (debug 1)))
- (declare (dynamic-extent rest))
- (length rest))
-@end lisp
-
-because both the allocation of the @code{&rest} list and the variable
-binding are outside the scope of the @code{optimize} declaration.
-
-There are many cases when @code{dynamic-extent} declarations could be
-useful. At present, SBCL implements
-
-@itemize
-
-@item
-Stack allocation of @code{&rest} lists, where these are declared
-@code{dynamic-extent}.
-
-@item
-Stack allocation of @code{list} and @code{list*}, whose result is
-bound to a variable, declared @code{dynamic-extent}, such as
-
-@lisp
-(let ((list (list 1 2 3)))
- (declare (dynamic-extent list)
- ...))
-@end lisp
-
-or
-
-@lisp
-(flet ((f (x)
- (declare (dynamic-extent x))
- ...))
- ...
- (f (list 1 2 3))
- ...)
-@end lisp
-
-@item
-Stack allocation of simple forms of @code{make-array}, whose result is
-bound to a variable, declared @code{dynamic-extent}. The resulting
-array should be one-dimensional, the only allowed keyword argument is
-@code{:element-type}.
-
-Notice, that stack space is limited, so allocation of a large vector
-may cause stack overflow and abnormal termination of the SBCL process.
-
-@item
-Stack allocation of closures, defined with @code{flet} or
-@code{labels} with a bound declaration @code{dynamic-extent}.
-Closed-over variables, which are assigned (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 @code{safety}.
-
-@end itemize
-
-Future plans include
-
-@itemize
-
-@item
-Stack allocation of closures, where these are declared
-@code{dynamic-extent};
-
-@item
-Stack allocation of @code{list}, @code{list*} and @code{cons}
-(including following chains during initialization, and also for
-binding mutation), where the allocation is declared
-@code{dynamic-extent};
-
-@item
-Automatic detection of the common idiom of applying a function to some
-defaults and a @code{&rest} list, even when this is not declared
-@code{dynamic-extent};
-
-@item
-Automatic detection of the common idiom of calling quantifiers with a
-closure, even when the closure is not declared @code{dynamic-extent}.
-
-@end itemize
-
-@node Modular arithmetic
-@comment node-name, next, previous, up
-@section Modular arithmetic
-@cindex Modular arithmetic
-@cindex Arithmetic, modular
-@cindex Arithmetic, hardware
-
-Some numeric functions have a property: @var{N} lower bits of the
-result depend only on @var{N} lower bits of (all or some)
-arguments. If the compiler sees an expression of form @code{(logand
-@var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
-functions and @var{mask} is known to be of type @code{(unsigned-byte
-@var{w})}, where @var{w} is a ``good'' width, all intermediate results
-will be cut to @var{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.
-
-@lisp
-(defun i (x y)
- (declare (type (unsigned-byte 32) x y))
- (ldb (byte 32 0) (logxor x (lognot y))))
-@end lisp
-
-The result of @code{(lognot y)} will be negative and of type
-@code{(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 @code{logxor} and @code{lognot}
-with versions cutting results to 32 bits, and because terminals
-(here---expressions @code{x} and @code{y}) are also of type
-@code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
-
-As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
-@code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
-combinations; and @code{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.
projects / sbcl.git / blobdiff