X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=doc%2Fmanual%2Fefficiency.texinfo;h=180672a6d62360ef96735deb85aa85f434c4a5e7;hb=979539d20a27f4315db9e1bde0a4413135cf8603;hp=de905ae3a4faa9a7168a8adebd0baa8c5a533696;hpb=6822034325136cde4e14773c83c3769b42721306;p=sbcl.git diff --git a/doc/manual/efficiency.texinfo b/doc/manual/efficiency.texinfo index de905ae..180672a 100644 --- a/doc/manual/efficiency.texinfo +++ b/doc/manual/efficiency.texinfo @@ -4,27 +4,123 @@ @cindex Efficiency @menu +* Slot access:: * Dynamic-extent allocation:: * Modular arithmetic:: +* Global and Always-Bound variables:: * Miscellaneous Efficiency Issues:: @end menu +@node Slot access +@comment node-name, next, previous, up +@section Slot access +@cindex Slot access + +@subsection 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 @code{notinline}, or passing +it as a functional argument to another function causes severe +performance degradation. + +@subsection Standard object slot access + +The most efficient way to access a slot of a @code{standard-object} is +by using @code{slot-value} with a constant slot name argument inside a +@code{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 +@code{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: + +@lisp +(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)) +@end lisp + +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. + @node Dynamic-extent allocation @comment node-name, next, previous, up @section Dynamic-extent allocation -@cindex Dynamic-extent declaration +@cindex @code{dynamic-extent} declaration +@cindex declaration, @code{dynamic-extent} -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. +SBCL has fairly extensive 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. + +@include var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo 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 +In particular, it is important to realize that dynamic extend is +contagious: + +@lisp +(let* ((a (list 1 2 3)) + (b (cons a a))) + (declare (dynamic-extent b)) + ;; Unless A is accessed elsewhere as well, SBCL will consider + ;; it to be otherwise inaccessible -- it can only be accessed + ;; through B, after all -- and stack allocate it as well. + ;; + ;; Hence returning (CAR B) here is unsafe. + ...) +@end lisp + +This allows stack allocation of complex structures. As a notable +exception to this, SBCL does not as of 1.0.48.21 propagate +dynamic-extentness through @code{&rest} arguments -- but another +conforming implementation might, so portable code should not rely on +this. + +@lisp +(declaim (inline foo)) +(defun foo (fun &rest arguments) + (declare (dynamic-extent arguments)) + (apply fun arguments)) + +(defun bar (a) + ;; SBCL will heap allocate the result of (LIST A), and stack allocate + ;; only the spine of the &rest list -- so this is safe, but unportable. + ;; + ;; Another implementation, including earlier versions of SBCL might consider + ;; (LIST A) to be otherwise inaccessible and stack-allocate it as well! + (foo #'car (list a))) +@end lisp There are many cases when @code{dynamic-extent} declarations could be useful. At present, SBCL implements stack allocation for @@ -35,27 +131,35 @@ useful. At present, SBCL implements stack allocation for @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}. +@findex @cl{cons} +@findex @cl{list} +@findex @cl{list*} +@findex @cl{vector} +@code{cons}, @code{list}, @code{list*}, and @code{vector} when the +result is bound to a variable declared @code{dynamic-extent}. @item +@findex @cl{make-array} 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}. +the resulting array is known to be both simple and one-dimensional, +and has a constant @code{:element-type}. +@cindex Safety optimization quality @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 +@findex @cl{flet} +@findex @cl{labels} +@cindex @code{safety} optimization quality +@cindex optimization quality, @code{safety} 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}. +@code{dynamic-extent} declaration. 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 @@ -63,11 +167,11 @@ user-defined structures when the structure constructor defined using call to the constructor is bound to a variable declared @code{dynamic-extent}. -@strong{Note:} structures with ``raw'' slots can currently be +@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 +all of the above when they appear as initial parts of another stack-allocated object. @end itemize @@ -111,15 +215,6 @@ 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}. @@ -131,7 +226,7 @@ closure, even when the closure is not declared @code{dynamic-extent}. @cindex Modular arithmetic @cindex Arithmetic, modular @cindex Arithmetic, hardware - +@findex @cl{logand} 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 @@ -166,6 +261,37 @@ 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 Global and Always-Bound variables +@comment node-name, next, previous, up +@section Global and Always-Bound variables + +@include macro-sb-ext-defglobal.texinfo + +@deffn {Declaration} @sbext{global} + +Syntax: @code{(sb-ext:global symbol*)} + +Only valid as a global proclamation. + +Specifies that the named symbols cannot be proclaimed or locally +declared @code{special}. Proclaiming an already special or constant +variable name as @code{global} signal an error. Allows more efficient +value lookup in threaded environments in addition to expressing +programmer intention. +@end deffn + +@deffn {Declaration} @sbext{always-bound} + +Syntax: @code{(sb-ext:always-bound symbol*)} + +Only valid as a global proclamation. + +Specifies that the named symbols are always bound. Inhibits +@code{makunbound} of the named symbols. Proclaiming an unbound symbol +as @code{always-bound} signals an error. Allows the compiler to elide +boundness checks from value lookups. +@end deffn + @node Miscellaneous Efficiency Issues @comment node-name, next, previous, up @section Miscellaneous Efficiency Issues @@ -199,6 +325,10 @@ points to keep in mind. @itemize @item +@findex @cl{let} +@findex @cl{let*} +@findex @cl{setq} +@findex @cl{setf} 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