# Re: Frequency of integer division in source code?

## pardo@cs.washington.edu (David Keppel)Thu, 17 Feb 1994 21:23:24 GMT

From comp.compilers

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)
| List of all articles for this month |

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