3 ms·
Why is this code so damn fancy? Shouldn't the fanciness be offset by proofs or extended testing? Open loop!
by sitkack 12y ago
Why is this code so damn fancy? Shouldn't the fanciness be offset by proofs or extended testing? Open loop!
- TTPrograms 12y agoMy guess is that naive searcher is O(nm) and two way is O(n) for haystack length n and needle length m.
- pcwalton 12y agoTwo-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 http://git.musl-libc.org/cgit/musl/tree/src/string/strstr.c
- userbinator 12y agoAgreed, 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://volnitsky.com/project/str_search/benchmark-4.5.1.png http://blog.phusion.nl/2010/12/06/efficient-substring-searching/ http://blog.phusion.nl/2010/12/06/efficient-substring-search...
- sitkack 12y agoIt 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