Re: Frequency of integer division in source code?

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

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