OPTIMIZATIONS

   1 #1
   2 (defun mysl (s)
   3     (declare (simple-string s))
   4     (declare (optimize (speed 3) (safety 0) (debug 0)))
   5     (let ((c 0))
   6       (declare (fixnum c))
   7       (dotimes (i (length s))
   8         (when (eql (aref s i) #\1)
   9           (incf c)))
  10       c))
  11
  12 * On X86 I is represented as a tagged integer.
  13
  14 * EQL uses "CMP reg,reg" instead of "CMP reg,im". This causes
  15   allocation of an extra register and an extra move.
  16
  17 * Unnecessary move:
  18   3: SLOT S!11[EDX] {SB-C::VECTOR-LENGTH 1 7} => t23[EAX]
  19   4: MOVE t23[EAX] => t24[EBX]
  20
  21 --------------------------------------------------------------------------------
  22 #2
  23 (defun quux (v)
  24   (declare (optimize (speed 3) (safety 0) (space 2) (debug 0)))
  25   (declare (type (simple-array double-float 1) v))
  26   (let ((s 0d0))
  27     (declare (type double-float s))
  28     (dotimes (i (length v))
  29       (setq s (+ s (aref v i))))
  30     s))
  31
  32 * Python does not combine + with AREF, so generates extra move and
  33   allocates a register.
  34
  35 * On X86 Python thinks that all FP registers are directly accessible
  36   and emits costy MOVE ... => FR1.
  37
  38 --------------------------------------------------------------------------------
  39 #3
  40 (defun bar (n)
  41   (declare (optimize (speed 3) (safety 0) (space 2))
  42            (type fixnum n))
  43   (let ((v (make-list n)))
  44     (setq v (make-array n))
  45     (length v)))
  46
  47 * IR1 does not optimize away (MAKE-LIST N).
  48 --------------------------------------------------------------------------------
  49 #4
  50 (defun bar (v1 v2)
  51   (declare (optimize (speed 3) (safety 0) (space 2))
  52            (type (simple-array base-char 1) v1 v2))
  53   (dotimes (i (length v1))
  54     (setf (aref v2 i) (aref v1 i))))
  55
  56 VOP DATA-VECTOR-SET/SIMPLE-STRING V2!14[EDI] t32[EAX] t30[S2]>t33[CL]
  57                                   => t34[S2]<t35[AL]
  58         MOV     #<TN t33[CL]>, #<TN t30[S2]>
  59         MOV     BYTE PTR [EDI+EAX+1], #<TN t33[CL]>
  60         MOV     #<TN t35[AL]>, #<TN t33[CL]>
  61         MOV     #<TN t34[S2]>, #<TN t35[AL]>
  62
  63 * The value of DATA-VECTOR-SET is not used, so there is no need in the
  64   last two moves.
  65
  66 * And why two moves?
  67 --------------------------------------------------------------------------------
  68 #5
  69 (loop repeat 1.5)
  70
  71 uses generic arithmetic
  72 --------------------------------------------------------------------------------
  73 #6
  74 09:49:05 <jtra> I have found a case in those where suboptimal code is
  75   generate with nested loops, it might be moderately easy to fix that
  76 09:49:28 <jtra> see
  77   http://www.bagley.org/~doug/shootout/bench/nestedloop/nestedloop.cmucl
  78 09:50:30 <jtra> if you add declarations to dotimes, generated code is
  79   almost optimal, but most inner loops run out of registers and use
  80   memory location for iteration variable
  81
  82 ;;; -*- mode: lisp -*-
  83 ;;; http://www.bagley.org/~doug/shootout/
  84 ;;; from Friedrich Dominicus
  85
  86 (defun main ()
  87   (let ((n (parse-integer (or (car (last extensions:*command-line-strings*)) "1")))
  88         (x 0))
  89     (declare (fixnum n)
  90              (fixnum x)
  91              (optimize (speed 3) (debug 0) (safety 0)))
  92     (dotimes (a n)
  93       (dotimes (b n)
  94         (dotimes (c n)
  95           (dotimes (d n)
  96             (dotimes (e n)
  97               (dotimes (f n)
  98                 (incf x)))))))
  99    (format t "~A~%" x)))
 100 --------------------------------------------------------------------------------
 101 #7
 102 (defun foo (x)
 103   (declare (optimize speed (debug 0)))
 104   (if (< x 0) x (foo (1- x))))
 105
 106 SBCL generates a full call of FOO (but CMUCL does not).
 107 --------------------------------------------------------------------------------
 108 #8
 109 (defun foo (d)
 110   (declare (optimize (speed 3) (safety 0) (debug 0)))
 111   (declare (type (double-float 0d0 1d0) d))
 112   (loop for i fixnum from 1 to 5
 113      for x1 double-float = (sin d) ;;; !!!
 114      do (loop for j fixnum from 1 to 4
 115              sum x1 double-float)))
 116
 117 Without the marked declaration Python will use boxed representation for X1.
 118
 119 This is equivalent to
 120
 121 (let ((x nil))
 122   (setq x 0d0)
 123   ;; use of X as DOUBLE-FLOAT
 124 )
 125
 126 The initial binding is effectless, and without it X is of type
 127 DOUBLE-FLOAT. Unhopefully, IR1 does not optimize away effectless
 128 SETs/bindings, and IR2 does not perform type inference.
 129 --------------------------------------------------------------------------------
 130 #9 "Multi-path constant folding"
 131 (defun foo (x)
 132   (if (= (cond ((irgh x) 0)
 133                ((buh x) 1)
 134                (t 2))
 135          0)
 136       :yes
 137       :no))
 138
 139 This code could be optimized to
 140
 141 (defun foo (x)
 142   (cond ((irgh x) :yes)
 143         ((buh x) :no)
 144         (t :no)))
 145 --------------------------------------------------------------------------------
 146 #11
 147 (inverted variant of #9)
 148
 149 (lambda (x)
 150   (let ((y (sap-alien x c-string)))
 151     (list (alien-sap y)
 152           (alien-sap y))))
 153
 154 It could be optimized to
 155
 156 (lambda (x) (list x x))
 157
 158 (if Y were used only once, the current compiler would optimize it)
 159 --------------------------------------------------------------------------------
 160 #12
 161 (typep (truly-the (simple-array * (*)) x) 'simple-vector)
 162
 163 tests lowtag.
 164 --------------------------------------------------------------------------------