What is the fastest substring search algorithm?

Question

OK, so I don't sound like an idiot I'm going to state the problem/requirements more explicitly:

• Needle (pattern) and haystack (text to search) are both C-style null-terminated strings. No length information is provided; if needed, it must be computed.
• Function should return a pointer to the first match, or NULL if no match is found.
• Failure cases are not allowed. This means any algorithm with non-constant (or large constant) storage requirements will need to have a fallback case for allocation failure (and performance in the fallback care thereby contributes to worst-case performance).
• Implementation is to be in C, although a good description of the algorithm (or link to such) without code is fine too.

...as well as what I mean by "fastest":

• Deterministic O(n) where n = haystack length. (But it may be possible to use ideas from algorithms which are normally O(nm) (for example rolling hash) if they're combined with a more robust algorithm to give deterministic O(n) results).
• Never performs (measurably; a couple clocks for if (!needle[1]) etc. are okay) worse than the naive brute force algorithm, especially on very short needles which are likely the most common case. (Unconditional heavy preprocessing overhead is bad, as is trying to improve the linear coefficient for pathological needles at the expense of likely needles.)
• Given an arbitrary needle and haystack, comparable or better performance (no worse than 50% longer search time) versus any other widely-implemented algorithm.
• Aside from these conditions, I'm leaving the definition of "fastest" open-ended. A good answer should explain why you consider the approach you're suggesting "fastest".

My current implementation runs in roughly between 10% slower and 8 times faster (depending on the input) than glibc's implementation of Two-Way.

Update: My current optimal algorithm is as follows:

• For needles of length 1, use strchr.
• For needles of length 2-4, use machine words to compare 2-4 bytes at once as follows: Preload needle in a 16- or 32-bit integer with bitshifts and cycle old byte out/new bytes in from the haystack at each iteration. Every byte of the haystack is read exactly once and incurs a check against 0 (end of string) and one 16- or 32-bit comparison.
• For needles of length >4, use Two-Way algorithm with a bad shift table (like Boyer-Moore) which is applied only to the last byte of the window. To avoid the overhead of initializing a 1kb table, which would be a net loss for many moderate-length needles, I keep a bit array (32 bytes) marking which entries in the shift table are initialized. Bits that are unset correspond to byte values which never appear in the needle, for which a full-needle-length shift is possible.

The big questions left in my mind are:

• Is there a way to make better use of the bad shift table? Boyer-Moore makes best use of it by scanning backwards (right-to-left) but Two-Way requires a left-to-right scan.
• The only two viable candidate algorithms I've found for the general case (no out-of-memory or quadratic performance conditions) are Two-Way and String Matching on Ordered Alphabets. But are there easily-detectable cases where different algorithms would be optimal? Certainly many of the O(m) (where m is needle length) in space algorithms could be used for m<100 or so. It would also be possible to use algorithms which are worst-case quadratic if there's an easy test for needles which provably require only linear time.

Bonus points for:

• Can you improve performance by assuming the needle and haystack are both well-formed UTF-8? (With characters of varying byte lengths, well-formed-ness imposes some string alignment requirements between the needle and haystack and allows automatic 2-4 byte shifts when a mismatching head byte is encountered. But do these constraints buy you much/anything beyond what maximal suffix computations, good suffix shifts, etc. already give you with various algorithms?)

Note: I'm well aware of most of the algorithms out there, just not how well they perform in practice. Here's a good reference so people don't keep giving me references on algorithms as comments/answers: http://www-igm.univ-mlv.fr/~lecroq/string/index.html

Solution 1

Build up a test library of likely needles and haystacks. Profile the tests on several search algorithms, including brute force. Pick the one that performs best with your data.

Boyer-Moore uses a bad character table with a good suffix table.

Boyer-Moore-Horspool uses a bad character table.

Knuth-Morris-Pratt uses a partial match table.

Rabin-Karp uses running hashes.

They all trade overhead for reduced comparisons to a different degree, so the real world performance will depend on the average lengths of both the needle and haystack. The more initial overhead, the better with longer inputs. With very short needles, brute force may win.

Edit:

A different algorithm might be best for finding base pairs, english phrases, or single words. If there were one best algorithm for all inputs, it would have been publicized.

Think about the following little table. Each question mark might have a different best search algorithm.

                 short needle     long needle
short haystack         ?               ?
long haystack          ?               ?

This should really be a graph, with a range of shorter to longer inputs on each axis. If you plotted each algorithm on such a graph, each would have a different signature. Some algorithms suffer with a lot of repetition in the pattern, which might affect uses like searching for genes. Some other factors that affect overall performance are searching for the same pattern more than once and searching for different patterns at the same time.

If I needed a sample set, I think I would scrape a site like google or wikipedia, then strip the html from all the result pages. For a search site, type in a word then use one of the suggested search phrases. Choose a few different languages, if applicable. Using web pages, all the texts would be short to medium, so merge enough pages to get longer texts. You can also find public domain books, legal records, and other large bodies of text. Or just generate random content by picking words from a dictionary. But the point of profiling is to test against the type of content you will be searching, so use real world samples if possible.

I left short and long vague. For the needle, I think of short as under 8 characters, medium as under 64 characters, and long as under 1k. For the haystack, I think of short as under 2^10, medium as under a 2^20, and long as up to a 2^30 characters.

Solution 2

Published in 2011, I believe it may very well be the "Simple Real-Time Constant-Space String Matching" algorithm by Dany Breslauer, Roberto Grossi, and Filippo Mignosi.

Update:

In 2014 the authors published this improvement: Towards optimal packed string matching.

Solution 3

I was surprised to see our tech report cited in this discussion; I am one of the authors of the algorithm that was named Sustik-Moore above. (We did not use that term in our paper.)

I wanted here to emphasize that for me the most interesting feature of the algorithm is that it is quite simple to prove that each letter is examined at most once. For earlier Boyer-Moore versions they proved that each letter is examined at most 3 and later 2 times at most, and those proofs were more involved (see cites in paper). Therefore I also see a didactical value in presenting/studying this variant.

In the paper we also describe further variations that are geared toward efficiency while relaxing the theoretical guarantees. It is a short paper and the material should be understandable to an average high school graduate in my opinion.

Our main goal was to bring this version to the attention of others who can further improve on it. String searching has so many variations and we alone cannot possibly think of all where this idea could bring benefits. (Fixed text and changing pattern, fixed pattern different text, preprocessing possible/not possible, parallel execution, finding matching subsets in large texts, allow errors, near matches etc., etc.)

Solution 4

The http://www-igm.univ-mlv.fr/~lecroq/string/index.html link you point to is an excellent source and summary of some of the best known and researched string matching algorithms.

Solutions to most search problems involve trade offs with respect to pre-processing overhead, time and space requirements. No single algorithm will be optimal or practical in all cases.

If you objective is to design a specific algorithm for string searching, then ignore the rest of what I have to say, If you want to develop a generalized string searching service routine then try the following:

Spend some time reviewing the specific strengths and weaknesses of the algorithms you have already referenced. Conduct the review with the objective of finding a set of algorithms that cover the range and scope of string searches you are interested in. Then, build a front end search selector based on a classifier function to target the best algorithm for the given inputs. This way you may employ the most efficient algorithm to do the job. This is particularly effective when an algorithm is very good for certain searches but degrades poorly. For example, brute force is probably the best for needles of length 1 but quickly degrades as needle length increases, whereupon the sustik-moore algoritim may become more efficient (over small alphabets), then for longer needles and larger alphabets, the KMP or Boyer-Moore algorithms may be better. These are just examples to illustrate a possible strategy.

The multiple algorithm approach not a new idea. I believe it has been employed by a few commercial Sort/Search packages (e.g. SYNCSORT commonly used on mainframes implements several sort algorithms and uses heuristics to choose the "best" one for the given inputs)

Each search algorithm comes in several variations that can make significant differences to its performance, as, for example, this paper illustrates.

Benchmark your service to categorize the areas where additional search strategies are needed or to more effectively tune your selector function. This approach is not quick or easy but if done well can produce very good results.

Solution 5

The fastest substring search algorithm is going to depend on the context:

1. the alphabet size (e.g. DNA vs English)
2. the needle length

The 2010 paper "The Exact String Matching Problem: a Comprehensive Experimental Evaluation" gives tables with runtimes for 51 algorithms (with different alphabet sizes and needle lengths), so you can pick the best algorithm for your context.

All of those algorithms have C implementations, as well as a test suite, here:

http://www.dmi.unict.it/~faro/smart/algorithms.php

View more solutions

Comments

[Greg Hewgill]

There are quite a number of string search algorithms listed on Algorithms on Strings. You may want to describe which algorithms you've considered from this list.

[Carlos]

That link at the end is gold!

[user541686]

I can't believe you still haven't accepted an answer.

[R.. GitHub STOP HELPING ICE]

@Mehrdad: I was about to say there aren't any answers which really address the question as asked, but yours seems to. At the time you answered I'd moved on and left further improvement of strstr as something for later, so I haven't actually gotten around to properly reading the paper you linked, but it does sound very promising. Thanks and sorry for not getting back to you.

[R.. GitHub STOP HELPING ICE]

Do you know a way to combine Boyer-Moore's bad shift table with Two-Way? Glibc does a variant of this for long needles (>32 byte) but only checks the last byte. The problem is that Two-Way needs to search the right portion of the needle left-to-right, whereas Boyer-Moore's bad shift is most efficient when searching from right-to-left. I tried using it with left-to-right in Two-Way (advance by shift table or normal Two-Way right half mismatch, whichever is longer) but I got a 5-10% slowdown versus normal Two-Way in most cases and couldn't find any cases where it improved performance.

[R.. GitHub STOP HELPING ICE]

Do you have good suggestions for a test library? The previous question I asked on SO was related to that and I never got any real answers. (except my own...) It should be extensive. Even if my idea of an application for strstr is searching English text, somebody else's might be searching for genes in base pair sequences...

[R.. GitHub STOP HELPING ICE]

It's a bit more complicated than short/long. For the needle, the big questions relevant to the performance of most algorithms are: Length? Is there any periodicity? Does the needle contain all unique characters (no repeats)? Or all the same character? Are there a large number of characters in the haystack that never appear in the needle? Is there a chance of having to deal with needles provided by an attacker who wants to exploit worst-case performance to cripple your system? Etc..

[R.. GitHub STOP HELPING ICE]

Thanks for the response, especially the link to Sustik-Moore which I hadn't seen before. The multiple algorithms approach is surely in widespread use. Glibc basically does strchr, Two-Way without bad character shift table, or Two-Way with bad character shift table, depending on whether needle_len is 1, <32, or >32. My current approach is the same except that I always use the shift table; I replaced the 1kb memset necessary to do so with a 32 byte memset on a bitset used to mark which elements of the table have been initialized, and I get the benefit (but not overhead) even for tiny needles.

[R.. GitHub STOP HELPING ICE]

After thinking about it, I'm really curious what the intended application for Sustik-Moore is. With small alphabets, you'll never get to make any significant shifts (all characters of the alphabet almost surely appear near the end of the needle) and finite automata approaches are very efficient (small state transition table). So I can't envision any scenario where Sustik-Moore could be optimal...

[Jason S]

great response -- if I could star this particular answer I would.

[NealB]

@R.. The theory behind the sustik-moore algorithm is that it should give you larger average shift amounts when the needle is relatively large and the alphabet is relatively small (eg. searching for DNA sequences). Larger in this case just means larger than the basic Boyer-Moore algorithm would produce given the same inputs. How much more efficient this is relative to a finite automata approach or to some other Boyer-Moore variation (of which there are many) is hard to say. That is why I emphasised spending some time to research the specific strengths/weaknesses of your candidate algorithms.

[R.. GitHub STOP HELPING ICE]

Hm, I guess I was stuck thinking of shifts just in the sense of bad character shifts from Boyer-Moore. With an improvement on BM good suffix shifts though, Sustik-Moore could possibly outperform DFA approaches to DNA searching. Neat stuff.

[R.. GitHub STOP HELPING ICE]

If you have some good needles to test along with the haystack candidates from the SACA benchmark, post them as an answer to my other question and, short of getting a better answer, I'll mark it accepted.

[R.. GitHub STOP HELPING ICE]

About your memmem and Boyer-Moore, it's very likely that Boyer-Moore (or rather one of the enhancements to Boyer-Moore) will perform best on random data. Random data has an extremely low probability of periodicity and long partial matches which lead to quadratic worst-case. I'm looking for a way to combine Boyer-Moore and Two-Way or to efficiently detect when Boyer-Moore is "safe to use" but so far I haven't had any success. BTW I wouldn't use glibc's memmem as a comparison. My implementation of what's basically the same algorithm as glibc's is several times faster.

[user172818]

As I said, it is not my implementation. Credit to Christian Charras and Thierry Lecroq. I can imagine why random input is bad for benchmarking and I am sure glibc chooses algorithms for reasons. I also guess memmem() is not implemented efficiently. I will try. Thanks.

[R.. GitHub STOP HELPING ICE]

And if you read my question you'd see I had a pretty easy time outperforming it. I like your sarcasm enough I'll skip the -1 though.

[johne]

"For needles of length 1, use strchr."- You asked for the fastest substring search algorithm(s). Finding a substring of length 1 is a just a special case, one that can also be optimized. If you swap out your current special case code for substrings of length 1 (strchr) with something like the above, things will (possibly, depending on how strchr is implemented) go faster. The above algorithm is nearly 3x faster than a typical naive strchr implementation.

[R.. GitHub STOP HELPING ICE]

A typical strchr implementation is not naive, but quite a bit more efficient than what you gave. See the end of this for the most widely used algorithm: graphics.stanford.edu/~seander/bithacks.html#ZeroInWord

[johne]

That isn't necessarily faster- the link provided only determines if an int contains a 0 byte, not its location (as the code in the answer does). As to whether or not one is faster than the other depends on on the microarchitecture. As to typical strchr implementations.. well, the above code clearly beats a typical strchr implementation.

[R.. GitHub STOP HELPING ICE]

By the way your version with possibly misaligned reads has an insurmountable bug: it can read past the sought byte or null terminator, which could access an unmapped page or page without read permission. You simply cannot use large reads in string functions unless they're aligned.

[R.. GitHub STOP HELPING ICE]

As for your ctz optimization, it only makes a difference for the O(1) tail operation. It could improve performance with tiny strings (e.g. strchr("abc", 'a'); but certainly not with strings of any major size.

[Seth Robertson]

OP said string was properly null terminated, so your discussion about char bytes[1] = {0x55}; is irrelevant. Very relevant is your comment about this being true for any word read algorithm which does not know the length beforehand.

[R.. GitHub STOP HELPING ICE]

The problem does not apply to the version I cited because you only use it on aligned pointers - at least that's what correct implementations do.

[johne]

@seth-robertson, you're right. And if you were to use the code in this answer in a standards compliant strchr, you would be required to check for '\0' as well as the character to check.

[johne]

@R, it has nothing to do with "aligned pointers". Hypothetically, if you had an architecture which supported VM protection with byte level granularity, and each malloc allocation was "sufficiently padded" on either side and the VM system enforced byte granular protection for that allocation.... whether or not the pointer is aligned (assuming trivial 32-bit int natural alignment) is moot- it is still possible for that aligned read to read past the size of the allocation. ANY read past the size of the allocation is undefined behavior.

[R.. GitHub STOP HELPING ICE]

@johne: +1 to comment. Conceptually you're right, but the reality is that byte-granularity protections are so expensive both to store and to enforce that they don't and never will exist. If you know the underlying storage is page-granularity mappings obtained from the equivalent of mmap, then alignment is sufficient.

[asdf]

Do you mind explaining your findFirstZeroByte32() macro? I'm especially having problems understanding the 0x7F7F7F7Fu part.

[R.. GitHub STOP HELPING ICE]

Wow thanks. I'm reading the paper. If it turns out to be better than what I have, I'll definitely accept your answer.

[user541686]

@R..: Sure! :) Speaking of which, if you manage to implement the algorithm, please consider posting it on StackOverflow so everyone can benefit from it! I haven't found any implementations of it anywhere and I'm not good at implementing algorithms I find in research papers haha.

[R.. GitHub STOP HELPING ICE]

It's a variant of the "two-way" algorithm I'm already using, so adapting my code to use this might actually be easy. I'll have to read the paper in more detail to be sure, though, and I need to evaluate whether the changes made are compatible with my use of a "bad character table" which greatly speeds up the common case.

[R.. GitHub STOP HELPING ICE]

Thanks for the link. The tests look interesting for typical-case timing but not for catching worst-case times.

[JDiMatteo]

Do you happen to know of a C or C++ implementation available? I'm thinking of using this for some dna motif search (exact motif matches). If not, maybe I'll try developing an implementation myself and submitting to boost algorithm

[JDiMatteo]

With no known available implementation, the Sustik-Moore/2BLOCK algorithm seems unlikely to be used in practice and continue to be omitted from results in summary papers like "The Exact String Matching Problem: a Comprehensive Experimental Evaluation"

[lifebalance]

And you still haven't accepted @Mehrdad's answer! :-)

