When are bugs not really bugs?

Discussions

News: When are bugs not really bugs?

  1. When are bugs not really bugs? (9 messages)

    A blog entry from Tim Bray ("On the Goodness of Binary Search") was updated to highlight a bug pointed out by Josh Bloch (and mentioned in TSS' blogs section) in most binary search algorithms. While the explanation makes sense (it's related to integer overflow), it raises a question: how serious is this bug? Does context play a part? Josh mentions that the bug has been in the JDK's implementation of binary search for nine years, and many public algorithms also suffer from it (the Wikipedia article on binary search has a version immune from overflow - but the history of the article shows that the overflow was removed fairly recently, on 25 March 2006). Most of us have used binary searches before, either from writing them ourselves or using others' implementations, but it's a fair guess that most of us haven't had to deal with sets large enough to fire off the bug. Integer.MAX_VALUE is 2147483647, roughly 2.1 billion. Your set would have to be 1,073,741,825 elements long to cause an overflow (and the overflow would only occur if the search led to the last few elements in the set, of a set that size.) It's fair to say that corner case testing would have exposed the bug, but while corner cases are usually simple, constructing this particular case is nontrivial; it overflows RAM on every single machine your Humble Editor possesses, for example. So while the bug certainly existed, and pointing it out is worthwhile, how serious is it - really? Is it worth all the handwringing?
  2. There are no bugs, just undocumented features!
  3. The bug becomes more serious as the size of your array gets closer to Integer.MAX_VALUE. If the array size is greater than 2/3rds of Integer.MAX_VALUE, any item in the second half of the array will trigger the error. It's worth noting that this bug won't exist in languages like Lisp (for example) which have arbitrary length integers.
  4. The bug becomes more serious as the size of your array gets closer to Integer.MAX_VALUE. If the array size is greater than 2/3rds of Integer.MAX_VALUE, any item in the second half of the array will trigger the error.

    It's worth noting that this bug won't exist in languages like Lisp (for example) which have arbitrary length integers.
    Right, but the whole "2/3rds of Integer.MAX_VALUE" is part of the point: an array of that size is staggeringly large. The smallest useful element that would go into that array would be an integer; that's well over 4G of ram solely dedicated to the array. Most people won't even want to work with a dataset that large - and if they do, chances are they're working with even larger object types being stored in the array, increasing the RAM requirements even further. I dare say that the set of people working with that kind of dataset are rare, indeed. It's not like the bug isn't real or worth solving; it's that the people affected by the bug would typically count in the, well, tens. (And yes, I did just pull that number out of a hat.) Therefore, the bug is worth solving, but still generating more discussion than it warrants.
  5. Right, but the whole "2/3rds of Integer.MAX_VALUE" is part of the point: an array of that size is staggeringly large. The smallest useful element that would go into that array would be an integer; that's well over 4G of ram solely dedicated to the array. Most people won't even want to work with a dataset that large - and if they do, chances are they're working with even larger object types being stored in the array, increasing the RAM requirements even further.

    I dare say that the set of people working with that kind of dataset are rare, indeed. It's not like the bug isn't real or worth solving; it's that the people affected by the bug would typically count in the, well, tens. (And yes, I did just pull that number out of a hat.) Therefore, the bug is worth solving, but still generating more discussion than it warrants.
    Agreed. However as Bloch's post points out, arrays of this size are becoming more common as time goes by. A more sensible data structure would avoid the problem, but who knows what other requirements there might be? As far as solving it, there are a couple of solutions mentioned in the original blog entry. I think the real lesson to take away is that there were some unspoken assumptions about the inputs to the binary search code and that is what led to the bug.
  6. The bug becomes more serious as the size of your array gets closer to Integer.MAX_VALUE. If the array size is greater than 2/3rds of Integer.MAX_VALUE, any item in the second half of the array will trigger the error. It's worth noting that this bug won't exist in languages like Lisp (for example) which have arbitrary length integers.
  7. As with most things in life. If someone had said "This binary search won't work for > N items", then no one would be saying boo, because no promise had been broken. But, particualarly nowadays with our vast capacities and resources, we rarely run in to "arbitrary" limits, or bump into the fact that our machines aren't infinite spaces, save perhaps for memory -- but only because we haven't installed it all. I mean, think about the 32-Bit address space of 4GB, and how we're now (for a vast majority of us) just bumping into the capacity limits of 32-bits. This bin search is one of those. If arrays could take a 64-bit long as an index, well, perhaps we wouldn't be having this discussion for another 10 years. But, at its basic form, a bug is where something doesn't meet up with expectations. If a limitation is documented properly, then it's not a bug, rather it's a documented limitation. "Don't do that".
  8. As with most things in life.

    If someone had said "This binary search won't work for > N items", then no one would be saying boo, because no promise had been broken.

    But, particualarly nowadays with our vast capacities and resources, we rarely run in to "arbitrary" limits, or bump into the fact that our machines aren't infinite spaces, save perhaps for memory -- but only because we haven't installed it all.

    I mean, think about the 32-Bit address space of 4GB, and how we're now (for a vast majority of us) just bumping into the capacity limits of 32-bits. This bin search is one of those. If arrays could take a 64-bit long as an index, well, perhaps we wouldn't be having this discussion for another 10 years.

    But, at its basic form, a bug is where something doesn't meet up with expectations. If a limitation is documented properly, then it's not a bug, rather it's a documented limitation. "Don't do that".
    Exactly. It wasn't a documented part of the contract, so either the implementation is at fault, or the contract is. Also, the algoritm is part of Java's core distribution which has millions of users, making the bug more serious/ more likely to be encountered.
  9. Reminds me of Bill Gates' (in)famous phrase, where he said 640K would be more than enough for everyone...
  10. If you are using Java for scientific apps, you're bound to deal with datasets much, much larger than the average JSP page.