Excessive compilation time for an expression involving LOGIOR on bignums
Affects  Status  Importance  Assigned to  Milestone  

 SBCL 
Medium

Unassigned 
Bug Description
The expression
(let ((a (logior (expt 2 100000) (random 2)))
(b (logior (expt 2 100000) (random 2))))
(integerlength (* a b)))
takes several seconds until a result is printed. Profiling shows that this time is spent in LOGIOR
The reason is that LOGIOR
Tested with sbcl1.1.1 on x8664 on linux, but these functions were last changed in 2005.
Lutz Euler (lutzeuler) wrote :  #1 
Lutz Euler (lutzeuler) wrote :  #2 
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 abovementioned case with both arguments being (INTEGER 0 184467440737095
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) wrote :  #3 
How about just punting on the bounds when they get too large (say around 10x nwordbits)?
Changed in sbcl:  
status:  In Progress → Fix Committed 
assignee:  Lutz Euler (lutzeuler) → nobody 
Changed in sbcl:  
status:  Fix Committed → Fix Released 
I have found a way to make the LOGIORDERIVE... functions use linear time in the worst case which should be applicable to LOGAND and LOGXOR, too. Replace the loop in LOGIORDERIVEUNSIGNEDLOWBOUND with:
(let* ((maskx (1 (ash 1 (integerlength (logxor a b)))))
(logior (logandc2 a (1 m)) c)))
(logior (logandc2 c (1 m)) a)))))))
(masky (1 (ash 1 (integerlength (logxor c d)))))
(indexx (integerlength (logand maskx (lognot a) c)))
(indexy (integerlength (logand masky (lognot c) a))))
(cond ((= indexx indexy)
;; Both indexes are 0 here.
(logior a c))
((>= indexx indexy)
(let ((m (ash 1 (1 indexx))))
(t
(let ((m (ash 1 (1 indexy))))
Unfortunately this slows down some common cases; for example in a large percentage of the calls to LOGIORDERIVEUNSIGNEDLOWBOUND during compilation of SBCL itself (on x8664) 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 LOGIORDERIVEUNSIGNEDLOWBOUND 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)
(masky (1 (ash 1 (integerlength (logxor c d)))))
(indexx (integerlength (logand maskx (lognot a) c)))
(indexy (integerlength (logand masky (lognot c) a))))
;; Both indexes are 0 here.
(logior a c))
((>= indexx indexy)
(let ((m (ash 1 (1 indexx))))
(logior (logandc2 a (1 m)) c)))
(t
(let ((m (ash 1 (1 indexy))))
(logior (logandc2 c (1 m)) a)))))))))
a)
((and (<= a d) (<= c b))
(max a c))
(t
(let* ((maskx (1 (ash 1 (integerlength (logxor a b)))))
(cond ((= indexx indexy)