[Peter Cordes]

I don't see any SSE3 insns in Apple's i386 strlen, only SSE2. pcmpeqb, pmovmskb, pxor, and movdqa are all SSE2. Probably they just say SSE3 in comments because SSE3 was Apple's baseline for x86 CPUs. (The original apple x86s were Core Duo, and SSSE3 was new in Core 2 Duo (Merom/Conroe). Kinda too bad Apple had to support a CPU that couldn't run 64bit code, since they were one CPU generation too early.)

[Dawood ibn Kareem]

Well, to be fair, it IS a link-only answer, which is not supposed to be allowed here.

[user541686]

@DavidWallace: What? It has the paper titles and the authors. Even if the link goes dead you can find the papers. What are you expecting me to do, write pseudocode for the algorithm? What makes you think I understand the algorithm?

[rurban]

Nope, the 2010 paper misses the latest and best, which is epsm, "Exact Packed String Matching". epsm is best in all cases. faro's new website is currently broken, in the internet archive you can see it.

[rurban]

This library and testcode exists with smart, and none of your listed old algos perform good. The Leroy paper is also too old. There are about 80 improvements to BM, KMP, BMH, KP. Currently best (as of 2020) is EPSM in all cases.

[user541686]

@rurban: The 2010 paper misses the paper from 2013?

[rurban]

@user541686: exactly. the latest and best was not yet known. op referred to that old paper, which misses the latest and best.