On bananas and string matching algorithms

http://www.wabbo.org/blog/2014/22aug_on_bananas.html

by cjbprime • 12 years ago

260 62 12 years ago

Really interesting post and good debugging work. A couple of take-aways:

1. This is one reason it's a good idea to use signed ints for lengths even though they can never be negative. Signed 64-bit ints have plenty of range for any array you're actually going to encounter. It may also be evidence that it's a good idea for mixed signed/unsigned arithmetic to produce signed results rather than unsigned: signed tends to be value-correct for "small" values (less than 2^63), including negative results; unsigned sacrifices value-correctness on all negative values to be correct for very large values, which is a less common case – here it will never happen since there just aren't strings that large.

2. If you're going to use a fancy algorithm like two-way search, you really ought to have a lot of test cases, especially ones that exercise corner cases of the algorithm. 100% coverage of all non-error code paths would be ideal.

QuantumChaos• 12 years ago

Regarding 2., I'm going to assume they have at least some unit tests.

It's not clear that even 100% coverage would have picked up this bug, since it doesn't automatically appear as a result of taking a particular code path.

I think that comparing to a naive algorithm on a large number of strings, or using a fuzzing tool, might be helpful, but this might also slow down the test suite excessively.

I find unit tests are a bit like good form at the gym. Whenever someone gets injured, they think back to the last exercise they did and find some imperfection in their form. They then attribute their injury to not using perfect form. Similarly, whenever a bug appears, there is a tendency to find a unit test that would have caught the bug, and therefore attribute it to insufficient testing.

The real value of testing (and good form) can only be demonstrated by having a criteria for good testing and seeing if following this reduces the number of bugs.

Ono-Sendai• 12 years ago

They did have some tests, obviously not enough though.

akkartik2• 12 years ago

No unit tests for the string library: https://github.com/rust-lang/rust/blob/6843d8ccd5/src/libcor... (That's the hash for tip at the time of this comment.)

haberman2• 12 years ago

I'm not sure I agree with #1. While it's true that using signed integers for lengths would have solved this problem, a negative length doesn't generally make sense or have any defined meaning. So if you have any logic that is doing case analysis on lengths, you basically have no reasonable action in the case of a negative length: all you can do is complain that the length got corrupted at some point.

For example, imagine that instead of testing whether the strings differed by more than 20, you were just testing whether the needle was >= 20 in length:

    impl Searcher {
        fn new(haystack: &[u8], needle: &[u8]) -> Searcher {
            match needle.len() {
                0..20 => Naive(NaiveSearcher::New)
                20..uint::MAX => TwoWay(TwoWaySearcher::New(needle))
                _ => fail!("Negative length, shouldn't happen!")
            }
        }
    }

Part of the feature of an unsigned type IMO is that it cannot have an out-of-domain value by definition.

CJefferson• 12 years ago

The problem is that while unsigned types cannot have an out-of-domain value, they wrap.

Also, often negative lengths make sense as meaning "backwards". In C++ I often hit in algorithms code that looks like some variant of:

    a.size()-1 >= capacity

But when a.size() == 0, a.size() - 1 is MAXINT. Of course I could re-write this as a.size() >= capacity + 1, but that requires remembering / noticing.

Personally I find this so annoying that when I recently had to write a set of my own C++ containers (as I needed 1-indexed rather than 0-indexed containers), I decided to make the return value of size() signed.

wyager3• 12 years ago

This is one reason it's a good idea to use signed ints for lengths

I disagree. Types are a form of documentation, and a constraint on proper program behavior. Length types can't be negative; that doesn't make any sense. If you end up with a negative length, you are doing something wrong. One should just write correct code and use the proper length type. In C that's `size_t`, and in Rust it's `uint`.

yongjik• 12 years ago

The problem is that C (and many other languages) only have the notion of "signed" vs. "unsigned" values, and nothing else. For example, if 'len' is a variable that holds the length of something, then its range is defined by (len >= 0). So far so good. But what is the range of the expression (len - 1)?

In a perfect world, its range is {-1, 0, 1, ...} (up to some maximum value), but C(++) doesn't have such notion. If we used uint, -1 will silently change to MAX_UINT. Oops.

Joeri• 12 years ago

I agree with you that negative lengths are not a good solution, but...

"One should just write correct code"

No one writes correct code, so our languages should be designed to avoid the possibility for mistakes to be made or go unnoticed. I'm wondering if the compiler in this case could have done more to inform the programmer of a possible bug. A 'this expression is likely to underflow' warning would have made a big difference I suspect.

