2 @comment node-name, next, previous, up
8 * Dynamic-extent allocation::
10 * Global and Always-Bound variables::
11 * Miscellaneous Efficiency Issues::
15 @comment node-name, next, previous, up
19 @subsection Structure object slot access
21 Structure slot accessors are efficient only if the compiler is able to
22 open code them: compiling a call to a structure slot accessor before
23 the structure is defined, declaring one @code{notinline}, or passing
24 it as a functional argument to another function causes severe
25 perfomance degradation.
27 @subsection Standard object slot access
29 The most efficient way to access a slot of a @code{standard-object} is
30 by using @code{slot-value} with a constant slot name argument inside a
31 @code{defmethod} body, where the variable holding the instance is a
32 specializer parameter of the method and is never assigned to. The cost
33 is roughly 1.6 times that of an open coded structure slot accessor.
35 Second most efficient way is to use a CLOS slot accessor, or
36 @code{slot-value} with a constant slot name argument, but in
37 circumstances other than specified above. This may be up to 3 times as
38 slow as the method described above.
43 (defclass foo () ((bar)))
45 ;; Fast: specializer and never assigned to
46 (defmethod quux ((foo foo) new)
47 (let ((old (slot-value foo 'bar)))
48 (setf (slot-value foo 'bar) new)
51 ;; Slow: not a specializer
52 (defmethod quux ((foo foo) new)
54 (old (slot-value temp 'bar)))
55 (setf (slot-value temp 'bar) new)
58 ;; Slow: assignment to FOO
59 (defmethod quux ((foo foo) new)
60 (let ((old (slot-value foo 'bar)))
61 (setf (slot-value foo 'bar) new)
66 Note that when profiling code such as this, the first few calls to the
67 generic function are not representative, as the dispatch mechanism is
68 lazily set up during those calls.
70 @node Dynamic-extent allocation
71 @comment node-name, next, previous, up
72 @section Dynamic-extent allocation
73 @cindex @code{dynamic-extent} declaration
74 @cindex declaration, @code{dynamic-extent}
76 SBCL has fairly extensive support for performing allocation on the
77 stack when a variable is declared @code{dynamic-extent}. The
78 @code{dynamic-extent} declarations are not verified, but are simply
79 trusted as long as @code{sb-ext:*stack-allocate-dynamic-extent*} is
82 @include var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo
84 If dynamic extent constraints specified in the Common Lisp standard
85 are violated, the best that can happen is for the program to have
86 garbage in variables and return values; more commonly, the system will
89 In particular, it is important to realize that dynamic extend is
93 (let* ((a (list 1 2 3))
95 (declare (dynamic-extent b))
96 ;; Unless A is accessed elsewhere as well, SBCL will consider
97 ;; it to be otherwise inaccessible -- it can only be accessed
98 ;; through B, after all -- and stack allocate it as well.
100 ;; Hence returning (CAR B) here is unsafe.
104 This allows stack allocation of complex structures. As a notable
105 exception to this, SBCL does not as of 1.0.48.21 propagate
106 dynamic-extentness through @code{&rest} arguments -- but another
107 conforming implementation might, so portable code should not rely on
111 (declaim (inline foo))
112 (defun foo (fun &rest arguments)
113 (declare (dynamic-extent arguments))
114 (apply fun arguments))
117 ;; SBCL will heap allocate the result of (LIST A), and stack allocate
118 ;; only the spine of the &rest list -- so this is safe, but unportable.
120 ;; Another implementation, including earlier versions of SBCL might consider
121 ;; (LIST A) to be otherwise inaccessible and stack-allocate it as well!
122 (foo #'car (list a)))
125 There are many cases when @code{dynamic-extent} declarations could be
126 useful. At present, SBCL implements stack allocation for
131 @code{&rest} lists, when these are declared @code{dynamic-extent}.
138 @code{cons}, @code{list}, @code{list*}, and @code{vector} when the
139 result is bound to a variable declared @code{dynamic-extent}.
142 @findex @cl{make-array}
143 simple forms of @code{make-array}, whose result is bound to a variable
144 declared @code{dynamic-extent}: stack allocation is possible only if
145 the resulting array is known to be both simple and one-dimensional,
146 and has a constant @code{:element-type}.
148 @cindex Safety optimization quality
149 @strong{Note}: stack space is limited, so allocation of a large vector
150 may cause stack overflow. For this reason potentially large vectors,
151 which might circumvent stack overflow detection, are stack allocated
152 only in zero @code{safety} policies.
157 @cindex @code{safety} optimization quality
158 @cindex optimization quality, @code{safety}
159 closures defined with @code{flet} or @code{labels}, with a bound
160 @code{dynamic-extent} declaration. Blocks and tags are also allocated
161 on the heap, unless all non-local control transfers to them are
162 compiled with zero @code{safety}.
165 user-defined structures when the structure constructor defined using
166 @code{defstruct} has been declared @code{inline} and the result of the
167 call to the constructor is bound to a variable declared
168 @code{dynamic-extent}.
170 @strong{Note}: structures with ``raw'' slots can currently be
171 stack-allocated only on x86 and x86-64.
174 all of the above when they appear as initial parts of another
175 stack-allocated object.
182 ;;; Declaiming a structure constructor inline before definition makes
183 ;;; stack allocation possible.
184 (declaim (inline make-thing))
185 (defstruct thing obj next)
187 ;;; Stack allocation of various objects bound to DYNAMIC-EXTENT
189 (let* ((list (list 1 2 3))
190 (nested (cons (list 1 2) (list* 3 4 (list 5))))
191 (vector (make-array 3 :element-type 'single-float))
192 (thing (make-thing :obj list
193 :next (make-thing :obj (make-array 3)))))
194 (declare (dynamic-extent list nested vector thing))
197 ;;; Stack allocation of arguments to a local function is equivalent
198 ;;; to stack allocation of local variable values.
200 (declare (dynamic-extent x))
204 (f (cons (cons 1 2) (cons 3 4)))
207 ;;; Stack allocation of &REST lists
208 (defun foo (&rest args)
209 (declare (dynamic-extent args))
218 Automatic detection of the common idiom of applying a function to some
219 defaults and a @code{&rest} list, even when this is not declared
220 @code{dynamic-extent};
223 Automatic detection of the common idiom of calling quantifiers with a
224 closure, even when the closure is not declared @code{dynamic-extent}.
228 @node Modular arithmetic
229 @comment node-name, next, previous, up
230 @section Modular arithmetic
231 @cindex Modular arithmetic
232 @cindex Arithmetic, modular
233 @cindex Arithmetic, hardware
235 Some numeric functions have a property: @var{N} lower bits of the
236 result depend only on @var{N} lower bits of (all or some)
237 arguments. If the compiler sees an expression of form @code{(logand
238 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
239 functions and @var{mask} is known to be of type @code{(unsigned-byte
240 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
241 will be cut to @var{w} bits (but it is not done for variables and
242 constants!). This often results in an ability to use simple machine
243 instructions for the functions.
249 (declare (type (unsigned-byte 32) x y))
250 (ldb (byte 32 0) (logxor x (lognot y))))
253 The result of @code{(lognot y)} will be negative and of type
254 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
255 platform is unable to use 32-bit arithmetic here. But modular
256 arithmetic optimizer is able to do it: because the result is cut down
257 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
258 with versions cutting results to 32 bits, and because terminals
259 (here---expressions @code{x} and @code{y}) are also of type
260 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
262 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
263 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
264 combinations; and @code{ash} with the positive second
265 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
266 64 on Alpha. While it is possible to support smaller widths as well,
267 currently this is not implemented.
269 @node Global and Always-Bound variables
270 @comment node-name, next, previous, up
271 @section Global and Always-Bound variables
273 @include macro-sb-ext-defglobal.texinfo
275 @deffn {Declaration} @sbext{global}
277 Syntax: @code{(sb-ext:global symbol*)}
279 Only valid as a global proclamation.
281 Specifies that the named symbols cannot be proclaimed or locally
282 declared @code{special}. Proclaiming an already special or constant
283 variable name as @code{global} signal an error. Allows more efficient
284 value lookup in threaded environments in addition to expressing
285 programmer intention.
288 @deffn {Declaration} @sbext{always-bound}
290 Syntax: @code{(sb-ext:always-bound symbol*)}
292 Only valid as a global proclamation.
294 Specifies that the named symbols is always bound. Inhibits @code{makunbound}
295 of the named symbols. Proclaiming an unbound symbol as @code{always-bound} signals
296 an error. Allows compiler to elide boundness checks from value lookups.
299 @node Miscellaneous Efficiency Issues
300 @comment node-name, next, previous, up
301 @section Miscellaneous Efficiency Issues
303 FIXME: The material in the CMUCL manual about getting good
304 performance from the compiler should be reviewed, reformatted in
305 Texinfo, lightly edited for SBCL, and substituted into this
306 manual. In the meantime, the original CMUCL manual is still 95+%
307 correct for the SBCL version of the Python compiler. See the
311 @item Advanced Compiler Use and Efficiency Hints
312 @item Advanced Compiler Introduction
313 @item More About Types in Python
315 @item Source Optimization
318 @item Block Compilation
319 @item Inline Expansion
320 @item Object Representation
322 @item General Efficiency Hints
323 @item Efficiency Notes
326 Besides this information from the CMUCL manual, there are a few other
327 points to keep in mind.
336 The CMUCL manual doesn't seem to state it explicitly, but Python has a
337 mental block about type inference when assignment is involved. Python
338 is very aggressive and clever about inferring the types of values
339 bound with @code{let}, @code{let*}, inline function call, and so
340 forth. However, it's much more passive and dumb about inferring the
341 types of values assigned with @code{setq}, @code{setf}, and
342 friends. It would be nice to fix this, but in the meantime don't
343 expect that just because it's very smart about types in most respects
344 it will be smart about types involved in assignments. (This doesn't
345 affect its ability to benefit from explicit type declarations
346 involving the assigned variables, only its ability to get by without
347 explicit type declarations.)
349 @c <!-- FIXME: Python dislikes assignments, but not in type
350 @c inference. The real problems are loop induction, closed over
351 @c variables and aliases. -->
354 Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has
355 gotten a generational garbage collector. This means that there are
356 some efficiency implications of various patterns of memory usage which
357 aren't discussed in the CMUCL manual. (Some new material should be
361 SBCL has some important known efficiency problems. Perhaps the most
367 The garbage collector is not particularly efficient, at least on
368 platforms without the generational collector (as of SBCL 0.8.9, all
372 Various aspects of the PCL implementation of CLOS are more inefficient
379 Finally, note that Common Lisp defines many constructs which, in
380 the infamous phrase, ``could be compiled efficiently by a
381 sufficiently smart compiler''. The phrase is infamous because
382 making a compiler which actually is sufficiently smart to find all
383 these optimizations systematically is well beyond the state of the art
384 of current compiler technology. Instead, they're optimized on a
385 case-by-case basis by hand-written code, or not optimized at all if
386 the appropriate case hasn't been hand-coded. Some cases where no such
387 hand-coding has been done as of SBCL version 0.6.3 include
392 @code{(reduce #'f x)} where the type of @code{x} is known at compile
396 various bit vector operations, e.g. @code{(position 0
400 specialized sequence idioms, e.g. @code{(remove item list :count 1)}
403 cases where local compilation policy does not require excessive type
404 checking, e.g. @code{(locally (declare (safety 1)) (assoc item
405 list))} (which currently performs safe @code{endp} checking internal
410 If your system's performance is suffering because of some construct
411 which could in principle be compiled efficiently, but which the SBCL
412 compiler can't in practice compile efficiently, consider writing a
413 patch to the compiler and submitting it for inclusion in the main
414 sources. Such code is often reasonably straightforward to write;
415 search the sources for the string ``@code{deftransform}'' to find many
416 examples (some straightforward, some less so).