Data.ByteString.Lazy.Search

In general, the Boyer-Moore algorithm is the most efficient method to search for a pattern inside a string. The advantage over other algorithms (e.g. Naïve, Knuth-Morris-Pratt, Horspool, Sunday) can be made arbitrarily large for specially selected patterns and targets, but usually, it's a factor of 2–3 versus Knuth-Morris-Pratt and of 6–10 versus the naïve algorithm. The Horspool and Sunday algorithms, which are simplified variants of the Boyer-Moore algorithm, typically have performance between Boyer-Moore and Knuth-Morris-Pratt, mostly closer to Boyer-Moore. The advantage of the Boyer-moore variants over other algorithms generally becomes larger for longer patterns. For very short patterns (or patterns with a very short period), other algorithms, e.g. Data.ByteString.Lazy.Search.DFA can be faster (my tests suggest that "very short" means two, maybe three bytes).

In general, searching in a strict ByteString is slightly faster than searching in a lazy ByteString, but for long targets the smaller memory footprint of lazy ByteStrings can make searching those (sometimes much) faster. On the other hand, there are cases where searching in a strict target is much faster, even for long targets.

On 32-bit systems, Int-arithmetic is much faster than Int64-arithmetic, so when there are many matches, that can make a significant difference.

Also, the modification to ameliorate the case of periodic patterns is defeated by chunk-boundaries, so long patterns with a short period and many matches exhibit poor behaviour (consider using indices from Data.ByteString.Lazy.Search.DFA or Data.ByteString.Lazy.Search.KMP in those cases, the former for medium-length patterns, the latter for long patterns; none of the functions except indices suffer from this problem, though).

When working with a lazy target string, the relation between the pattern length and the chunk size can play a big rôle. Crossing chunk boundaries is relatively expensive, so when that becomes a frequent occurrence, as may happen when the pattern length is close to or larger than the chunk size, performance is likely to degrade. If it is needed, steps can be taken to ameliorate that effect, but unless entirely separate functions are introduced, that would hurt the performance for the more common case of patterns much shorter than the default chunk size.

Preprocessing the pattern is O(patternLength + σ) in time and space (σ is the alphabet size, 256 here) for all functions. The time complexity of the searching phase for indices is O(targetLength / patternLength) in the best case. For non-periodic patterns, the worst case complexity is O(targetLength), but for periodic patterns, the worst case complexity is O(targetLength * patternLength) for the original Boyer-Moore algorithm.

The searching functions in this module contain a modification which drastically improves the performance for periodic patterns, although less for lazy targets than for strict ones. If I'm not mistaken, the worst case complexity for periodic patterns is O(targetLength * (1 + patternLength / chunkSize)).

The other functions don't have to deal with possible overlapping patterns, hence the worst case complexity for the processing phase is O(targetLength) (respectively O(firstIndex + patternLength) for the breaking functions if the pattern occurs).

All functions can usefully be partially applied. Given only a pattern, the pattern is preprocessed only once, allowing efficient re-use.

The current code uses Int to keep track of the locations in the target string. If the length of the pattern plus the length of any strict chunk of the target string is greater or equal to maxBound :: Int then this will overflow causing an error. We try to detect this and call error before a segfault occurs.