Nearly All Binary Searches and Mergesorts Are Broken (2006) | Hacker News Reader

Nearly All Binary Searches and Mergesorts Are Broken (2006)

research.googleblog.com

98 pointsrargulati86 comments

Previous discussions at https://hn.algolia.com/?query=Nearly%20All%20Binary%20Search...

That line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.

Agreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).

Simply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.

If "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type.

Of course sorting 2^63 elements would require the different calculation.

Pointers are 64-bit on 64-bit machines, and so are the largest unsigned ints, hence the problem. On the other hand, you're probably searching at least 4-byte objects, so your actual list length isn't 64 bits but at most 62 bits even if you filled the memory space.

It doesn't, by itself, fix the bug identified in the article (though it does avoid a memory safety issue). But it's still important. Indexes should never be signed, any more than pointers should.

Why not? Indices are not pointers, so that's a poor argument by itself. Indices are offsets to pointers. If you can see any use for a negative offset off a pointer, that's your negative index use case. A nice example use is implementing IIR filters in a way that looks like the common mathematical form:

    y = a[0]*y[-1] + a[1]*y[-2] + b[0]*x[-1] + b[1]*x[-2]

For C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.

> size_t is guaranteed to be large enough for the target architecture

I'm not sure if you've misunderstood this (some of the other comments mentioning type certainly have) but size_t being large enough for the purpose of indexing an array is absolutely not the issue. The issue, illustrated by the glibc code pishpash shared, is that a size_t (or any other integer type) is not necessarily large enough to hold the sum of two other variables of the same type without overflowing.

Right, my comment wasn't intended to imply that simply changing the type was a fix for the bug. Just that the best practice is to use size_t for the index types, you still have to perform the calculation in a way that won't overflow.

Here's some code you can compile, it shows the problem:

  #include <stdio.h>
  #include <stdint.h>
  
  int main() {
    printf("size_t bytes: %u\n", sizeof(size_t));
    
    size_t high = SIZE_MAX;
    size_t low = high-1;
    size_t mid_correct = low+(high-low)/2;
    size_t mid_incorrect = (low+high)/2;
    
    printf("low: %.ju\n", low);
    printf("high: %.ju\n", high);
    printf("low+high: %.ju\n", low+high);
    printf("(low+high)/2 -- incorrect: %.ju\n", mid_incorrect);
    printf("low+(high-low)/2 -- correct: %.ju\n", mid_correct);
  }

On my 64-bit machine, I get:

  size_t bytes: 8
  low: 18446744073709551614
  high: 18446744073709551615
  low+high: 18446744073709551613
  (low+high)/2 -- incorrect: 9223372036854775806
  low+(high-low)/2 -- correct: 18446744073709551614

This is a great illustration of the actual bug.

The range of size_t only comes into play if the array can potentially be huge. If the array is small, there may be other considerations. Suppose you have a displaced array with negative indices: p[-2], p[-1], p[0], p[1], ... size_t is good for nothing here.

The unsigned types are generally awful; they have a big discontinuity right at zero, so you have to be careful with arithmetic even if it involves small values.

If I'm working with int and I know that all quantities fit into two decimal digits, then there isn't possibly any problem. Not so with unsigned int or size_t or what have you.

If a, b, c are small integers in a signed type then I know I can rewrite a < b + c as a - c < b, following straight algebraic rules of derivation. Not so if these are unsigned; moving c from the right side to the left may break the inequality because a may be smaller than c.