SolarNet• 12 years ago

I think the correct solution is for the type system to be able to say "Hey, this unsigned int is being subtracted from and was not checked to ensure it is greater than the value being subtracted." And the typical solution would be to either a) invert the subtraction to an addition, b) do a check, or c) annotate the type.

eru2• 12 years ago

Or add a proof.

nly• 12 years ago

On #1: Signed under and overflow in C and C++ is undefined behaviour and can do weird things. In combination with compiler optimizations especially, the compiler can simply assume it never happens. Using unsigned types means when someone passes you a negative int at least the result is well-defined and can be debugged when your program explodes.

Use unsigned types for unsigned values, and ensure all (new at least) code compiles cleanly with -Wconversion and -Wsign-conversion enabled, which should really be the default warning level these days.

zackmorris• 12 years ago

I've seen some very strange things in my career. I find posts like this delightful, because I can point to them and say "see, here is proof that even code written with the best of intentions can still have bugs."

Programmers tend to fall into (at least) two camps: the skeptics and the pragmatists.

Sometimes when I report a finding, programmers accuse me in one way or another of messing something up because “that can’t possibly be failing.” Those are the skeptics, using incredulousness almost like a shield to protect their worldview. They tend to have an up-close/what’s right in front of them approach to programming, are prolific and usually take a positive stance on programming.

At other times, reporting a finding is met with resignation, almost like “please work around it because we just don’t need this right now”. Those are the pragmatists, taking the long view/forest for the trees approach, knowing that programming is more than the some of its parts but also that it’s a miracle it even works at all. They are the daydreamers and sometimes are perceived as negative or defeatist.

I was a pragmatist for as long as I could remember, but had a change of heart working with others in professional settings. I saw that certain things like databases or unix filesystems could largely be relied upon to work in a deterministic manner, like they created a scaffolding that helps one stay grounded in reality. They help one command a very mathematical/deliberate demeanor, and overcome setbacks by treating bugs as something to be expected but still tractable.

But here is one of those bugs, where the floor seemed to fall out from under our feet. One day I mentioned that “SSL isn’t working” and about half the office flipped out on me and the other half rolled their eyes and had me track it down:

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=694667

The gist of it is that OpenSSL was failing when the MTU was 1496 instead of 1500, because of path MTU discovery failing and SSL thinking it was a MITM attack and closing (at least, that is how I remember it, I am probably futzing some details).

That was odd behavior to me, because I see SSL as something that should be a layer above TCP and not bother with the implementation details of underlying layers. It should operate under the assumption that there is always a man in the middle. If you can open a stream to a server, you should be able to send secure data over it.

Anyway, we fixed the router setting and got back to work. All told I probably lost a day or two of productivity, because the office network had been running just fine for years and so I discounted it for a long time until I ruled out every other possibility. I’ve hit crazy bugs like this at least once a year, and regret not documenting them I suppose. Usually by the time they are fixed, people have forgotten the initial shock, but they still remember that you are the one weirdo who always seems to break everything.

cjbprime5• 12 years ago

Yeah, I like the phrase "suspecting a compiler bug is the principle of last resort". (Maybe there should be an "unless you're using Rust" thrown in there.)

It's not that compilers can't have bugs. It's that you're more fallible than the compiler, and should use that likelihood when deciding where to investigate to fix the bug you're seeing.

Retric• 12 years ago

I remember a long day tracking down a bug in some low level networking code that turned out to be bad RAM on a test machine. I remember thinking "This is probably what going crazy feels like." But, I still trusted the compiler more than the HW.

kedean• 12 years ago

To be fair, this was a bug in the standard library, not the compiler. You should also trust your stdlib too, though, unless its a demonstrable problem like the article.

todd82• 12 years ago

Yes, there are certain tools that I trust almost completely, like TeX [1], and it helps me focus on finding my own bugs because I'm not tempted to spend some time wondering if is the tool (build tools, library, compiler, etc.) with the bug and not my own code.

[1] http://texdoc.net/texmf-dist/doc/generic/knuth/errata/errorl...

gus_massa• 12 years ago

Yes, TeX is almost bug free.

