memchr

The memchr library provides highly optimized routines for string search primitives. It operates on &[u8] (byte slices) without regard to encoding, making it suitable for both UTF-8 and arbitrary byte sequences.

Key features include:

• Top-level module: Routines for searching for 1, 2, or 3 bytes in both forward and reverse directions. When searching for multiple bytes, a match is found if the byte at a position matches any of the target bytes.
• memmem sub-module: Provides forward and reverse substring search routines.

The crate selects different algorithms based on the input characteristics to optimize performance:

• Small haystacks: Uses the Rabin-Karp algorithm to minimize latency and overhead.
• Small needles: Uses a variant of the Generic SIMD algorithm, employing a heuristic to select bytes based on background byte frequency distributions.
• General cases: Uses the Two-Way string-matching algorithm. If possible, it uses a Generic SIMD prefilter to find candidates quickly, with a dynamic heuristic to disable the prefilter if it proves ineffective.

The minimum supported rustc version for this crate is 1.61.0.

The policy allows the minimum version to be increased during minor version updates (e.g., 1.0.z will always support the same minimum as 1.0.0), but major version updates (e.g., 1.y where y > 0) may require a newer minimum Rust version.

The random-huge dataset, which consists of long lines of principally random data, can be generated using the following command. This dataset is modeled after real-world benchmarks reported to ripgrep and is used to test the robustness of the memmem implementation.

dd if=/dev/urandom bs=32 count=10000 | xxd -ps -c32

By default, memchr links to the standard library. If you are building a #![no_std] crate, you can disable the std feature in your Cargo.toml.

Platform-specific behavior when std is disabled on x86_64:

• Uses SSE2 accelerated implementations.

Platform-specific behavior when std is enabled on x86_64:

• Uses AVX2 accelerated implementations if the CPU supports it at runtime.

SIMD accelerated routines are also available for wasm32 and aarch64 targets without requiring the std feature. If no SIMD version is available, the crate falls back to SWAR techniques.

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

If you are searching for the same needle across many different haystacks, you can avoid the overhead of repeatedly constructing a searcher by using memmem::Finder (for forward searches) or memmem::FinderRev (for reverse searches).

Construct the Finder once and call .find() or .rfind() on it for each haystack.

Complexity: Both routines have worst-case linear time complexity O(needle.len() + haystack.len()) and worst-case constant space complexity.

The crate provides several features to control its capabilities and performance:

• std: (Default) Enables standard library features, specifically allowing runtime SIMD CPU feature detection. This is required to get AVX2 acceleration on x86_64 without enabling the avx2 compile-time feature.
• alloc: (Default) Enables APIs that require allocation, such as memmem::Finder::into_owned.
• logging: Enables the log crate to emit messages about which specific SIMD or fallback algorithms are being used. Useful for debugging performance.
• libc: DEPRECATED. No longer used.

The library provides specialized iterators for searching multiple needles:

• memchr2_iter(needle1, needle2, haystack) returns a Memchr2 iterator.
• memchr3_iter(needle1, needle2, needle3, haystack) returns a Memchr3 iterator.

Both implement DoubleEndedIterator, so you can use .rev() to iterate through matches from the end of the haystack to the beginning.

Use memchr to find the first occurrence of a specific byte (u8) within a byte slice (&[u8]). It returns Option<usize> containing the index of the match.

use memchr::memchr;

let haystack = b"foo bar baz quuz";
assert_eq!(Some(10), memchr(b'z', haystack));

Use memchr2 to find the first occurrence of either needle1 or needle2 in a slice, or memrchr2 to find the last occurrence. This is semantically equivalent to haystack.iter().position(|&b| b == needle1 || b == needle2) but optimized for performance.

use memchr::memchr2;

let haystack = b"the quick brown fox";
assert_eq!(memchr2(b'k', b'q', haystack), Some(4));