Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nearly all binary search and merge sort implementations are broken (2006)

googleresearch.blogspot.com

Post reply on HN
Print view View original

61–70 of 70 posts

Re: Nearly all binary search and merge sort implementations are broken (2006)

#61

Post by gsg »

yason wrote: post #55

I don't like the index variables and splitting in half part. I like to write my binary searches with bit patterns: 1) figure out the number of bits required to cover the largest index (= a little bit of cheap bit-twiddling) 3) initialize your index to 0 2) flip a bit on in index, starting from the highest bit available from step 1) 3) if data[index] is smaller than what you're looking for, leave the bit on 4) try wit…

You mean this one?

    int binary_search_pow2(const int a[], int len, int key) {
        int i = 0, step;
        for (step = len / 2; step > 0; step >>= 1)
            if (a[i | step]
I thought that only worked for power-of-two sized arrays.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#62

Post by Confusion »

xyzzyz wrote: post #57
Confusion wrote: post #49

Earlier quoted context omitted.

The programs that can be proven are severely limited in power. For one, the tools to prove correctness of programs can't deal with data other than integers[1]. The way this usually works is that the proof is written and the code is then generated from the proof. That code is then incorporated in something larger, which has not been proven correct. Such is the case with algorithms. You can mathematically prove an algo…

For one, the tools to prove correctness of programs can't deal with data other than integers. This is the first time I hear such claim. Which tools are you talking about? The tools I know (Coq) certainly don't have such limitations -- why would they, anyway?

For performance reasons. The SPIN model checker, which is the state of the art in terms of performance, employs only integers.

Has Coq ever been used to solve an actual practical industrial or business problem, either by generating code from a known correct program or by using the Coq model as an oracle to drive automatic testing? If not, then there's your answer: academically useful proof assistants cannot deal with real world data. Proof assistants useful in the real world can only deal with limited data types to be able to achieve their goal.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#63

Post by exDM69 »

onemoreact wrote: post #15
Bootvis wrote: post #10

Earlier quoted context omitted.

You can prove the correctness of a program given a specification of the language you write it in. But is the compiler you use to compile your program correct? Do you know all processor bugs?

Computer hardware is not correct. So, you need to step past mathematical perfection and write defensively. Rule 1: you can't trust RAM it lies. That said you can build automated tests that add random memory errors to help find the program that's best able to handle memory errors.

I have never seen a piece of software that is built with memory error tolerance is tested against random memory errors. Have you?

Maybe a spacecraft might have some. Error correcting memory, and the software associated with it is, of course, an exception. Is there code dealing with memory errors somewhere in the kernel (of any OS)?

For most programming, it would simply not make sense to try to take memory errors into account. It's very unlikely that in the lifetime of the program, there will ever be a situation where a bit will be flipped and it will have an actual effect.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#64

Post by gjm11 »

ColinWright wrote: post #59
yason wrote: post #55

I don't like the index variables and splitting in half part. I like to write my binary searches with bit patterns: 1) figure out the number of bits required to cover the largest index (= a little bit of cheap bit-twiddling) 3) initialize your index to 0 2) flip a bit on in index, starting from the highest bit available from step 1) 3) if data[index] is smaller than what you're looking for, leave the bit on 4) try wit…

That's really cool - would you care to post some example code so we can see the clarity obtained by this novel approach? Did you come up with it yourself, or did you see it somewhere else?

I think one of Jon Bentley's "Programming pearls" books contains a version of binary search that works more or less that way and shows how to get there from a naive and more obviously correct implementation by successive small transformations. IIRC it ends up having a particularly tight inner loop. And it doesn't, I think, require a power-of-2-sized array. My copy of the book is at home and I'm at work so I can't check any of my recollections right now.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#65

Post by ColinWright »

gjm11 wrote: post #64
ColinWright wrote: post #59

Earlier quoted context omitted.

That's really cool - would you care to post some example code so we can see the clarity obtained by this novel approach? Did you come up with it yourself, or did you see it somewhere else?

I think one of Jon Bentley's "Programming pearls" books contains a version of binary search that works more or less that way and shows how to get there from a naive and more obviously correct implementation by successive small transformations. IIRC it ends up having a particularly tight inner loop. And it doesn't, I think, require a power-of-2-sized array. My copy of the book is at home and I'm at work so I can't che…

You're right - Programming Pearls, column 8 "Code Tuning." It's not quite like this, and it's in some variant of BASIC, but when you squint, it's there.

Thanks.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#66

Post by onemoreact »

exDM69 wrote: post #63
onemoreact wrote: post #15

Earlier quoted context omitted.

Computer hardware is not correct. So, you need to step past mathematical perfection and write defensively. Rule 1: you can't trust RAM it lies. That said you can build automated tests that add random memory errors to help find the program that's best able to handle memory errors.

I have never seen a piece of software that is built with memory error tolerance is tested against random memory errors. Have you? Maybe a spacecraft might have some. Error correcting memory, and the software associated with it is, of course, an exception. Is there code dealing with memory errors somewhere in the kernel (of any OS)? For most programming, it would simply not make sense to try to take memory errors into…

They are a lot more common than you might think, basicly every day every PC has a memory error. If one of the textures in a video game gets corrupted you may not notice it, and if you have real issues simply rebooting tends to work well. Recent tests give widely varying error rates with over 7 orders of magnitude difference, ranging from 10^−10 to 10^17 error/bit·h, roughly one bit error, per hour, per gigabyte of memory to one bit error, per century, per gigabyte of memory.[7][8][9] http://en.wikipedia.org/wiki/Dynamic_random-access_memory The biggest defence for a home user is simply the banial nature of most information stored in memory.

Yet, you don't have to be building a spacecraft for rebooting to be an issue. One example that comes to mind is remote sensors. A friend was working on power meter which reported back it's findings every few days. The initial version used normal programming practices and after a six months field test of a few thousand units the projected failure rate over 10 years in the field was unacceptably high. He said the code was simple and 'correct' but failed to deal with with corruption. His version had less than 1% of the original failure rate in the field and is projected to save the company far more than his 6 month contract to rewrite the thing from scratch.

A more dramatic example is your car's internal engine controls. But, there they simply reboot regularly as there is no need for maintaining state over the long term.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#67

Post by sesqu »

gsg wrote: post #61
yason wrote: post #55

I don't like the index variables and splitting in half part. I like to write my binary searches with bit patterns: 1) figure out the number of bits required to cover the largest index (= a little bit of cheap bit-twiddling) 3) initialize your index to 0 2) flip a bit on in index, starting from the highest bit available from step 1) 3) if data[index] is smaller than what you're looking for, leave the bit on 4) try wit…

