SBCL: Fixnum Optimizations

Question

I'm trying to get more speed out of a little quadratic solver by using optimizations and fixnums. Here's my code:

 1: (defun solve-x (d)
 2:   (declare (optimize (speed 3))
 3:               (type fixnum d))
 4:   (let ((x 1) (y 1))
 5:     (declare (type fixnum x y))
 6:     (loop while (/= (- (* x x) (* d y y)) 1) do
 7:       (if (> (- (* x x) (* d y y)) 1)
 8:         (incf y)
 9:         (incf x)))
10:     (list x y)))

The SBCL compiler seems to have trouble optimizing lines 6 and 7 correctly. I'm getting lots of warnings like this one:

forced to do GENERIC-- (cost 10)
      unable to do inline fixnum arithmetic (cost 2) because:
      The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a FIXNUM.
      The second argument is a (INTEGER
                                -98079714615416886892398913872502479823289163909206900736
                                98079714615416886871131265939943825866051622981576163327), not a FIXNUM.
      The result is a (VALUES
                       (INTEGER
                        -98079714615416886871131265939943825866051622981576163326
                        98079714615416886913666561805061133780526704836837638145)
                       &OPTIONAL), not a (VALUES FIXNUM &REST T).
      unable to do inline (signed-byte 64) arithmetic (cost 5) because:
      The first argument is a (INTEGER 1 21267647932558653957237540927630737409), not a (SIGNED-BYTE
                                                                                         64).
      The second argument is a (INTEGER
                                -98079714615416886892398913872502479823289163909206900736
                                98079714615416886871131265939943825866051622981576163327), not a (SIGNED-BYTE
                                                                                                  64).
      The result is a (VALUES
                       (INTEGER
                        -98079714615416886871131265939943825866051622981576163326
                        98079714615416886913666561805061133780526704836837638145)
                       &OPTIONAL), not a (VALUES (SIGNED-BYTE 64) &REST T).
      etc.

Don't know, where to continue. I already tried to insert 'the fixnum' around multiplications, divisions and subtractions, but it only got worse.

Any ideas, how to make this fast?

Answer 1

If you're sure that the numbers will not overflow at any point, you can add (SAFETY 0) to the optimizations. Also add (THE FIXNUM ...) around the calculations to tell SBCL that you want the result to be treated as a fixnum. The three argument * should be split to two separate calls.

Your code is currently calculating (- (* x x) (* d y y)) twice in the loop. You should assign it to a variable instead. Also notice that since only X or Y changes in the loop, it's unnecessary to calculate the other part again (I don't know what those calculations are, so I just called them FOO, BAR and QUUX).

(defun solve-x (d)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d))
  (let ((x 1) (y 1))
    (declare (type fixnum x y))
    (loop with foo of-type fixnum = (* x x)
          with bar of-type fixnum = (* (the fixnum (* d y)) y)
          for quux of-type fixnum = (- foo bar)
          while (/= quux 1)
          do (if (> quux 1)
                 (setf y (1+ y)
                       bar (* (the fixnum (* d y)) y))
                 (setf x (1+ x)
                       foo (* x x))))
    (list x y)))

To avoid having to write the formulas twice, you could use the #n= reader macro. X and Y can also be moved to the parameter list as &AUX variables to get rid of the LET and second DECLARE.

(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d x y))
  (loop with foo of-type fixnum = #1=(* x x)
        with bar of-type fixnum = #2=(* d (the fixnum (* y y)))
        for quux of-type fixnum = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf y (1+ y)
                     bar #2#)
               (setf x (1+ x)
                     foo #1#)))
  (list x y))

Since X and Y always increase by one, you could avoid some multiplication by incrementing the previous value.

(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type fixnum d x y))
  (loop with foo of-type fixnum = 1
        with bar of-type fixnum = d
        for quux of-type fixnum = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf bar (+ bar (the fixnum (* d y)))
                     y (1+ y)
                     bar (+ bar (the fixnum (* d y))))
               (setf foo (+ foo x)
                     x (1+ x)
                     foo (+ foo x))))
  (list x y))

Answer 2

The problem is that fixnum is not a very useful type. In particular, if a and b are fixnums then (* a b) may well not be: consider (* most-positive-fixnum most-positive-fixnum): this is not a fixnum.

So what you need to do is declare the arguments to have good types: in particular types which are enough smaller than a fixnum that the arithmetic will not overflow into bignums. Assuming you're using a 64-bit platform this is reasonably easy.

Answer 3

I don't know how large those numbers can get in your application but by declaring them to be (signed-byte 31) can result in another 25-ish % speed gain.

(deftype int31 (&optional (bits 31)) `(signed-byte ,bits))
(defun solve-x (d &aux (x 1) (y 1))
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type int31 d x y))
  (loop with foo of-type int31 = 1
        with bar of-type int31 = d
        for quux of-type int31 = (- foo bar)
        while (/= quux 1)
        do (if (> quux 1)
               (setf bar (+ bar (the int31 (* d y)))
                     y (1+ y)
                     bar (+ bar (the int31 (* d y))))
               (setf foo (+ foo x)
                     x (1+ x)
                     foo (+ foo x))))
  (list x y))