Incorrect results for binary search on large arrays due to miscomputation of midpoint about d3-array HOT 11 OPEN

from d3-array.

for reference https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Unsigned_right_shift

from d3-array.

Fun! Does this manifest in practice? The largest array I've been able to generate has 2,145,386,496 Uint8 elements, and it seems that d3 bisects it correctly.

from d3-array.

In Safari the following code freezes the tab, which I think is compatible with the idea described here.

a = new Uint8Array(2147483649)

d3.bisectRight(a, 0)

https://github.com/d3/d3-array/blob/main/src/bisector.js#L34-L44

The comparison will always be zero, so lo will be incremented, even though mid is no longer in [lo, hi).

from d3-array.

Confirmed with Safari's debugger – after a few iterations, e is the left endpoint, i is the (exclusive) right endpoint, and r is the midpoint (zero!)

from d3-array.

from d3-array.

All good questions.

It looks like this isn't a common issue right now, but given the direction things are heading I wouldn't be surprised if Chrome lifts the limit at some point in the next few years. Binary search has a rich history of bugs like this, which weren't discovered until many years later when data sizes increased. :)

I took a quick look and d3 uses the x >>> 1 idiom in other places, some of which would probably want a similar update.

FWIW I noticed this while experimenting with techniques for interactively zooming and panning ~billion-point datasets on the client side, which is a fairly niche use case right now.

from d3-array.

Actually, I think we could just use

const mid = lo + (hi - lo) >>> 1;

as a strict improvement, which will work correctly for a larger range of values.

I was also reminded today of the existence of Math.trunc, which would work for this case and is said to be faster than Math.floor, though I haven't benchmarked it:

const mid = lo + Math.trunc((hi - lo) / 2);

from d3-array.

Is there any reason not to use the simpler form?

const mid = Math.trunc((lo + hi) / 2);

I mean sure, you could run out of integer precision when adding lo + hi, but that should only happen if the combined index is greater than or equal to 2^53 (9,007,199,254,740,992). Which at a minimum would represent 9 petabytes of memory. And if d3-array is being used on a supercomputer of that size… well, they’d probably find other problems lol.

from d3-array.

That's a good point. I don't see any issues with the simpler form.

Which at a minimum would represent 9 petabytes of memory. And if d3-array is being used on a supercomputer of that size… well, they’d probably find other problems lol.

😄

from d3-array.

Related https://lemire.me/blog/2022/12/06/fast-midpoint-between-two-integers-without-overflow/

from d3-array.