Repository files navigation

This library provides heavily optimized routines for string search primitives.

Dual-licensed under MIT or theUNLICENSE.

https://docs.rs/memchr

• The top-level module provides routines for searching for 1, 2 or 3 bytesin the forward or reverse direction. When searching for more than one byte,positions are considered a match if the byte at that position matches anyof the bytes.
• Thememmem sub-module provides forward and reverse substring searchroutines.

In all such cases, routines operate on&[u8] without regard to encoding. Thisis exactly what you want when searching either UTF-8 or arbitrary bytes.

memchr links to the standard library by default, but you can disable thestd feature if you want to use it in a#![no_std] crate:

[dependencies]memchr = {version ="2",default-features =false }

Onx86_64 platforms, when thestd feature is disabled, the SSE2 acceleratedimplementations will be used. Whenstd is enabled, AVX2 acceleratedimplementations will be used if the CPU is determined to support it at runtime.

SIMD accelerated routines are also available on thewasm32 andaarch64targets. Thestd feature is not required to use them.

When a SIMD version is not available, then this crate falls back toSWAR techniques.

This crate's minimum supportedrustc version is1.61.0.

The current policy is that the minimum Rust version required to use this cratecan be increased in minor version updates. For example, ifcrate 1.0 requiresRust 1.20.0, thencrate 1.0.z for all values ofz will also require Rust1.20.0 or newer. However,crate 1.y fory > 0 may require a newer minimumversion of Rust.

In general, this crate will be conservative with respect to the minimumsupported version of Rust.

Given the complexity of the code in this crate, along with the pervasive useofunsafe, this crate has an extensive testing strategy. It combines multipleapproaches:

• Hand-written tests.
• Exhaustive-style testing meant to exercise all possible branching and offsetcalculations.
• Property based testing throughquickcheck.
• Fuzz testing throughcargo fuzz.
• A huge suite of benchmarks that are also run as tests. Benchmarks alwaysconfirm that the expected result occurs.

Improvements to the testing infrastructure are very welcome.

At time of writing, this crate's implementation of substring search actuallyhas a few different algorithms to choose from depending on the situation.

• For very small haystacks,Rabin-Karpis used to reduce latency. Rabin-Karp has very small overhead and can oftencomplete before other searchers have even been constructed.
• For small needles, a variant of the"Generic SIMD"algorithm is used. Instead of using the first and last bytes, a heuristic isused to select bytes based on a background distribution of byte frequencies.
• In all other cases,Two-Wayis used. If possible, a prefilter based on the "Generic SIMD" algorithmlinked above is used to find candidates quickly. A dynamic heuristic is usedto detect if the prefilter is ineffective, and if so, disables it.

We'll start by establishing what the difference in performance actuallyis. There are two relevant benchmark classes to consider:prebuilt andoneshot. Theprebuilt benchmarks are designed to measure---to the extentpossible---search time only. That is, the benchmark first starts by building asearcher and then only tracking the time forusing the searcher:

$ rebar rank benchmarks/record/x86_64/2023-08-26.csv --intersection -e memchr/memmem/prebuilt -e std/memmem/prebuiltEngine                       Version                   Geometric mean of speed ratios  Benchmark count------                       -------                   ------------------------------  ---------------rust/memchr/memmem/prebuilt  2.5.0                     1.03                            53rust/std/memmem/prebuilt     1.73.0-nightly 180dffba1  6.50                            53

Conversely, theoneshot benchmark class measures the time it takes to bothbuild the searcherand use it:

$ rebar rank benchmarks/record/x86_64/2023-08-26.csv --intersection -e memchr/memmem/oneshot -e std/memmem/oneshotEngine                      Version                   Geometric mean of speed ratios  Benchmark count------                      -------                   ------------------------------  ---------------rust/memchr/memmem/oneshot  2.5.0                     1.04                            53rust/std/memmem/oneshot     1.73.0-nightly 180dffba1  5.26                            53

NOTE: Replacerebar rank withrebar cmp in the above commands toexplore the specific benchmarks and their differences.

So in both cases, this crate is quite a bit faster over a broad sampling ofbenchmarks regardless of whether you measure only search time or search timeplus construction time. The difference is a little smaller when you includeconstruction time in your measurements.

These two different types of benchmark classes make for a nice segue intoone reason why the standard library's substring search can be slower: APIdesign. In the standard library, the only APIs available to you requireone to re-construct the searcher for every search. While you can benefitfrom building a searcher once and iterating over all matches in a singlestring, you cannot reuse that searcher to search other strings. This mightcome up when, for example, searching a file one line at a time. You'll needto re-build the searcher for every line searched, and this canreallymatter.

NOTE: Theprebuilt benchmark for the standard library can't actuallyavoid measuring searcher construction at some level, because there is no APIfor it. Instead, the benchmark consists of building the searcher once and thenfinding all matches in a single string via an iterator. This tends toapproximate a benchmark where searcher construction isn't measured, but itisn't perfect. While this means the comparison is not strictlyapples-to-apples, it does reflect what is maximally possible with the standardlibrary, and thus reflects the best that one could do in a real world scenario.

While there is more to the story than just API design here, it's important topoint out that even if the standard library's substring search were a preciseclone of this crate internally, it would still be at a disadvantage in someworkloads because of its API. (The same also applies to C's standard librarymemmem function. There is no way to amortize construction of the searcher.You need to pay for it on every call.)

The other reason for the difference in performance is thatthe standard library has trouble using SIMD. In particular, substring searchis implemented in thecore library, where platform specific code generallycan't exist. That's an issue because in order to utilize SIMD beyond SSE2while maintaining portable binaries, one needs to usedynamic CPU featuredetection, and that in turn requires platform specific code.While there isan RFC for enabling target feature detection incore, it doesn't yet exist.

The bottom line here is thatcore's substring search implementation islimited to making use of SSE2, but not AVX.

Still though, this crate does accelerate substring search even when only SSE2is available. The standard library could therefore adopt the techniques in thiscrate just for SSE2. The reason why that hasn't happened yet isn't totallyclear to me. It likely needs a champion to push it through. The standardlibrary tends to be more conservative in these things. With that said, thestandard library does use someSSE2 acceleration onx86-64 addedinthis PR. However, at the time of writing, it is only usedfor short needles and doesn't use the frequency based heuristics found in thiscrate.

NOTE: Another thing worth mentioning is that the standard library'ssubstring search routine requires that both the needle and haystack have type&str. Unless you can assume that your data is valid UTF-8, building a&strwill come with the overhead of UTF-8 validation. This may in turn result inoverall slower searching depending on your workload. In contrast, thememchrcrate permits both the needle and the haystack to have type&[u8], where&[u8] can be created from a&str with zero cost. Therefore, the substringsearch in this crate is strictly more flexible than what the standard libraryprovides.