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

[Zoltan Somogyi]

On Sun, 21 Dec 2014 10:34:54 +0800, Sebastian Godelet <sebastian.godelet+github at gmail.com> wrote:
> But in the current Mercury implementation this is not the case,
> as demonstrated in this gist:
> https://gist.github.com/sebgod/ee1172fd736289aaeaa8

Thanks for catching that. The reason is that when computing
(Lo + Hi) / 2 in Mercury, the intermediate value Lo + Hi is
stored as MR_Integer, not MR_Unsigned, so the following
division (or shift) treats it as signed, not unsigned. The C version
does not have this problem.

> The implementations in the specific grades are taken from this
> article:
> http://googleresearch.blogspot.de/2006/06/extra-extra-read-all-about-it-nearly.html
> But this diff uses the
> > the standard fix for that is to compute it as Lo + (Hi - Lo) / 2.
> together with the >> 1 optimisation.

Actually, in Mercury, that turns out not to be an optimization,
because the Mercury version of >>, unlike the C version,
checks for the right operand being out of range. Because of
these tests, it is not a builtin, so just ">> 1' generates a
procedure call.

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 /.)

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

Zoltan.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Log.mid
Type: audio/midi
Size: 108 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20141221/cc8f3cba/attachment.mid>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: DIFF.mid
Type: audio/midi
Size: 11809 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/reviews/attachments/20141221/cc8f3cba/attachment-0001.mid>