Even with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-defined, the result here is still nonsense. (i.e., while the result of (low + high) >> 1 during overflow will be well defined, it won't be the midpoint…)

You might argue that you're never going to overflow a size_t on a 64-bit, maybe, but given that the correct code is right there above in the article, it seems easy enough to just do the right thing (add half the delta to the lower bound, which avoids overflow all together for unsigned integer inputs).

With size_t, it would never overflow, even on 32 bits.

The input is an array of int, ints are 4 bytes, 32 bit systems can only address 2^32 bytes, so the array is no more than 2^30 elements long, so in the worst case, low+high equals 2^31-3, less than even a signed it.

It could overflow if we pass it a char* instead but if you have a >2GB array of sorted single bytes, you probably have a problem somewhere else...

Programmer: "The bug is in the choice of data type. Use unsigned ints to index arrays."

Computer scientist: "The bug is in the language. Signed integer overflow behavior should have been defined in such a way as to guarantee correct functionality in cases such as this."

Me: "Use int64s for this sort of thing. It's still broken, but I'll be retired or dead before anyone notices."

Engineer: "The bug is in the documentation. The program is correct but should have been specified for use with element counts no greater than INT_MAX / 2."

Mathematician: "A solution exists."

Manager: "Ship it."

Mathematician: "I conjecture that a solution exists."

I'm surprised about the suggested solution for java:

  int mid = (low + high) >>> 1;

I suppose things like this is why the ">>>" (unsigned shift) operator exists - but it's a bit odd when the value it works on is considered signed by the language, and implemented as two-compliment signed in memory.

What's interesting to me is that this allows the sum to overflow, and would fail with the ">>" operator as far as I can tell (signed shift) - just like the original code would fail with simply dividing by 2.

Guess it shows java's "system language" roots - in that one might expect there to be a way to be alerted to overflow when working with signed integers - but the solution here is to use a special operator to "fix" the problem.

Maybe it's just me, but it's a solution that would feel more at home in assembler, than I personally think it does in java.

I agree it would be very surprising to see that line in a java codebase. >>> seems more like an answer to a java trivia question than something you'd come across on a regular basis.

Thinking a bit more about this, I think what feels off about it to me, is the invisible "type gymnastics" - it's something that might be a bad idea, but feel more natural, in assembly (that byte is what you decide it represents at any given moment). The individual numbers are signed ints, the sum overflows and is treated as an "unsigned two's complement binary" and shifted down to a signed int...

It feels like subtle subversion of java's admittedly strange type system for numbers (mix of raw integer types and boxed numbers is never going to be pretty...).

So what 'bout this? It's the latest glibc.

https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source....

The problematic line is:

__idx = (__l + __u) / 2;

__idx, __l, and __u are all the same type and the addition of __l and __u could cause an overflow resulting in a nonsense value assigned to __idx.

Seems like it's still an open ticket:

https://sourceware.org/bugzilla/show_bug.cgi?id=2753

> int mid = low + ((high - low) / 2);

That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search.

For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) < 0 and f(b) > 0, and you want to find an n in (a,b), if such n exists, such that f(n) = 0. Binary search on [a, b] is a reasonable approach.

If a < 0 and b > 0, then that mid computation could overflow on the subtraction.

In that case, then you can to go back to

    int mid = (low + high) / 2;

but you'd have to constrain low and high to be in the range [-2^30, 2^30 - 1] so as to not overflow a (assuming 32-bit) signed integer. (And you're probably using 64-bit floating point, or similar, which has other fiddly bits.)

However, the article specifically talks about merge sort in arrays, so low (your "a") is always >= 0. The discovery was "oh, we went decades before someone had to sort an array with more than 2^31 elements". Frankly, it's akin to when we ran out of IPv4 addresses -- when it was originally built, there was some range over which the computation was defined to be correct, and we later discovered that we wanted to do computation outside that range.

I'm tempted to suggest

    (low / 2) + (high / 2)

but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.

That won't get you the middle, these are integer divisions.

Yes, that's why I said: "but then I have to think about rounding error. Ugh." Because integer division rounds. (Or truncates, if you prefer.)

Plus, an extra operation, at least compared to some of the shift-based fixes.

Rouding error can be taken care of:

https://news.ycombinator.com/item?id=14908117

Bullet proof:

    mid = lo / 2 + hi / 2;

Well, that is, if your algorithm can tolerate a mid == 6, for hi == 7 and lo == 7. :) :) :)

Cough, cough; seriously though: here is a variant based on the above idea which takes care of the remainders, avoiding that problem:

   ;; TXR Lisp
   (defun mid (lo hi)
     (tree-bind ((lq lr) . (hq hr)) (cons (trunc-rem lo 2) (trunc-rem hi 2))
       (+ lq hq (trunc (+ lr hr) 2))))

trunc-rem has toward-zero truncation, with a remainder that is harmonized to that.

Based on my testing in the REPL, this is behaving sensibly.

Adding the quotients, and then adding to them the sum of the remainders, truncated by two, seems to be doing the trick.

(mid 7 7) is 7, (mid -7 -7) is -7 and various other cases are all sensible. (mid k (+ 2 k)) is yielding (+ 1 k), for both values being negative, either being zero, and zero-crossing cases. (mid k k) seems to be k for all k.

