2 @comment node-name, next, previous, up
6 FIXME: The material in the CMUCL manual about getting good
7 performance from the compiler should be reviewed, reformatted in
8 Texinfo, lightly edited for SBCL, and substituted into this
9 manual. In the meantime, the original CMUCL manual is still 95+%
10 correct for the SBCL version of the Python compiler. See the
14 @item Advanced Compiler Use and Efficiency Hints
15 @item Advanced Compiler Introduction
16 @item More About Types in Python
18 @item Source Optimization
21 @item Block Compilation
22 @item Inline Expansion
23 @item Object Representation
25 @item General Efficiency Hints
26 @item Efficiency Notes
29 Besides this information from the CMUCL manual, there are a few other
30 points to keep in mind.
35 The CMUCL manual doesn't seem to state it explicitly, but Python has a
36 mental block about type inference when assignment is involved. Python
37 is very aggressive and clever about inferring the types of values
38 bound with @code{let}, @code{let*}, inline function call, and so
39 forth. However, it's much more passive and dumb about inferring the
40 types of values assigned with @code{setq}, @code{setf}, and
41 friends. It would be nice to fix this, but in the meantime don't
42 expect that just because it's very smart about types in most respects
43 it will be smart about types involved in assignments. (This doesn't
44 affect its ability to benefit from explicit type declarations
45 involving the assigned variables, only its ability to get by without
46 explicit type declarations.)
48 @c <!-- FIXME: Python dislikes assignments, but not in type
49 @c inference. The real problems are loop induction, closed over
50 @c variables and aliases. -->
53 Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has
54 gotten a generational garbage collector. This means that there are
55 some efficiency implications of various patterns of memory usage which
56 aren't discussed in the CMUCL manual. (Some new material should be
60 SBCL has some important known efficiency problems. Perhaps the most
66 There is only limited support for the ANSI @code{dynamic-extent}
67 declaration. @xref{Dynamic-extent allocation}.
70 The garbage collector is not particularly efficient, at least on
71 platforms without the generational collector (as of SBCL 0.8.9, all
75 Various aspects of the PCL implementation of CLOS are more inefficient
82 Finally, note that Common Lisp defines many constructs which, in
83 the infamous phrase, ``could be compiled efficiently by a
84 sufficiently smart compiler''. The phrase is infamous because
85 making a compiler which actually is sufficiently smart to find all
86 these optimizations systematically is well beyond the state of the art
87 of current compiler technology. Instead, they're optimized on a
88 case-by-case basis by hand-written code, or not optimized at all if
89 the appropriate case hasn't been hand-coded. Some cases where no such
90 hand-coding has been done as of SBCL version 0.6.3 include
95 @code{(reduce #'f x)} where the type of @code{x} is known at compile
99 various bit vector operations, e.g. @code{(position 0
103 specialized sequence idioms, e.g. @code{(remove item list :count 1)}
106 cases where local compilation policy does not require excessive type
107 checking, e.g. @code{(locally (declare (safety 1)) (assoc item
108 list))} (which currently performs safe @code{endp} checking internal
113 If your system's performance is suffering because of some construct
114 which could in principle be compiled efficiently, but which the SBCL
115 compiler can't in practice compile efficiently, consider writing a
116 patch to the compiler and submitting it for inclusion in the main
117 sources. Such code is often reasonably straightforward to write;
118 search the sources for the string ``@code{deftransform}'' to find many
119 examples (some straightforward, some less so).
122 * Dynamic-extent allocation::
123 * Modular arithmetic::
126 @node Dynamic-extent allocation
127 @comment node-name, next, previous, up
128 @section Dynamic-extent allocation
129 @cindex Dynamic-extent declaration
131 SBCL has limited support for performing allocation on the stack when a
132 variable is declared @code{dynamic-extent}. The @code{dynamic-extent}
133 declarations are not verified, but are simply trusted; if the
134 constraints in the Common Lisp standard are violated, the best that
135 can happen is for the program to have garbage in variables and return
136 values; more commonly, the system will crash.
138 As a consequence of this, the condition for performing stack
139 allocation is stringent: either of the @code{speed} or @code{space}
140 optimization qualities must be higher than the maximum of
141 @code{safety} and @code{debug} at the point of the allocation. For
146 (declare (optimize speed (safety 1) (debug 1)))
147 (defun foo (&rest rest)
148 (declare (dynamic-extent rest))
152 Here the @code{&rest} list will be allocated on the stack. Note that
153 it would not be in the following situation:
156 (defun foo (&rest rest)
157 (declare (optimize speed (safety 1) (debug 1)))
158 (declare (dynamic-extent rest))
162 because both the allocation of the @code{&rest} list and the variable
163 binding are outside the scope of the @code{optimize} declaration.
165 There are many cases when @code{dynamic-extent} declarations could be
166 useful. At present, SBCL implements
171 Stack allocation of @code{&rest} lists, where these are declared
172 @code{dynamic-extent}.
175 Stack allocation of @code{list} and @code{list*}, whose result is
176 bound to a variable, declared @code{dynamic-extent}, such as
179 (let ((list (list 1 2 3)))
180 (declare (dynamic-extent list)
188 (declare (dynamic-extent x))
196 Stack allocation of closures, defined with @code{flet} or
197 @code{labels} with a bound declaration @code{dynamic-extent}.
198 Closed-over variables, which are assigned (either inside or outside
199 the closure) are still allocated on the heap. Blocks and tags are also
200 allocated on the heap, unless all non-local control transfers to them
201 are compiled with zero @code{safety}.
210 Stack allocation of closures, where these are declared
211 @code{dynamic-extent};
214 Stack allocation of @code{list}, @code{list*} and @code{cons}
215 (including following chains during initialization, and also for
216 binding mutation), where the allocation is declared
217 @code{dynamic-extent};
220 Automatic detection of the common idiom of applying a function to some
221 defaults and a @code{&rest} list, even when this is not declared
222 @code{dynamic-extent};
225 Automatic detection of the common idiom of calling quantifiers with a
226 closure, even when the closure is not declared @code{dynamic-extent}.
230 @node Modular arithmetic
231 @comment node-name, next, previous, up
232 @section Modular arithmetic
233 @cindex Modular arithmetic
234 @cindex Arithmetic, modular
235 @cindex Arithmetic, hardware
237 Some numeric functions have a property: @var{N} lower bits of the
238 result depend only on @var{N} lower bits of (all or some)
239 arguments. If the compiler sees an expression of form @code{(logand
240 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
241 functions and @var{mask} is known to be of type @code{(unsigned-byte
242 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
243 will be cut to @var{w} bits (but it is not done for variables and
244 constants!). This often results in an ability to use simple machine
245 instructions for the functions.
251 (declare (type (unsigned-byte 32) x y))
252 (ldb (byte 32 0) (logxor x (lognot y))))
255 The result of @code{(lognot y)} will be negative and of type
256 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
257 platform is unable to use 32-bit arithmetic here. But modular
258 arithmetic optimizer is able to do it: because the result is cut down
259 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
260 with versions cutting results to 32 bits, and because terminals
261 (here---expressions @code{x} and @code{y}) are also of type
262 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
264 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
265 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
266 combinations; and @code{ash} with the positive second
267 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
268 64 on Alpha. While it is possible to support smaller widths as well,
269 currently this is not implemented.