You mean this one? int binary_search_pow2(const int a[], int len, int key) { int i = 0, step; for (step = len / 2; step > 0; step >>= 1) if (a[i | step] I thought that only worked for power-of-two sized arrays.

I implemented one for practise, without assuming powers of two:

    int binarySearch(const int needle, const int haystack[], const int size) {
    	if (size==0)
    		return -1;
    
    	short log2 = 0;	// rounded down
    	for (int sz=size; sz>>=1; log2++);
    
    	int index = 0;
    	for (int flag=10; flag>>=1) {
    		index |= flag;	// set
    		if (index>=size || needle

Re: Nearly all binary search and merge sort implementations are broken (2006)

#68

Post by sesqu »

MarkSweep wrote: post #28

I don't understand why I need Javscript enabled to merely read a blog post on blogspots.

To be fair, there's a classic version (but the link to it discards the article id, for some unfathomable reason).

This works: http://googleresearch.blogspot.com/2006/06/extra-extra-read-...

Re: Nearly all binary search and merge sort implementations are broken (2006)

#69

Post by gjm11 »

ColinWright wrote: post #65
gjm11 wrote: post #64

Earlier quoted context omitted.

I think one of Jon Bentley's "Programming pearls" books contains a version of binary search that works more or less that way and shows how to get there from a naive and more obviously correct implementation by successive small transformations. IIRC it ends up having a particularly tight inner loop. And it doesn't, I think, require a power-of-2-sized array. My copy of the book is at home and I'm at work so I can't che…

You're right - Programming Pearls, column 8 "Code Tuning." It's not quite like this, and it's in some variant of BASIC, but when you squint, it's there. Thanks.

You're welcome. In the second edition, which is what I happen to have, it's column 9 (because the old column 4 got split into two) and the code is in a pseudocode that's much more like C with the semicolons deleted than like any version of BASIC.

I wasn't quite right to say that the inner loop is very tight; rather, the code assumes a particular size of array and unrolls the loop completely. But, indeed, the size doesn't need to be a power of 2.

Here's the (pseudo)code, in case anyone cares. It's for an array of size 1000. I've changed a variable name from "l" to "m" because of the usual l1I| thing. I've removed a couple of helpful comments because anyone who cares enough to bother reading them will probably have more fun figuring everything out on their own. I've also elided some obvious repetitive code and formatted it slightly differently from Bentley. Any errors in the code were probably introduced by me.

  m = -1
  if (x[  511] 1000 || x[p]!=t) p = -1 /* i.e., not found */
Bentley says this is "not for the faint of heart". I agree, but I do think it's lovely. Though personally I'd be inclined to use a value of m offset by 1 from what Bentley does (initialize to 0, look up m+255, m+127, etc.) and save a line of code and a couple of cycles.

Re: Nearly all binary search and merge sort implementations are broken (2006)

#70

Post by caf »

pantaloons wrote: post #45
caf wrote: post #30

Earlier quoted context omitted.

INT_MAX == UINT_MAX is the only valid failing case, because elsewhere in the standard integer types are restricted to pure binary representations. This means that if UINT_MAX is greater than INT_MAX, it must be at least INT_MAX * 2 + 1.

That can't actually be taken for granted, relevant Usenet discussion begins here: http://groups.google.com/group/comp.std.c/browse_thread/thre...

I concur with Dan Pop's interpretation.
Post reply on HN