Excessive compilation time for an expression involving LOGIOR on bignums

[Lutz Euler]

The expression

(let ((a (logior (expt 2 100000) (random 2)))
      (b (logior (expt 2 100000) (random 2))))
  (integer-length (* a b)))

takes several seconds until a result is printed. Profiling shows that this time is spent in LOGIOR-DERIVE-UNSIGNED-LOW-BOUND when the compiler tries to derive the types of a and b.

The reason is that LOGIOR-DERIVE-UNSIGNED-LOW-BOUND uses an algorithm that in the worst case (which is triggered here) has quadratic runtime (and amount of garbage generated) in the number of bits of the bounds of the input integer ranges. (The HIGH variant, and both of these for LOGAND and LOGXOR, too, have the same worst case complexity.)

Tested with sbcl-1.1.1 on x86-64 on linux, but these functions were last changed in 2005.

[Lutz Euler (lutz-euler)]

I have found a way to make the LOGIOR-DERIVE-... functions use linear time in the worst case which should be applicable to LOGAND and LOGXOR, too. Replace the loop in LOGIOR-DERIVE-UNSIGNED-LOW-BOUND with:

   (let* ((mask-x (1- (ash 1 (integer-length (logxor a b)))))
          (mask-y (1- (ash 1 (integer-length (logxor c d)))))
          (index-x (integer-length (logand mask-x (lognot a) c)))
          (index-y (integer-length (logand mask-y (lognot c) a))))
     (cond ((= index-x index-y)
            ;; Both indexes are 0 here.
            (logior a c))
           ((>= index-x index-y)
            (let ((m (ash 1 (1- index-x))))
              (logior (logandc2 a (1- m)) c)))
           (t
            (let ((m (ash 1 (1- index-y))))
              (logior (logandc2 c (1- m)) a)))))))

Unfortunately this slows down some common cases; for example in a large percentage of the calls to LOGIOR-DERIVE-UNSIGNED-LOW-BOUND during compilation of SBCL itself (on x86-64) both arguments are the range (INTEGER 0 18446744073709551615) and here the new version takes five times the time of the current one. (For randomly chosen fixnum ranges the new version is somewhat faster than the current one).

Does anyone have code examples where these type derivation functions use up measurable parts of the compilation time despite being used with smallish numbers? If not, this slow down may well be unmeasurable (we are talking about, say, 500 machine clocks per call instead of 100 here).

Also, for LOGIOR-DERIVE-UNSIGNED-LOW-BOUND it is possible, while making the code somewhat more complex, to make the commonly occurring cases even be faster than with the current version. Replace the code above by:

   (cond ((= a c)
          a)
         ((and (<= a d) (<= c b))
          (max a c))
         (t
          (let* ((mask-x (1- (ash 1 (integer-length (logxor a b)))))
                 (mask-y (1- (ash 1 (integer-length (logxor c d)))))
                 (index-x (integer-length (logand mask-x (lognot a) c)))
                 (index-y (integer-length (logand mask-y (lognot c) a))))
            (cond ((= index-x index-y)
                   ;; Both indexes are 0 here.
                   (logior a c))
                  ((>= index-x index-y)
                   (let ((m (ash 1 (1- index-x))))
                     (logior (logandc2 a (1- m)) c)))
                  (t
                   (let ((m (ash 1 (1- index-y))))
                     (logior (logandc2 c (1- m)) a)))))))))

[Lutz Euler (lutz-euler)]

The attached patch shows how the LOGIOR bounds can be derived.

Joining the calculations for the low and the high bound allows sharing of work which makes the above-mentioned case with both arguments being (INTEGER 0 18446744073709551615) take only 50 percent more time than the orginal implementation (when both bounds are needed, which is always the case).

The algorithm runs in constant time if all arguments are fixnums and in linear time in the number of bignum digits otherwise.

[Paul Khuong (pvk)]

How about just punting on the bounds when they get too large (say around 10x n-word-bits)?