Re: Modulo optimizations

David Chase <chase@world.std.com>
13 Oct 1999 01:15:59 -0400

          From comp.compilers

Related articles
Modulo optimizations gmarshal@globalnet.co.uk (Graham Marshall) (1999-10-04)
Re: Modulo optimizations jgk@jgk.org (Joe Keane) (1999-10-11)
Re: Modulo optimizations torbenm@diku.dk (1999-10-13)
Re: Modulo optimizations chase@world.std.com (David Chase) (1999-10-13)
Re: Modulo optimizations ger@informatik.uni-bremen.de (George Russell) (1999-10-14)
Re: Modulo optimizations harley@corton.inria.fr (Robert Harley) (1999-10-14)
Re:Modulo optimizations Wilco.Dijkstra@arm.com (Wilco Dijkstra) (1999-10-19)
Re: Modulo optimizations harley@corton.inria.fr (Robert Harley) (1999-10-21)
Re: Modulo optimizations Peter-Lawrence.Montgomery@cwi.nl (1999-10-27)
| List of all articles for this month |

From: David Chase <chase@world.std.com>
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"
label:
    sra input, log_2(divisor)


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


Post a followup to this message

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