Thu, 17 Feb 1994 21:23:24 GMT

Related articles |
---|

[2 earlier articles] |

Re: Frequency of integer division in source code? meissner@osf.org (1994-02-09) |

Re: Frequency of integer division in source code? tfj@apusapus.demon.co.uk (1994-02-10) |

Re: Frequency of integer division in source code? glew@ichips.intel.com (1994-02-11) |

Re: Frequency of integer division in source code? bazyar@netcom.com (1994-02-10) |

Re: Frequency of integer division in source code? cliffc@dawn.cs.rice.edu (1994-02-14) |

Re: Frequency of integer division in source code? chase@Think.COM (1994-02-15) |

Re: Frequency of integer division in source code? pardo@cs.washington.edu (1994-02-17) |

Newsgroups: | comp.compilers |

From: | pardo@cs.washington.edu (David Keppel) |

Keywords: | architecture, optimize, comment |

Organization: | Compilers Central |

References: | 94-02-058 94-02-092 |

Date: | Thu, 17 Feb 1994 21:23:24 GMT |

*>>[Beware of `n = a - b' where sizeof(*a) isn't a power of 2.]*

David Chase writes:

*>[Or you can multiply by ...]*

In some cases, `n' is being computed just to compare against another

variable, e.g. `maxn'. In those cases it is possible to eliminate the

divide and instead multiply `maxn' by `sizeof(*a)'. That is, instead

of

n = a - b;

if (n >= maxn) {

return (NULL);

}

*b = val;

return (b+1);

you do (or better yet, your compiler does it for you):

n' = (char *)a - (char *)b;

maxn' = maxn * sizeof(*a);

if (n' >= maxn') {

return (NULL);

}

*b = val;

return (b+1);

If `sizeof(*a)' is 12, then multiply to compute maxn' takes 3 cycles

instead of the 11 to compute n in David's example.

This trick only works when you don't actually need `n' and where you

can show the multiply won't overflow (it can't in this case or `a - b'

would be nonsense) or can show that the result is the same even in the

presence of overflow. If you have to scale several values (e.g. `maxn'

and also `minn' and also ...) then it may not be profitable.

But it's useful when it works.

;-D on ( Divisive multiplication ) Pardo

[This is a classic technique. If you look up Bresenham's original paper on

rasterizing a line segment, he uses this trick to avoid an expensive

division by two. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.