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

Paul Bone paul at bone.id.au
Mon Dec 22 17:22:21 AEDT 2014


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.

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


-- 
Paul Bone



More information about the reviews mailing list