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 dynamic-extent declarations could be useful.
166 At present, SBCL implements
171 Stack allocation of @code{&rest} lists, where these are declared
172 @code{dynamic-extent}.
181 Stack allocation of closures, where these are declared
182 @code{dynamic-extent};
185 Stack allocation of @code{list}, @code{list*} and @code{cons}
186 (including following chains during initialization, and also for
187 binding mutation), where the allocation is declared
188 @code{dynamic-extent};
191 Automatic detection of the common idiom of applying a function to some
192 defaults and a @code{&rest} list, even when this is not declared
193 @code{dynamic-extent};
196 Automatic detection of the common idiom of calling quantifiers with a
197 closure, even when the closure is not declared @code{dynamic-extent}.
201 @node Modular arithmetic
202 @comment node-name, next, previous, up
203 @section Modular arithmetic
204 @cindex Modular arithmetic
205 @cindex Arithmetic, modular
206 @cindex Arithmetic, hardware
208 Some numeric functions have a property: @var{N} lower bits of the
209 result depend only on @var{N} lower bits of (all or some)
210 arguments. If the compiler sees an expression of form @code{(logand
211 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
212 functions and @var{mask} is known to be of type @code{(unsigned-byte
213 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
214 will be cut to @var{w} bits (but it is not done for variables and
215 constants!). This often results in an ability to use simple machine
216 instructions for the functions.
222 (declare (type (unsigned-byte 32) x y))
223 (ldb (byte 32 0) (logxor x (lognot y))))
226 The result of @code{(lognot y)} will be negative and of type
227 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
228 platform is unable to use 32-bit arithmetic here. But modular
229 arithmetic optimizer is able to do it: because the result is cut down
230 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
231 with versions cutting results to 32 bits, and because terminals
232 (here---expressions @code{x} and @code{y}) are also of type
233 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
235 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
236 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
237 combinations; and @code{ash} with the positive second
238 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
239 64 on Alpha. While it is possible to support smaller widths as well,
240 currently this is not implemented.