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

[Sebastian Godelet]

On Mon, 22 Dec 2014 17:22:21 +1100
Paul Bone <paul at bone.id.au> wrote:

> On Mon, Dec 22, 2014 at 05:08:36PM +1100, Zoltan Somogyi wrote:
> > 
> > 
> > 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?
> 
> I mean that if we don't already we should try to strenght-reduce / to
> right shift and that this should be done before we convert / to
> unchecked quotent or >> to unchecked_right_shift.
Being still rather unfamiliar with the Mercury internals,
if implementing unsigned integer arithmetic is hard, how about
the unsigned right shift operator as Java has it (>>>), as Java is also
lacking unsigned integers, that really helps when doing bitwise
operations, since that way signed integers can be treated as unsigned
integers for that particular operation.
> 
> (We might already do this, I havn't spent a lot of time in simplify.m)
> 
> > > > > 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 :-(
> 
> Yes, that's also one of my concerns.
> 
>