2 @comment node-name, next, previous, up
8 * Dynamic-extent allocation::
10 * Miscellaneous Efficiency Issues::
14 @comment node-name, next, previous, up
18 @subsection Structure object slot access
20 Structure slot accessors are efficient only if the compiler is able to
21 open code them: compiling a call to a structure slot accessor before
22 the structure is defined, declaring one @code{notinline}, or passing
23 it as a functional argument to another function causes severe
24 perfomance degradation.
26 @subsection Standard object slot access
28 The most efficient way to access a slot of a @code{standard-object} is
29 by using @code{slot-value} with a constant slot name argument inside a
30 @code{defmethod} body, where the variable holding the instance is a
31 specializer parameter of the method and is never assigned to. The cost
32 is roughly 1.6 times that of an open coded structure slot accessor.
34 Second most efficient way is to use a CLOS slot accessor, or
35 @code{slot-value} with a constant slot name argument, but in
36 circumstances other than specified above. This may be up to 3 times as
37 slow as the method described above.
42 (defclass foo () ((bar)))
44 ;; Fast: specializer and never assigned to
45 (defmethod quux ((foo foo) new)
46 (let ((old (slot-value foo 'bar)))
47 (setf (slot-value foo 'bar) new)
50 ;; Slow: not a specializer
51 (defmethod quux ((foo foo) new)
53 (old (slot-value temp 'bar)))
54 (setf (slot-value temp 'bar) new)
57 ;; Slow: assignment to FOO
58 (defmethod quux ((foo foo) new)
59 (let ((old (slot-value foo 'bar)))
60 (setf (slot-value foo 'bar) new)
65 Note that when profiling code such as this, the first few calls to the
66 generic function are not representative, as the dispatch mechanism is
67 lazily set up during those calls.
69 @node Dynamic-extent allocation
70 @comment node-name, next, previous, up
71 @section Dynamic-extent allocation
72 @cindex Dynamic-extent declaration
74 SBCL has limited support for performing allocation on the stack when a
75 variable is declared @code{dynamic-extent}. The @code{dynamic-extent}
76 declarations are not verified, but are simply trusted as long as
77 @code{sb-ext:*stack-allocate-dynamic-extent*} is true.
79 If dynamic extent constraints specified in the Common Lisp standard
80 are violated, the best that can happen is for the program to have
81 garbage in variables and return values; more commonly, the system will
84 @include var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo
86 There are many cases when @code{dynamic-extent} declarations could be
87 useful. At present, SBCL implements stack allocation for
92 @code{&rest} lists, when these are declared @code{dynamic-extent}.
95 @code{cons}, @code{list} and @code{list*}, when the result is bound to
96 a variable declared @code{dynamic-extent}.
99 simple forms of @code{make-array}, whose result is bound to a variable
100 declared @code{dynamic-extent}: stack allocation is possible only if
101 the resulting array is one-dimensional, and the call has no keyword
102 arguments with the exception of @code{:element-type}.
104 @strong{Note}: stack space is limited, so allocation of a large vector
105 may cause stack overflow. For this reason potentially large vectors,
106 which might circumvent stack overflow detection, are stack allocated
107 only in zero @code{safety} policies.
110 closures defined with @code{flet} or @code{labels}, with a bound
111 @code{dynamic-extent} declaration. Closed-over variables, which are
112 assigned to (either inside or outside the closure) are still allocated
113 on the heap. Blocks and tags are also allocated on the heap, unless
114 all non-local control transfers to them are compiled with zero
118 user-defined structures when the structure constructor defined using
119 @code{defstruct} has been declared @code{inline} and the result of the
120 call to the constructor is bound to a variable declared
121 @code{dynamic-extent}.
123 @strong{Note:} structures with ``raw'' slots can currently be
124 stack-allocated only on x86 and x86-64.
127 all of the above when they appear as initial parts of another
128 stack-allocated object.
135 ;;; Declaiming a structure constructor inline before definition makes
136 ;;; stack allocation possible.
137 (declaim (inline make-thing))
138 (defstruct thing obj next)
140 ;;; Stack allocation of various objects bound to DYNAMIC-EXTENT
142 (let* ((list (list 1 2 3))
143 (nested (cons (list 1 2) (list* 3 4 (list 5))))
144 (vector (make-array 3 :element-type 'single-float))
145 (thing (make-thing :obj list
146 :next (make-thing :obj (make-array 3)))))
147 (declare (dynamic-extent list nested vector thing))
150 ;;; Stack allocation of arguments to a local function is equivalent
151 ;;; to stack allocation of local variable values.
153 (declare (dynamic-extent x))
157 (f (cons (cons 1 2) (cons 3 4)))
160 ;;; Stack allocation of &REST lists
161 (defun foo (&rest args)
162 (declare (dynamic-extent args))
171 Stack allocation of assigned-to closed-over variables, where these are
172 declared @code{dynamic-extent};
175 Automatic detection of the common idiom of applying a function to some
176 defaults and a @code{&rest} list, even when this is not declared
177 @code{dynamic-extent};
180 Automatic detection of the common idiom of calling quantifiers with a
181 closure, even when the closure is not declared @code{dynamic-extent}.
185 @node Modular arithmetic
186 @comment node-name, next, previous, up
187 @section Modular arithmetic
188 @cindex Modular arithmetic
189 @cindex Arithmetic, modular
190 @cindex Arithmetic, hardware
192 Some numeric functions have a property: @var{N} lower bits of the
193 result depend only on @var{N} lower bits of (all or some)
194 arguments. If the compiler sees an expression of form @code{(logand
195 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
196 functions and @var{mask} is known to be of type @code{(unsigned-byte
197 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
198 will be cut to @var{w} bits (but it is not done for variables and
199 constants!). This often results in an ability to use simple machine
200 instructions for the functions.
206 (declare (type (unsigned-byte 32) x y))
207 (ldb (byte 32 0) (logxor x (lognot y))))
210 The result of @code{(lognot y)} will be negative and of type
211 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
212 platform is unable to use 32-bit arithmetic here. But modular
213 arithmetic optimizer is able to do it: because the result is cut down
214 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
215 with versions cutting results to 32 bits, and because terminals
216 (here---expressions @code{x} and @code{y}) are also of type
217 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
219 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
220 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
221 combinations; and @code{ash} with the positive second
222 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
223 64 on Alpha. While it is possible to support smaller widths as well,
224 currently this is not implemented.
226 @node Miscellaneous Efficiency Issues
227 @comment node-name, next, previous, up
228 @section Miscellaneous Efficiency Issues
230 FIXME: The material in the CMUCL manual about getting good
231 performance from the compiler should be reviewed, reformatted in
232 Texinfo, lightly edited for SBCL, and substituted into this
233 manual. In the meantime, the original CMUCL manual is still 95+%
234 correct for the SBCL version of the Python compiler. See the
238 @item Advanced Compiler Use and Efficiency Hints
239 @item Advanced Compiler Introduction
240 @item More About Types in Python
242 @item Source Optimization
245 @item Block Compilation
246 @item Inline Expansion
247 @item Object Representation
249 @item General Efficiency Hints
250 @item Efficiency Notes
253 Besides this information from the CMUCL manual, there are a few other
254 points to keep in mind.
259 The CMUCL manual doesn't seem to state it explicitly, but Python has a
260 mental block about type inference when assignment is involved. Python
261 is very aggressive and clever about inferring the types of values
262 bound with @code{let}, @code{let*}, inline function call, and so
263 forth. However, it's much more passive and dumb about inferring the
264 types of values assigned with @code{setq}, @code{setf}, and
265 friends. It would be nice to fix this, but in the meantime don't
266 expect that just because it's very smart about types in most respects
267 it will be smart about types involved in assignments. (This doesn't
268 affect its ability to benefit from explicit type declarations
269 involving the assigned variables, only its ability to get by without
270 explicit type declarations.)
272 @c <!-- FIXME: Python dislikes assignments, but not in type
273 @c inference. The real problems are loop induction, closed over
274 @c variables and aliases. -->
277 Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has
278 gotten a generational garbage collector. This means that there are
279 some efficiency implications of various patterns of memory usage which
280 aren't discussed in the CMUCL manual. (Some new material should be
284 SBCL has some important known efficiency problems. Perhaps the most
290 The garbage collector is not particularly efficient, at least on
291 platforms without the generational collector (as of SBCL 0.8.9, all
295 Various aspects of the PCL implementation of CLOS are more inefficient
302 Finally, note that Common Lisp defines many constructs which, in
303 the infamous phrase, ``could be compiled efficiently by a
304 sufficiently smart compiler''. The phrase is infamous because
305 making a compiler which actually is sufficiently smart to find all
306 these optimizations systematically is well beyond the state of the art
307 of current compiler technology. Instead, they're optimized on a
308 case-by-case basis by hand-written code, or not optimized at all if
309 the appropriate case hasn't been hand-coded. Some cases where no such
310 hand-coding has been done as of SBCL version 0.6.3 include
315 @code{(reduce #'f x)} where the type of @code{x} is known at compile
319 various bit vector operations, e.g. @code{(position 0
323 specialized sequence idioms, e.g. @code{(remove item list :count 1)}
326 cases where local compilation policy does not require excessive type
327 checking, e.g. @code{(locally (declare (safety 1)) (assoc item
328 list))} (which currently performs safe @code{endp} checking internal
333 If your system's performance is suffering because of some construct
334 which could in principle be compiled efficiently, but which the SBCL
335 compiler can't in practice compile efficiently, consider writing a
336 patch to the compiler and submitting it for inclusion in the main
337 sources. Such code is often reasonably straightforward to write;
338 search the sources for the string ``@code{deftransform}'' to find many
339 examples (some straightforward, some less so).