Commit [62f92b] Maximize Restore History

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.

Lutz Euler Lutz Euler 2013-04-29

changed src/compiler/bitops-derive-type.lisp
changed tests/test-util.lisp
changed tests/type.pure.lisp
changed CREDITS
changed NEWS
src/compiler/bitops-derive-type.lisp Diff Switch to side-by-side view
Loading...
tests/test-util.lisp Diff Switch to side-by-side view
Loading...
tests/type.pure.lisp Diff Switch to side-by-side view
Loading...
CREDITS Diff Switch to side-by-side view
Loading...
NEWS Diff Switch to side-by-side view
Loading...