Re: Modulo optimizations

Joe Keane wrote:


> Or maybe this is the right thing:
>
> x = ISPOW(z) ? y & (z - 1) : y % z;


If y is a signed number, if this is Java, C++ or C, then this
transformation is probably not what you intended, because Java % and
in most cases C/C++ % has round-to-zero behavior, not
round-to-negative infinity.


However, if what you were computing was in fact the mathematical
modulus, then it is helpful to write ISPOW(z) in a particular way:


  ISPOW(z) is (z-1)&(-z) == 0


the z-1 is, of course, used in the subsequent mod operation.
Yes, there are cases where I've used this and it has been faster.


> The cost of missed branches is something to keep in mind.


Very, very true on modern machines. The benchmarks I've done
have been pretty surprising along these lines; in the case of
division by powers of two, it is more efficient to execute


    movl input, temp
    srl temp,31
    and temp,"divisor-1"
    add input, temp
    sra input, log_2(divisor)


rather than


    test_ge input
    btrue label
    add input, "divisor-1"
label:
    sra input, log_2(divisor)


on a Pentium Pro.
--
David Chase -- chase@naturalbridge.com
NaturalBridge LLC -- http://www.naturalbridge.com

Return to the comp.compilers page.
Search the comp.compilers archives again.