Improve scaling of type derivation for LOG{AND,IOR,XOR}.
authorLutz Euler <lutz.euler@freenet.de>
Mon, 29 Apr 2013 20:35:01 +0000 (22:35 +0200)
committerLutz Euler <lutz.euler@freenet.de>
Mon, 29 Apr 2013 20:35:01 +0000 (22:35 +0200)
commit62f92bd02e9c04a46893ff9e7b88acdaeab230fa
tree2632c61f09ef4eed9d34d7d046678accd325a33c
parent423b1f8cba83d16e57e852a51cf5d51ef709b2ed
Improve scaling of type derivation for LOG{AND,IOR,XOR}.

If the types of the arguments of LOG{AND,IOR,XOR} are known to be ranges
of non-negative integers the compiler currently derives the range of the
result using straightforward implementations of algorithms from
"Hacker's Delight". These take quadratical time in the number of bits of
the inputs in the worst case, potentially leading to unacceptably long
compilation times. (The algorithms are based on loops over the bits of
the inputs, doing calculations during each iteration that are themselves
linear in the number of bits of their operands.)

Instead implement bit-parallel algorithms I have found that take linear
time in all cases. While their runtime therefore is limited to much
smaller values for large inputs, it is comparable to that of the current
algorithms for small inputs, too; the new deriver for LOGXOR is in fact
faster than the old one by a factor of two to ten already in the latter
case.

The (existing) test for these derivers compares their results with those
from a brute-force algorithm for all O(N^4) many pairs of input ranges
with endpoints from the set of N-bit unsigned integers. The brute-force
algorithm needs to consider O(N^2) input pairs for each pair of ranges,
making the total runtime O(N^6). Therefore the test normally runs with
N = 5. I have tested all three new derivers successfully with N = 7.

Replace LOG{AND,IOR,XOR}-DERIVE-UNSIGNED-{LOW,HIGH}-BOUND with
LOG{AND,IOR,XOR}-DERIVE-UNSIGNED-BOUNDS to make it possible to evaluate
expressions only once that the calculations for the low and the high
bound have in common. The callers always need both bounds anyway.

Adapt the test to this change. (It runs twice as fast now due to the
brute force loop calculating both bounds in one go.)

Add a test for the scaling behaviour. This needs a function to measure
runtimes over potentially large ranges; add this to test-util.lisp.

Fixes lp#1096444.
CREDITS
NEWS
src/compiler/bitops-derive-type.lisp
tests/test-util.lisp
tests/type.pure.lisp