I think as of ISO C99, the / and % operators truncate toward zero. Unless I'm gravely mistaken, this is then nicely expressible in C as:

  lo / 2 + hi / 2 + ((lo % 2) + (hi % 2)) / 2;

It's mathematically well founded: we have added the truncations, and then continue working with the remainders. This is because the following expression in fact expresses the exact result.

  trunc(lo,2) + trunc(hi,2) + (rem(lo, 2) + rem(hi, 2))/2

where / is exact rational division! Dividing the remainders by two just continues the inexact division, completing it to exactness. What we're doing differently in the machine calculation is using truncating division on the sum of the remainders, which we need because mid is to be an integer result.

I don't think that is broken. The algorithm is sound conceptually. I was almost looking for some type of theory where all mergesorts and binary searches could be improved.

Agreed. This was a very underwhelming article.

(High-low) works, well if we consider this from a pointer pov!

Won't this line have similar issue?

  return -(low + 1);  // key not found.

A more modern version of this is: nearly all discussion about sorts that claims computers can't do search in better than O(n log n) are wrong and have been for some time.

Edit: I'm quite surprised I'm being modded down given the magnitude of what I'm implying. I suspect someone doesn't understand what I'm saying.

The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.

Right, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions.

I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'm still working through the papers, the base of that chain is like 86 pages long!

This search fallacy has been corrected. I'm mentioning one that hasn't.

Huh, is this the stuff you're talking about:

    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
    http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf
    https://www.youtube.com/watch?v=sz9ZlZIRDAg
    https://hackage.haskell.org/package/discrimination

I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.

Yes that is it. And it's really a variation on radix sort as well. They're all in the same general family.

I can't believe I got down voted for this thread. What does it take?

I guess I should just post it.

Given how few of those posting tonight appeared to understand the import of what Joshua Bloch wrote, I wouldn't take it personally. I'm slightly shocked by it, but I wouldn't take it personally...

I did post it, I even said provocatively, "O(n) general sort" in the title. Sadly the point gods were not kind.

Classic programming defect !

I wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit.

It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could it be possible to predict?

I wish it was worth a lot to be good at assembly these days. It seems like the huge salaries are for c++ devs. I spent like ten years getting really good at this stuff but nowadays it feels like being really good at trivial pursuit.

Edit: Did not mean to "mock" the OP, just merely trying to showing that you can apply that thought to almost anything in the programming world by replacing the technology/language names.

Are you mocking the parent poster? Why?

Nah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain.

http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this.

EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515

That's an amazing article. Thanks for sharing.

Yes and no. My response to that article is "The more things change, the more they stay the same." There is no steam roller. The fundamentals are not changing. So much touted (even here on HN) as new and innovative are little more than re-hashed versions of what we were already using 5, 10, 20, 30 years ago, just prettier. Sure the syntax is always changing a little, and the frameworks and tools are evolving, but at a fundamental level the job of a programmer is little different now than it was in any of those eras. I have no doubt that a competent programmer from then, if picked up and plopped in front of a MacBook in 2017 could do a little reading up and perform proficiently in most programming jobs today. Probably more proficient because 1. they've seen it all before including the bugs and pitfalls and 2. I'd argue programming is much easier today than it ever has been.

EDIT: I swear I did not read the top comment in the (newly) linked HN discussion of that article before I wrote my response. I agree completely.

I really wonder about this. It seems true to me that it's easier now and anyone who could do it back when it was harder could do it now.

But then, I wonder if it just seems that way to me because I'm a product of "now", which makes me more proficient in how we do things now, which makes it seem easier. It's possible neither is easier, that they are just different, and for everyone, the other seems harder than the one they already know.

I'm not trying to argue that this is the case: I could see it being either way and I sincerely wonder which way it is.

grep for "fundamentals" | "first principles" in that article.

It is worth a lot to be good at assembly these days. It's a big piece of how my team makes a living. As one of my older colleagues puts it: there are fewer relevant jobs, but those jobs pay significantly more money, and you can only hold one job at a time.

Except it's a bad analogy. Rails is not the next step up from systems level programming, it's a completely different (and honestly far less difficult) domain. Most of those rails devs could never be good at the hard stuff.

It's still worth a lot to be good at systems programming. Outside of the HN bubble there are plenty of companies willing to pay extremely well for people who can do systems programming, particularly under high performance constraints.

