Don't hardcode the number of gencgc generations.
[sbcl.git] / doc / manual / efficiency.texinfo
1 @node Efficiency
2 @comment  node-name,  next,  previous,  up
3 @chapter Efficiency
4 @cindex Efficiency
5
6 @menu
7 * Slot access::
8 * Dynamic-extent allocation::
9 * Modular arithmetic::
10 * Global and Always-Bound variables::
11 * Miscellaneous Efficiency Issues::
12 @end menu
13
14 @node  Slot access
15 @comment  node-name,  next,  previous,  up
16 @section Slot access
17 @cindex Slot access
18
19 @subsection Structure object slot access
20
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 performance degradation.
26
27 @subsection Standard object slot access
28
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.
34
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.
39
40 Example:
41
42 @lisp
43 (defclass foo () ((bar)))
44
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)
49     old))
50
51 ;; Slow: not a specializer
52 (defmethod quux ((foo foo) new)
53   (let* ((temp foo)
54          (old (slot-value temp 'bar)))
55     (setf (slot-value temp 'bar) new)
56     old))
57
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)
62     (setf foo new)
63     old))
64 @end lisp
65
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.
69
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}
75
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
80 true.
81
82 @include var-sb-ext-star-stack-allocate-dynamic-extent-star.texinfo
83
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
87 crash.
88
89 In particular, it is important to realize that dynamic extend is
90 contagious:
91
92 @lisp
93 (let* ((a (list 1 2 3))
94        (b (cons a a)))
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.
99    ;;
100    ;; Hence returning (CAR B) here is unsafe.
101    ...)
102 @end lisp
103
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
108 this.
109
110 @lisp
111 (declaim (inline foo))
112 (defun foo (fun &rest arguments)
113   (declare (dynamic-extent arguments))
114   (apply fun arguments))
115
116 (defun bar (a)
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.
119   ;;
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)))
123 @end lisp
124
125 There are many cases when @code{dynamic-extent} declarations could be
126 useful. At present, SBCL implements stack allocation for
127
128 @itemize
129
130 @item
131 @code{&rest} lists, when these are declared @code{dynamic-extent}.
132
133 @item
134 @findex @cl{cons}
135 @findex @cl{list}
136 @findex @cl{list*}
137 @findex @cl{vector}
138 @code{cons}, @code{list}, @code{list*}, and @code{vector} when the
139 result is bound to a variable declared @code{dynamic-extent}.
140
141 @item
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}.
147
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.
153
154 @item
155 @findex @cl{flet}
156 @findex @cl{labels}
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}.
163
164 @item
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}.
169
170 @strong{Note}: structures with ``raw'' slots can currently be
171 stack-allocated only on x86 and x86-64.
172
173 @item
174 all of the above when they appear as initial parts of another
175 stack-allocated object.
176
177 @end itemize
178
179 Examples:
180
181 @lisp
182 ;;; Declaiming a structure constructor inline before definition makes
183 ;;; stack allocation possible.
184 (declaim (inline make-thing))
185 (defstruct thing obj next)
186
187 ;;; Stack allocation of various objects bound to DYNAMIC-EXTENT
188 ;;; variables.
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))
195   ...)
196
197 ;;; Stack allocation of arguments to a local function is equivalent
198 ;;; to stack allocation of local variable values.
199 (flet ((f (x)
200          (declare (dynamic-extent x))
201          ...))
202   ...
203   (f (list 1 2 3))
204   (f (cons (cons 1 2) (cons 3 4)))
205   ...)
206
207 ;;; Stack allocation of &REST lists
208 (defun foo (&rest args)
209   (declare (dynamic-extent args))
210   ...)
211 @end lisp
212
213 Future plans include
214
215 @itemize
216
217 @item
218 Automatic detection of the common idiom of calling quantifiers with a
219 closure, even when the closure is not declared @code{dynamic-extent}.
220
221 @end itemize
222
223 @node  Modular arithmetic
224 @comment  node-name,  next,  previous,  up
225 @section Modular arithmetic
226 @cindex Modular arithmetic
227 @cindex Arithmetic, modular
228 @cindex Arithmetic, hardware
229 @findex @cl{logand}
230 Some numeric functions have a property: @var{N} lower bits of the
231 result depend only on @var{N} lower bits of (all or some)
232 arguments. If the compiler sees an expression of form @code{(logand
233 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
234 functions and @var{mask} is known to be of type @code{(unsigned-byte
235 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
236 will be cut to @var{w} bits (but it is not done for variables and
237 constants!). This often results in an ability to use simple machine
238 instructions for the functions.
239
240 Consider an example.
241
242 @lisp
243 (defun i (x y)
244   (declare (type (unsigned-byte 32) x y))
245   (ldb (byte 32 0) (logxor x (lognot y))))
246 @end lisp
247
248 The result of @code{(lognot y)} will be negative and of type
249 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
250 platform is unable to use 32-bit arithmetic here. But modular
251 arithmetic optimizer is able to do it: because the result is cut down
252 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
253 with versions cutting results to 32 bits, and because terminals
254 (here---expressions @code{x} and @code{y}) are also of type
255 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
256
257 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
258 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
259 combinations; and @code{ash} with the positive second
260 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
261 64 on Alpha.  While it is possible to support smaller widths as well,
262 currently this is not implemented.
263
264 @node  Global and Always-Bound variables
265 @comment  node-name,  next,  previous,  up
266 @section Global and Always-Bound variables
267
268 @include macro-sb-ext-defglobal.texinfo
269
270 @deffn {Declaration} @sbext{global}
271
272 Syntax: @code{(sb-ext:global symbol*)}
273
274 Only valid as a global proclamation.
275
276 Specifies that the named symbols cannot be proclaimed or locally
277 declared @code{special}. Proclaiming an already special or constant
278 variable name as @code{global} signal an error. Allows more efficient
279 value lookup in threaded environments in addition to expressing
280 programmer intention.
281 @end deffn
282
283 @deffn {Declaration} @sbext{always-bound}
284
285 Syntax: @code{(sb-ext:always-bound symbol*)}
286
287 Only valid as a global proclamation.
288
289 Specifies that the named symbols are always bound. Inhibits
290 @code{makunbound} of the named symbols. Proclaiming an unbound symbol
291 as @code{always-bound} signals an error. Allows the compiler to elide
292 boundness checks from value lookups.
293 @end deffn
294
295 @node  Miscellaneous Efficiency Issues
296 @comment  node-name,  next,  previous,  up
297 @section Miscellaneous Efficiency Issues
298
299 FIXME: The material in the CMUCL manual about getting good
300 performance from the compiler should be reviewed, reformatted in
301 Texinfo, lightly edited for SBCL, and substituted into this
302 manual. In the meantime, the original CMUCL manual is still 95+%
303 correct for the SBCL version of the Python compiler. See the
304 sections
305
306 @itemize
307 @item Advanced Compiler Use and Efficiency Hints
308 @item Advanced Compiler Introduction
309 @item More About Types in Python
310 @item Type Inference
311 @item Source Optimization
312 @item Tail Recursion
313 @item Local Call
314 @item Block Compilation
315 @item Inline Expansion
316 @item Object Representation
317 @item Numbers
318 @item General Efficiency Hints
319 @item Efficiency Notes
320 @end itemize
321
322 Besides this information from the CMUCL manual, there are a few other
323 points to keep in mind.
324
325 @itemize
326
327 @item
328 @findex @cl{let}
329 @findex @cl{let*}
330 @findex @cl{setq}
331 @findex @cl{setf}
332 The CMUCL manual doesn't seem to state it explicitly, but Python has a
333 mental block about type inference when assignment is involved. Python
334 is very aggressive and clever about inferring the types of values
335 bound with @code{let}, @code{let*}, inline function call, and so
336 forth. However, it's much more passive and dumb about inferring the
337 types of values assigned with @code{setq}, @code{setf}, and
338 friends. It would be nice to fix this, but in the meantime don't
339 expect that just because it's very smart about types in most respects
340 it will be smart about types involved in assignments.  (This doesn't
341 affect its ability to benefit from explicit type declarations
342 involving the assigned variables, only its ability to get by without
343 explicit type declarations.)
344
345 @c <!-- FIXME: Python dislikes assignments, but not in type
346 @c     inference. The real problems are loop induction, closed over
347 @c     variables and aliases. -->
348
349 @item
350 Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has
351 gotten a generational garbage collector. This means that there are
352 some efficiency implications of various patterns of memory usage which
353 aren't discussed in the CMUCL manual. (Some new material should be
354 written about this.)
355
356 @item
357 SBCL has some important known efficiency problems.  Perhaps the most
358 important are
359
360 @itemize @minus
361
362 @item
363 The garbage collector is not particularly efficient, at least on
364 platforms without the generational collector (as of SBCL 0.8.9, all
365 except x86).
366
367 @item
368 Various aspects of the PCL implementation of CLOS are more inefficient
369 than necessary.
370
371 @end itemize
372
373 @end itemize
374
375 Finally, note that Common Lisp defines many constructs which, in
376 the infamous phrase, ``could be compiled efficiently by a
377 sufficiently smart compiler''. The phrase is infamous because
378 making a compiler which actually is sufficiently smart to find all
379 these optimizations systematically is well beyond the state of the art
380 of current compiler technology. Instead, they're optimized on a
381 case-by-case basis by hand-written code, or not optimized at all if
382 the appropriate case hasn't been hand-coded. Some cases where no such
383 hand-coding has been done as of SBCL version 0.6.3 include
384
385 @itemize
386
387 @item
388 @code{(reduce #'f x)} where the type of @code{x} is known at compile
389 time
390
391 @item
392 various bit vector operations, e.g.  @code{(position 0
393 some-bit-vector)}
394
395 @item
396 specialized sequence idioms, e.g.  @code{(remove item list :count 1)}
397
398 @item
399 cases where local compilation policy does not require excessive type
400 checking, e.g.  @code{(locally (declare (safety 1)) (assoc item
401 list))} (which currently performs safe @code{endp} checking internal
402 to assoc).
403
404 @end itemize
405
406 If your system's performance is suffering because of some construct
407 which could in principle be compiled efficiently, but which the SBCL
408 compiler can't in practice compile efficiently, consider writing a
409 patch to the compiler and submitting it for inclusion in the main
410 sources. Such code is often reasonably straightforward to write;
411 search the sources for the string ``@code{deftransform}'' to find many
412 examples (some straightforward, some less so).