13 Oct 1999 01:15:59 -0400

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) |

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.