memchr picks Rabin-Karp, generic SIMD or Two-Way based on the haystack

Two APIs, one byte-oriented interface

The top level module covers searching for one, two or three bytes, forward or backward. When you search for more than one byte, a position counts as a match if the byte at that position matches any of the bytes, which makes it the primitive behind things like finding the next of a set of delimiters.

The memmem submodule is the substring search, also forward and reverse.

Every routine in both places works on &[u8] and makes no assumption about encoding. The README puts it plainly: this is what you want when searching either UTF-8 or arbitrary bytes. That is the design decision that keeps the crate small. There is no string type, no encoding detection and no allocation in the search path, so the same call works on a byte buffer that happens to be text and on one that is a compressed frame.

Cargo.toml records the same scope in the package description: extremely fast routines for 1, 2 or 3 byte search and single substring search, using SIMD on x86_64, aarch64 and wasm32. Version 2.8.3, edition 2021, rust-version 1.61, dual licensed Unlicense OR MIT, with Andrew Gallant and bluss listed as authors.

The algorithm depends on the sizes involved

This is the part of the README that explains the crate's behaviour rather than its API.

For very small haystacks, Rabin-Karp is used to reduce latency. The rationale given is that it has very small overhead and can often complete before other searchers have even been constructed. On a short buffer, setup cost is the whole cost.

For small needles, a variant of the Generic SIMD algorithm is used. Instead of using the first and last bytes, a heuristic selects bytes based on a background distribution of byte frequencies, which is a better bet when you do not know what your data looks like.

In all other cases the Two-Way algorithm is used, and if possible a prefilter based on that same Generic SIMD algorithm finds candidates quickly. A dynamic heuristic watches whether the prefilter is effective and disables it when it is not, which is the safety valve: a badly chosen prefilter on pathological data would otherwise slow the search down rather than speed it up.

So the crate is not one algorithm with SIMD bolted on. It is three strategies plus an adaptive prefilter, chosen per call.

Why the standard library search is slower, and the honest caveat

The README spends its longest section on this, and the argument is about API design rather than assembly.

The benchmark infrastructure distinguishes two classes. The prebuilt benchmarks build a searcher and then measure only the time spent using it. The oneshot benchmarks measure building the searcher and using it together.

In the prebuilt ranking shown in the README, rust/memchr scores a geometric mean of 1.03 against rust/std at 6.50 across 53 benchmarks, and in the oneshot ranking the figures are 1.04 against 5.26. In other words, memchr is substantially faster across that broad sample, and the gap narrows a little when construction time is counted.

The explanation is that the standard library only offers APIs that require reconstructing the searcher for every search. You can build once and iterate matches in a single string, but you cannot reuse that searcher on another string. If you search a file one line at a time, you rebuild for every line, and the README links to a blog post arguing that this can really matter.

The caveat is stated too. The prebuilt benchmark for the standard library cannot avoid measuring construction at some level because no API exists for it, so the comparison is not strictly apples-to-apples. The README also notes that rebar rank can be replaced with rebar cmp to explore individual benchmarks.

no_std costs you runtime CPU detection

Disabling the standard library is a supported configuration with one real trade-off. The manifest documents it directly:

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

The consequence is that on x86_64 with std disabled you get the SSE2 accelerated implementations, while with std enabled you get AVX2 if the CPU is determined to support it at runtime. Runtime detection is what std buys you.

SIMD routines are also available on wasm32 and aarch64, and the std feature is not required to use them. When no SIMD version is available, the crate falls back to SWAR techniques, which process a machine word at a time with bitwise arithmetic rather than one byte at a time.

The feature list in Cargo.toml is small and well commented. default is std, std implies alloc, alloc enables APIs that require allocation such as Finder::into_owned and explicitly does not enable runtime CPU detection. Two features are deprecated and marked for removal: use_std is an alias for std and will be removed in memchr 3, and libc is deprecated as well. logging, off by default, emits strategy messages through the log crate, which is described as useful when debugging performance problems.

Testing, MSRV policy and where this is the wrong tool

The testing strategy is the strongest signal about how the code should be trusted. Given the complexity and the pervasive use of unsafe, the crate combines hand-written tests, exhaustive-style testing meant to exercise all branching and offset calculations, property based testing through quickcheck, fuzz testing through cargo fuzz, and a large suite of benchmarks that are also run as tests, where benchmarks always confirm the expected result occurs.

Running benchmarks as correctness tests is the unusual part. It means the benchmark corpus doubles as a regression suite, which is how an SIMD library catches a wrong result on an alignment edge case.

The minimum Rust version policy is explicit: the floor is rustc 1.61.0, it can be raised in minor version updates but never retroactively within a major version, so 1.0.z keeps whatever 1.0 required while 1.y for y greater than zero may require something newer. The stated intent is to be conservative.

Where it is the wrong tool: on a handful of bytes, a hand-written loop is clearer and fast enough. And if your program searches a fresh buffer once and throws it away, the reusable Finder advantage does not apply, so the standard library remains a reasonable choice. The win shows up when you search repeatedly, and the repository publishes no GitHub releases, so version tracking goes through Cargo.toml and crates.io.

Editorial conclusion

memchr is the right dependency when a Rust program searches large buffers repeatedly, or searches many small ones where construction cost dominates, since its Finder is reusable across haystacks while the standard library searcher is not. It is not worth reaching for on a tiny input where a simple loop is clearer. Before disabling default features, remember that turning off std disables runtime CPU detection, so x86_64 builds fall back to SSE2 even on hardware that supports AVX2, and check whether the deprecated use_std and libc features still appear in your dependency tree.

Frequently asked questions

Official sources

1. BurntSushi/memchr on GitHub
2. Issues
3. License: Unlicense
4. README