build_numeric_ranges sometimes builds invalid ranges

[shane]

CategorySelectMatchSpy::build_numeric_ranges can occasionally construct ranges where one interval overlaps all others.

The attached python script shows the problem (apologies for the external dependency). It prints the range constructed:

[((11.949999999999999, 60.0), 2), ((14.5, 14.5), 1)]

when it should be:

[((11.949999999999999, 11.949999999999999), 1), ((14.5, 14.5), 1), ((60.0, 60.0), 1)]

This was using fedora 10 on x86_64.

The attached patch fixes this.

b was getting set to size_t(-1) due to taking the floor of a number that was slightly on the wrong side of 0. It then later got set to n_buckets and that resulted in items that should have been in the smallest bucket ending up in the largest one.

[Olly Betts]

I don't think floor -> round is the correct fix here - that will put values in the wrong bucket.

The variable lo should be the lowest value, and:

start = floor(lo / unit) * unit;

And unit should be positive.

So start should be strictly less than any value being considered...

If it was x86 I'd suspect excess precision, but you say it's x86-64.

I've added some assertions to try to narrow down what is going wrong.

[Olly Betts]

Um, not strictly less - I meant less than or equal...

[shane]

Ah, ok, I understand why you're rounding down.

It seems that sometimes start > lo due to fp rounding.

In my example, I have:
lo = 11.949999999999999289457264239899814128875732421875
unit = 0.01000000000000000020816681711721685132943093776702880859375
and get:
start = 11.9500000000000010658141036401502788066864013671875

This also happens on Opteron.

I guess the solution is:

if (start > lo) start = lo;

[Olly Betts]

Yes, that fix seems good.

I'll it to trunk.

It would be nice to have a regression test for this that doesn't require xappy - should be easy enough now we know what's going on I think - but this code isn't actually currently even built used on trunk...

[Olly Betts]

Richard confirms this is definitely fixed on trunk and there's a regression test in xappy's testsuite.

He said on IRC he'd check if there was a xapian test for it, so reassinging.

[Richard Boulton]

Added a Xapian test in r13658, which passes with trunk, but fails if the fix (from r11812) is reverted.

Closing this, therefore. Not marking it as applying to a particular milestone, since when it was actually fixed, it applied to the matchspy branch, and the fix was included before the matchspy features were added to trunk.

[Olly Betts]

I think "fixed in 1.1.4" is probably appropriate since you just committed a regression test for it which will debut there.