Name 5 please

google facebook microsoft amazon baidu

All of those places will pay just as much for (as well as hire far more of) enterprise Java/Go/HTML/JS code monkeys There's nothing wrong with that, but picking 5 companies with their hands in damn-near anything is disingenuous.

Is your goal to be paid extremely well for doing systems programming relative to other people in the same company? Or to be paid extremely well for doing systems programming?

The latter: solid salary for sys

So it's less about getting paid for your work and more about a dick measuring contest with your coworkers.

I think that's your issue.

ng nasa boeing lockheed spacex

name 5 companies and typical salary ranges for junior dev or senior developer experience.

The current hotness is AI/machine learning/deep learning. Maybe after that it will be something like "quantum programming"?

Just my guess.

http://www.newsweek.com/2017/04/21/quantum-computing-ibm-580...

It seems like in that field you can use some of your knowledge of system programming. Overflow and underflow happens a lot with the big data volumes you face. Another systems programming topic discussed in most big data courses is floating point accuracy.

Understanding floating point arithmetic is even more important than over/underflow of integers in dynamic languages such as Python (see e.g. https://www.python.org/dev/peps/pep-0237/).

The next boom will be in whatever _isn't_ being hyped right now.

There was definitely a recent boom in fintech / high-frequency trading.

The problem is these sorts of things are trivia. They are things that sufficiently smart tooling should handle for us so people can spend time building higher level constructs and less time worrying about individual bits.

A smart compiler should have caught (a + b) / 2 and fixed it to be correct, there's no way the overflow situation is what the programmer wanted.

"sufficiently smart tooling" has got to be one of the best jokes in programming.

On one hand, it is true that the tooling is possible. On the other hand, it remains an open problem.

http://wiki.c2.com/?SufficientlySmartCompiler

I'd accept a warning, but a C compiler shouldn't be making guesses at what the programmer intended. In another language? Sure, if it's consistent with other behaviors in that language.

If you don't mind me asking how did you get into Systems Programming? (Or how would you recommend someone getting into it?)

I liked xv6. https://pdos.csail.mit.edu/6.828/2016/xv6.html

https://pdos.csail.mit.edu/6.828/2016/xv6/book-rev9.pdf

https://pdos.csail.mit.edu/6.828/2012/xv6/xv6-rev7.pdf

The labs are very informative: https://pdos.csail.mit.edu/6.828/2016/labs/lab3/

I also worked through the 6.824 Distributed Systems course, which is a lot of fun:

https://pdos.csail.mit.edu/6.824/

Lab 4 is fiendishly difficult, but you end up learning a lot.

Beyond all that, there's no substitute for just diving in and breaking stuff. Just go with whatever area you find the most fun. Maybe that's compiling and modifying the Linux kernel, or maybe it's tweaking a software rasterizer like https://github.com/blitzcode/rust-exp.

I got into systems programming mainly as a consequence of being a game developer -- when you write your own engines, you're forced to consider a hundred low-level details like memory layout, pipelining, threading, simulation, adding a scripting interface for your designers, cursing AMD when you run into GPU driver bugs, etc. There are a lifetime worth of interesting problems to solve in that area.

The bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.

Big integer by default is a terrible idea. Just look at Python 3.

Python 2 was bigint by default. Not even going to deconstruct your argument past that

I didn't say it wasn't...?

I didn't say you didn't say it wasn't

It works fine in Common Lisp. What's the problem with it in Python?

Could you expand? The number tower is one of the things I happen to like about python 3, but apparently you think there's something wrong? Performance?

Erlang has arbitrary length integers by default, and I've found it to be incredibly liberating.

I thought Erlang didn't even have random access. Might not be the best fit for an in-place quicksort.

The bug isn't in the language, you just disagree with some of the goals. It was designed for the compiler to be small and easy to write, with data types and operations that map directly to operations that most CPUs can perform.

The bug is in the author's understanding of his choice of language. The language did a perfectly reasonable thing.

Still, the formula low + (high - low)/2 keeps the integers smaller (assuming everything is positive). That is to say, it can work with larger values before requiring bignums compared to (low + high) / 2. On the other hand, it is more operations.

* for arrays with counts over a billion if you choose to use signed 32-bit integers for array indexes.

Not that it isn't a potential problem, but it's a narrow issue.

Reply on news.ycombinator.com