doc/manual/efficiency.texinfo

   1 @cindex Efficiency
   2
   3 FIXME: The material in the CMUCL manual about getting good
   4 performance from the compiler should be reviewed, reformatted in
   5 Texinfo, lightly edited for SBCL, and substituted into this
   6 manual. In the meantime, the original CMUCL manual is still 95+%
   7 correct for the SBCL version of the Python compiler. See the
   8 sections
   9
  10 @itemize
  11 @item Advanced Compiler Use and Efficiency Hints
  12 @item Advanced Compiler Introduction
  13 @item More About Types in Python
  14 @item Type Inference
  15 @item Source Optimization
  16 @item Tail Recursion
  17 @item Local Call
  18 @item Block Compilation
  19 @item Inline Expansion
  20 @item Object Representation
  21 @item Numbers
  22 @item General Efficiency Hints
  23 @item Efficiency Notes
  24 @end itemize
  25
  26 Besides this information from the CMUCL manual, there are a few other
  27 points to keep in mind.
  28
  29 @itemize
  30
  31 @item
  32 The CMUCL manual doesn't seem to state it explicitly, but Python has a
  33 mental block about type inference when assignment is involved. Python
  34 is very aggressive and clever about inferring the types of values
  35 bound with @code{let}, @code{let*}, inline function call, and so
  36 forth. However, it's much more passive and dumb about inferring the
  37 types of values assigned with @code{setq}, @code{setf}, and
  38 friends. It would be nice to fix this, but in the meantime don't
  39 expect that just because it's very smart about types in most respects
  40 it will be smart about types involved in assignments.  (This doesn't
  41 affect its ability to benefit from explicit type declarations
  42 involving the assigned variables, only its ability to get by without
  43 explicit type declarations.)
  44
  45 @c <!-- FIXME: Python dislikes assignments, but not in type
  46 @c     inference. The real problems are loop induction, closed over
  47 @c     variables and aliases. -->
  48
  49 @item
  50 Since the time the CMUCL manual was written, CMUCL (and thus SBCL) has
  51 gotten a generational garbage collector. This means that there are
  52 some efficiency implications of various patterns of memory usage which
  53 aren't discussed in the CMUCL manual. (Some new material should be
  54 written about this.)
  55
  56 @item
  57 SBCL has some important known efficiency problems.  Perhaps the most
  58 important are
  59
  60 @itemize @minus
  61
  62 @item
  63 There is only limited support for the ANSI @code{dynamic-extent}
  64 declaration.  @xref{Dynamic-extent allocation}.
  65
  66 @item
  67 The garbage collector is not particularly efficient, at least on
  68 platforms without the generational collector (as of SBCL 0.8.9, all
  69 except x86).
  70
  71 @item
  72 Various aspects of the PCL implementation of CLOS are more inefficient
  73 than necessary.
  74
  75 @end itemize
  76
  77 @end itemize
  78
  79 Finally, note that Common Lisp defines many constructs which, in
  80 the infamous phrase, ``could be compiled efficiently by a
  81 sufficiently smart compiler''. The phrase is infamous because
  82 making a compiler which actually is sufficiently smart to find all
  83 these optimizations systematically is well beyond the state of the art
  84 of current compiler technology. Instead, they're optimized on a
  85 case-by-case basis by hand-written code, or not optimized at all if
  86 the appropriate case hasn't been hand-coded. Some cases where no such
  87 hand-coding has been done as of SBCL version 0.6.3 include
  88
  89 @itemize
  90
  91 @item
  92 @code{(reduce #'f x)} where the type of @code{x} is known at compile
  93 time
  94
  95 @item
  96 various bit vector operations, e.g.  @code{(position 0
  97 some-bit-vector)}
  98
  99 @item
 100 specialized sequence idioms, e.g.  @code{(remove item list :count 1)}
 101
 102 @item
 103 cases where local compilation policy does not require excessive type
 104 checking, e.g.  @code{(locally (declare (safety 1)) (assoc item
 105 list))} (which currently performs safe @code{endp} checking internal
 106 to assoc).
 107
 108 @end itemize
 109
 110 If your system's performance is suffering because of some construct
 111 which could in principle be compiled efficiently, but which the SBCL
 112 compiler can't in practice compile efficiently, consider writing a
 113 patch to the compiler and submitting it for inclusion in the main
 114 sources. Such code is often reasonably straightforward to write;
 115 search the sources for the string ``@code{deftransform}'' to find many
 116 examples (some straightforward, some less so).
 117
 118 @menu
 119 * Dynamic-extent allocation::
 120 * Modular arithmetic::
 121 @end menu
 122
 123 @node  Dynamic-extent allocation
 124 @comment  node-name,  next,  previous,  up
 125 @section Dynamic-extent allocation
 126 @cindex Dynamic-extent declaration
 127
 128 SBCL has limited support for performing allocation on the stack when a
 129 variable is declared @code{dynamic-extent}.  The @code{dynamic-extent}
 130 declarations are not verified, but are simply trusted; if the
 131 constraints in the Common Lisp standard are violated, the best that
 132 can happen is for the program to have garbage in variables and return
 133 values; more commonly, the system will crash.
 134
 135 As a consequence of this, the condition for performing stack
 136 allocation is stringent: either of the @code{speed} or @code{space}
 137 optimization qualities must be higher than the maximum of
 138 @code{safety} and @code{debug} at the point of the allocation.  For
 139 example:
 140
 141 @lisp
 142 (locally
 143   (declare (optimize speed (safety 1) (debug 1)))
 144   (defun foo (&rest rest)
 145     (declare (dynamic-extent rest))
 146     (length rest)))
 147 @end lisp
 148
 149 Here the @code{&rest} list will be allocated on the stack.  Note that
 150 it would not be in the following situation:
 151
 152 @lisp
 153 (defun foo (&rest rest)
 154   (declare (optimize speed (safety 1) (debug 1)))
 155   (declare (dynamic-extent rest))
 156   (length rest))
 157 @end lisp
 158
 159 because both the allocation of the @code{&rest} list and the variable
 160 binding are outside the scope of the @code{optimize} declaration.
 161
 162 There are many cases when dynamic-extent declarations could be useful.
 163 At present, SBCL implements
 164
 165 @itemize
 166
 167 @item
 168 Stack allocation of @code{&rest} lists, where these are declared
 169 @code{dynamic-extent}.
 170
 171 @end itemize
 172
 173 Future plans include
 174
 175 @itemize
 176
 177 @item
 178 Stack allocation of closures, where these are declared
 179 @code{dynamic-extent};
 180
 181 @item
 182 Stack allocation of @code{list}, @code{list*} and @code{cons}
 183 (including following chains during initialization, and also for
 184 binding mutation), where the allocation is declared
 185 @code{dynamic-extent};
 186
 187 @item
 188 Automatic detection of the common idiom of applying a function to some
 189 defaults and a @code{&rest} list, even when this is not declared
 190 @code{dynamic-extent};
 191
 192 @item
 193 Automatic detection of the common idiom of calling quantifiers with a
 194 closure, even when the closure is not declared @code{dynamic-extent}.
 195
 196 @end itemize
 197
 198 @node  Modular arithmetic
 199 @comment  node-name,  next,  previous,  up
 200 @section Modular arithmetic
 201 @cindex Modular arithmetic
 202 @cindex Arithmetic, modular
 203 @cindex Arithmetic, hardware
 204
 205 Some numeric functions have a property: @var{N} lower bits of the
 206 result depend only on @var{N} lower bits of (all or some)
 207 arguments. If the compiler sees an expression of form @code{(logand
 208 @var{exp} @var{mask})}, where @var{exp} is a tree of such ``good''
 209 functions and @var{mask} is known to be of type @code{(unsigned-byte
 210 @var{w})}, where @var{w} is a ``good'' width, all intermediate results
 211 will be cut to @var{w} bits (but it is not done for variables and
 212 constants!). This often results in an ability to use simple machine
 213 instructions for the functions.
 214
 215 Consider an example.
 216
 217 @lisp
 218 (defun i (x y)
 219   (declare (type (unsigned-byte 32) x y))
 220   (ldb (byte 32 0) (logxor x (lognot y))))
 221 @end lisp
 222
 223 The result of @code{(lognot y)} will be negative and of type
 224 @code{(signed-byte 33)}, so a naive implementation on a 32-bit
 225 platform is unable to use 32-bit arithmetic here. But modular
 226 arithmetic optimizer is able to do it: because the result is cut down
 227 to 32 bits, the compiler will replace @code{logxor} and @code{lognot}
 228 with versions cutting results to 32 bits, and because terminals
 229 (here---expressions @code{x} and @code{y}) are also of type
 230 @code{(unsigned-byte 32)}, 32-bit machine arithmetic can be used.
 231
 232 As of SBCL 0.8.5 ``good'' functions are @code{+}, @code{-};
 233 @code{logand}, @code{logior}, @code{logxor}, @code{lognot} and their
 234 combinations; and @code{ash} with the positive second
 235 argument. ``Good'' widths are 32 on HPPA, MIPS, PPC, Sparc and x86 and
 236 64 on Alpha.  While it is possible to support smaller widths as well,
 237 currently this is not implemented.