News for hackers. Stuff that matters.
Re:How We Beat C++ STL Binary Search by myle on Tuesday August 11, 2015 @04:23PM (#10044102)
Isn't version 2 wrong, because

    size_t probe = (low + high) / 2;
may overflow?
Re:How We Beat C++ STL Binary Search by eloff on Tuesday August 11, 2015 @04:30PM (#10044172)
Not if low and high are both unsigned (size_t is unsigned.) Even if it overflows, the result will be correct. See: http://googleresearch.blogspot.com/2006/06/extra-extra-read-...
Re:How We Beat C++ STL Binary Search by jongraehl on Tuesday August 11, 2015 @05:29PM (#10044541)
for 64 bit size_t it's pretty academic, but no, not correct.

suppose low is M-3 and high is M-1 (where M is 2^[#bits]) then mid should be M-2. but (M-3 + M-1) is (modulo M) equal to M-4. and half that is M/2 - 2, which is a lot less than the correct M-2. (pretend it's 2 bit unsigned ints so M is 4)

the correct 'mid' computation is low + (high - low)/2.

Re:How We Beat C++ STL Binary Search by cautious_int on Tuesday August 11, 2015 @04:41PM (#10044239)
That blog is wrong. The program won't be undefined( unsigned wrap is defined ), but the offset will not be correct.
Re:How We Beat C++ STL Binary Search by dastbe on Tuesday August 11, 2015 @11:23PM (#10045858)
So the article isn't wrong, but its misleading you into thinking this should be correct for the wrong reasons.

They are using signed integers as their indices, which means that the signed bit is always 0. Thus the addition after casting to unsigned will never overflow, and you can divide by two (shift by 1) and then recast to a signed integer, no harm no foul.

Re:How We Beat C++ STL Binary Search by cautious_int on Wednesday August 12, 2015 @01:50AM (#10046243)
Actually it is misleading by them( and you ) to assume that in C, an unsigned int can represent values larger than the largest signed int value.

In other words, C allows that UINT_MAX == INT_MAX, in which case you will overflow.

If they made that assumption, they should explicitly mention it, but they didn't.

> Update 17 Feb 2008:... ...Now that we've made this change, we know that the program is correct;)

It seems the article is aware of the irony. Another update would be in order.

Re:How We Beat C++ STL Binary Search by dastbe on Wednesday August 12, 2015 @10:47AM (#10047969)
Sure, and if you expect your software to run on such a platform with any degree of confidence then you're right to consider it. Even better, tell us about a conforming implementation that you've used in product recently that has UINT_MAX == INT_MAX.

Also I'm not trying to mislead people into thinking that its a good way to implement this. The confounding bit from the article is they started in Java and ended up in C. If you were indexing with signed ints in C, C++, or any language that has unsigned integers then you already have a bug with or without the bad mean check.

Re:How We Beat C++ STL Binary Search by cautious_int on Wednesday August 12, 2015 @11:11AM (#10048117)
You got it backwards there. Only if you know your implementation and plan to code only for it, can you even start to consider bending the C Standard, and not the other way around.
Re:How We Beat C++ STL Binary Search by eloff on Tuesday August 11, 2015 @07:03PM (#10044986)
They didn't say unsigned overflow was undefined, but you're right that the offset won't be correct. I thought it seemed intuitively wrong to me, but I figured google research is probably a reliable source!
Re:How We Beat C++ STL Binary Search by banachtarski on Tuesday August 11, 2015 @09:22PM (#10045486)
That's not true. Unsigned wrap is well-defined and wraps around to 0. Signed wrap is undefined.
Re:How We Beat C++ STL Binary Search by cautious_int on Wednesday August 12, 2015 @01:38AM (#10046213)
It is not true that unsigned wrap is defined? Did you even read my comment, here is the relevant part: unsigned wrap is defined
Re:How We Beat C++ STL Binary Search by rrrlasse on Tuesday August 11, 2015 @06:50PM (#10044939)
True, but only if the list has more than 2^31 entries on a 32-bit machine.

In practise that's not possible if it contains 32-bit integers because that would take up a 16 GB linear address space which doesn't exist on a 32-bit machine.

An academically correct version would be `size_t probe = low + ((high - low) / 2);` but that would be much slower.

You could instead just add an initial debug-mode-only assert on the list length, for correctness.

Re:How We Beat C++ STL Binary Search by maxlybbert on Tuesday August 11, 2015 @10:17PM (#10045634)
Sun had to put out a JDK bug fix for this nine years ago ( http://googleresearch.blogspot.com/2006/06/extra-extra-read-... ).