But once you start to use LaTeX you are not long so safe. If you use two LaTeX packages, you have to pray that they are compatible, and they are loaded in the right order. If you have to use babel (because you don't speak in english) you are probably out of luck.

rdtsc• 12 years ago

One day I mentioned that “SSL isn’t working”

The distinction is who they think you are. I a junior programmers comes up with "I think gcc is broken". Well they could be right, but my first instinct is to say "no, probably not".

Then Linus says:

---

For chrissake, that compiler shouldn't have been allowed to graduate from kindergarten. We're talking "sloth that was dropped on the head as a baby" level retardation levels here

---

I'll probably believe him.

These are two extremes. The pragmatists vs sceptics is just as much pragmatism and scepticism about the person reporting the problem.

daxelrod• 12 years ago

For context, that is an actual Torvalds quote, talking about GCC 4.9.0: https://lkml.org/lkml/2014/7/24/584

sitkack3• 12 years ago

Why is this code so damn fancy? Shouldn't the fanciness be offset by proofs or extended testing? Open loop!

TTPrograms• 12 years ago

My guess is that naive searcher is O(nm) and two way is O(n) for haystack length n and needle length m.

pcwalton4• 12 years ago

Two-way searching is the norm for substring matching. Even your libc is probably using it for strstr(). For example, here's musl's implementation: http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c

userbinator• 12 years ago

Agreed, this seems like a case of excessive complexity. I hadn't even heard of "two-way" before, but I don't think an algorithm the paper claims to be "remarkably simple" should require twenty-five pages to describe.

"two-way" isn't all that fast either, so I don't see any good reason for its use; in the benchmarks I could find, the simpler BMH easily beats it (and optimised BMH variants go even faster): http://volnitsky.com/project/str_search/benchmark-4.5.1.png http://blog.phusion.nl/2010/12/06/efficient-substring-search...

sitkack3• 12 years ago

It would be interesting to put a trace on `strstr` for a couple days and see what the distribution of arguments look like.

ToDo: Profile libc for various workloads, record arguments and code coverage

alayne2• 12 years ago

I try to never look at GPL/LGPL code if I'm going to implement something at work or under another license.

Sorry for suggesting a good practice to avoid legal liability.

JadeNB4• 12 years ago

Sorry for suggesting a good practice to avoid legal liability.

Why is this good practice? Has anyone ever been exposed to a legal liability that could be creditably attributed to their merely looking at (as opposed to using) such code? (Although my suspicion is that the answer is 'no', this is an honest question.)

steveklabnik• 12 years ago

Yes, it can come up. See the recent Google / Oracle lawsuit, where it was specifically presented that Dalvik was a 'clean room' implementation.

cjbprime5• 12 years ago

I think the idea is that it's going to be difficult, having looked at the code, to implement a version that is not similar enough to the original to trigger a copyright "derivative work".

For example, I believe it used to be the case (just a few years ago) that Microsoft employees were contractually prohibited from looking at GPL'd code.

But if alayne is planning on bringing that up every time someone shares a post that might contain GPL code, alayne is quickly going to become the most tedious person at the party, and that's why the downvotes are happening.

If your situation prevents you from studying and learning from GPL'd code, then just don't study it, and don't brag about not studying it.

srean2• 12 years ago

There are many comments discussing whether length should be unsigned or signed. There are arguments for and against it. This a prototypical carpet bump, you squash it in one place it raises its head somewhere else.

I see it not as a question whether lengths should be signed or unsigned but whether subtraction, assignment etc should be polymorphic w.r.t signed and unsigned. I think the issue here is the polymorphic variants of these binary operators are inherently risky.

Casting gets a little tedious, but languages that do not have operator overloading should disallow subtraction from unsigned and subtraction that return unsigned. You either cast it up, or if possible reorder the expression/comparison so that the problem goes away. Even assignment can be a problem. Ocaml can get irritating because it takes this view but I think it is safer this way. It is very hard to be always vigilant about the unsigned signed issue, but hopefully a compiler error will mitigate risks, not completely, but it is better than nothing.

That leaves languages that allow operator overloading, in those cases if you are overloading an operator you better know what you are doing, and watch out for cases where the operator is not closed.

judk2• 12 years ago

What is the signed value of 0-UINT_MAX?

There is no way to handle this issue on machine types, unless part of the range is reserved for overflow and checked. But performance nuts intentionally discard safety for performance.

srean2• 12 years ago

As I suggested there should not be a '-' that returns unsigned. If you want to cast it back to unsigned you would have to do it explicitly, and ideally a checked cast, though I am not averse to a more verbose unchecked cast.

I am not averse to binary operators with wrap around / modulo arithmetic, but they should be look different from the usual '+', '-' etc. This only applies to languages that do not allow overloading operators.

On bananas and string matching algorithms

Related Stories