[m-rev.] for review: fix possible integer overflow in binary search

[Zoltan Somogyi]

On Mon, 22 Dec 2014 16:12:59 +1100, Paul Bone <paul at bone.id.au> wrote:
> > I am in committing a modified version of your diff, which uses
> > unchecked_right shift instead of >>, and which applies the fix
> > to some more places that also compute Mid similarly.
> > 
> > I will see whether we can make the compiler automatically
> > replace X >> Y with X unchecked_right_shift Y if Y is known
> > to be a constant in the right range. (And similarly for <<,
> > and maybe for some other ops, such as /.)
> 
> If the righthand argument to / is known then we could try to strength-reduce
> / before applying the unchecked optimisation.  The unchecked optimisation
> should still be tried for /.

I don't know what you mean that. What strength reduction can you do
for / that does not involve right shift, other than for division by 1?

> > > Maybe a mid_rounding_down/2 or similar could be included in the int
> > > module.
> > 
> > Maybe, but any code that cares about performance would likely
> > call that predicate in inner loops, and so would want to avoid
> > the expense of a call. That means that it should be a builtin,
> > which means that its addition needs to be in two stages:
> > adding to compiler/builtin_ops.m, and only when that is
> > installed, adding its declaration to library/int.m.
> > 
> > Any opinions about whether this should be done?
> 
> I'm not sure about this particular calculation.  It depends how often it's
> used and the benefit of adding it to int.m.  If people use the
> non-overflowing method, and the compiler optimises things well then I don't
> see the benefit of putting it in int.m

I think that at least 90% of the uses of such a predicate will be
in binary searches, whether in the Mercury library, or in user code.
The main benefit I see in putting such a predicate into int.m is to remind
people of the overflow issue, and that benefit is limited by the fact that
many people who could benefit from such a reminder won't be reading
the documentation for int.m :-(

> It may help if we had separate types for signed and
> unsigned integers.  I know we've discussed this before and I know it's a
> fair bit of work, but it would be helpful.

I agree that it would be helpful, but in this case, "fair bit of work" is
a colossal understatement.

Zoltan.