Re: Modulo optimizations

David Chase <>
13 Oct 1999 01:15:59 -0400

          From comp.compilers

Related articles
Modulo optimizations (Graham Marshall) (1999-10-04)
Re: Modulo optimizations (Joe Keane) (1999-10-11)
Re: Modulo optimizations (1999-10-13)
Re: Modulo optimizations (David Chase) (1999-10-13)
Re: Modulo optimizations (George Russell) (1999-10-14)
Re: Modulo optimizations (Robert Harley) (1999-10-14)
Re:Modulo optimizations (Wilco Dijkstra) (1999-10-19)
Re: Modulo optimizations (Robert Harley) (1999-10-21)
Re: Modulo optimizations (1999-10-27)
| List of all articles for this month |

From: David Chase <>
Newsgroups: comp.compilers
Date: 13 Oct 1999 01:15:59 -0400
Organization: None
References: 99-10-017 99-10-047
Keywords: arithmetic

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"
    sra input, log_2(divisor)

on a Pentium Pro.
David Chase --
NaturalBridge LLC --

Post a followup to this message

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