| 1 |
memchr |
| 2 |
====== |
| 3 |
This library provides heavily optimized routines for string search primitives. |
| 4 |
|
| 5 |
[](https://github.com/BurntSushi/memchr/actions) |
| 6 |
[](https://crates.io/crates/memchr) |
| 7 |
|
| 8 |
Dual-licensed under MIT or the [UNLICENSE](https://unlicense.org/). |
| 9 |
|
| 10 |
|
| 11 |
### Documentation |
| 12 |
|
| 13 |
[https://docs.rs/memchr](https://docs.rs/memchr) |
| 14 |
|
| 15 |
|
| 16 |
### Overview |
| 17 |
|
| 18 |
* The top-level module provides routines for searching for 1, 2 or 3 bytes |
| 19 |
in the forward or reverse direction. When searching for more than one byte, |
| 20 |
positions are considered a match if the byte at that position matches any |
| 21 |
of the bytes. |
| 22 |
* The `memmem` sub-module provides forward and reverse substring search |
| 23 |
routines. |
| 24 |
|
| 25 |
In all such cases, routines operate on `&[u8]` without regard to encoding. This |
| 26 |
is exactly what you want when searching either UTF-8 or arbitrary bytes. |
| 27 |
|
| 28 |
### Compiling without the standard library |
| 29 |
|
| 30 |
memchr links to the standard library by default, but you can disable the |
| 31 |
`std` feature if you want to use it in a `#![no_std]` crate: |
| 32 |
|
| 33 |
```toml |
| 34 |
[dependencies] |
| 35 |
memchr = { version = "2", default-features = false } |
| 36 |
``` |
| 37 |
|
| 38 |
On `x86_64` platforms, when the `std` feature is disabled, the SSE2 accelerated |
| 39 |
implementations will be used. When `std` is enabled, AVX2 accelerated |
| 40 |
implementations will be used if the CPU is determined to support it at runtime. |
| 41 |
|
| 42 |
SIMD accelerated routines are also available on the `wasm32` and `aarch64` |
| 43 |
targets. The `std` feature is not required to use them. |
| 44 |
|
| 45 |
When a SIMD version is not available, then this crate falls back to |
| 46 |
[SWAR](https://en.wikipedia.org/wiki/SWAR) techniques. |
| 47 |
|
| 48 |
### Minimum Rust version policy |
| 49 |
|
| 50 |
This crate's minimum supported `rustc` version is `1.61.0`. |
| 51 |
|
| 52 |
The current policy is that the minimum Rust version required to use this crate |
| 53 |
can be increased in minor version updates. For example, if `crate 1.0` requires |
| 54 |
Rust 1.20.0, then `crate 1.0.z` for all values of `z` will also require Rust |
| 55 |
1.20.0 or newer. However, `crate 1.y` for `y > 0` may require a newer minimum |
| 56 |
version of Rust. |
| 57 |
|
| 58 |
In general, this crate will be conservative with respect to the minimum |
| 59 |
supported version of Rust. |
| 60 |
|
| 61 |
|
| 62 |
### Testing strategy |
| 63 |
|
| 64 |
Given the complexity of the code in this crate, along with the pervasive use |
| 65 |
of `unsafe`, this crate has an extensive testing strategy. It combines multiple |
| 66 |
approaches: |
| 67 |
|
| 68 |
* Hand-written tests. |
| 69 |
* Exhaustive-style testing meant to exercise all possible branching and offset |
| 70 |
calculations. |
| 71 |
* Property based testing through [`quickcheck`](https://github.com/BurntSushi/quickcheck). |
| 72 |
* Fuzz testing through [`cargo fuzz`](https://github.com/rust-fuzz/cargo-fuzz). |
| 73 |
* A huge suite of benchmarks that are also run as tests. Benchmarks always |
| 74 |
confirm that the expected result occurs. |
| 75 |
|
| 76 |
Improvements to the testing infrastructure are very welcome. |
| 77 |
|
| 78 |
|
| 79 |
### Algorithms used |
| 80 |
|
| 81 |
At time of writing, this crate's implementation of substring search actually |
| 82 |
has a few different algorithms to choose from depending on the situation. |
| 83 |
|
| 84 |
* For very small haystacks, |
| 85 |
[Rabin-Karp](https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm) |
| 86 |
is used to reduce latency. Rabin-Karp has very small overhead and can often |
| 87 |
complete before other searchers have even been constructed. |
| 88 |
* For small needles, a variant of the |
| 89 |
["Generic SIMD"](http://0x80.pl/articles/simd-strfind.html#algorithm-1-generic-simd) |
| 90 |
algorithm is used. Instead of using the first and last bytes, a heuristic is |
| 91 |
used to select bytes based on a background distribution of byte frequencies. |
| 92 |
* In all other cases, |
| 93 |
[Two-Way](https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm) |
| 94 |
is used. If possible, a prefilter based on the "Generic SIMD" algorithm |
| 95 |
linked above is used to find candidates quickly. A dynamic heuristic is used |
| 96 |
to detect if the prefilter is ineffective, and if so, disables it. |
| 97 |
|
| 98 |
|
| 99 |
### Why is the standard library's substring search so much slower? |
| 100 |
|
| 101 |
We'll start by establishing what the difference in performance actually |
| 102 |
is. There are two relevant benchmark classes to consider: `prebuilt` and |
| 103 |
`oneshot`. The `prebuilt` benchmarks are designed to measure---to the extent |
| 104 |
possible---search time only. That is, the benchmark first starts by building a |
| 105 |
searcher and then only tracking the time for _using_ the searcher: |
| 106 |
|
| 107 |
``` |
| 108 |
$ rebar rank benchmarks/record/x86_64/2023-08-26.csv --intersection -e memchr/memmem/prebuilt -e std/memmem/prebuilt |
| 109 |
Engine Version Geometric mean of speed ratios Benchmark count |
| 110 |
------ ------- ------------------------------ --------------- |
| 111 |
rust/memchr/memmem/prebuilt 2.5.0 1.03 53 |
| 112 |
rust/std/memmem/prebuilt 1.73.0-nightly 180dffba1 6.50 53 |
| 113 |
``` |
| 114 |
|
| 115 |
Conversely, the `oneshot` benchmark class measures the time it takes to both |
| 116 |
build the searcher _and_ use it: |
| 117 |
|
| 118 |
``` |
| 119 |
$ rebar rank benchmarks/record/x86_64/2023-08-26.csv --intersection -e memchr/memmem/oneshot -e std/memmem/oneshot |
| 120 |
Engine Version Geometric mean of speed ratios Benchmark count |
| 121 |
------ ------- ------------------------------ --------------- |
| 122 |
rust/memchr/memmem/oneshot 2.5.0 1.04 53 |
| 123 |
rust/std/memmem/oneshot 1.73.0-nightly 180dffba1 5.26 53 |
| 124 |
``` |
| 125 |
|
| 126 |
**NOTE:** Replace `rebar rank` with `rebar cmp` in the above commands to |
| 127 |
explore the specific benchmarks and their differences. |
| 128 |
|
| 129 |
So in both cases, this crate is quite a bit faster over a broad sampling of |
| 130 |
benchmarks regardless of whether you measure only search time or search time |
| 131 |
plus construction time. The difference is a little smaller when you include |
| 132 |
construction time in your measurements. |
| 133 |
|
| 134 |
These two different types of benchmark classes make for a nice segue into |
| 135 |
one reason why the standard library's substring search can be slower: API |
| 136 |
design. In the standard library, the only APIs available to you require |
| 137 |
one to re-construct the searcher for every search. While you can benefit |
| 138 |
from building a searcher once and iterating over all matches in a single |
| 139 |
string, you cannot reuse that searcher to search other strings. This might |
| 140 |
come up when, for example, searching a file one line at a time. You'll need |
| 141 |
to re-build the searcher for every line searched, and this can [really |
| 142 |
matter][burntsushi-bstr-blog]. |
| 143 |
|
| 144 |
**NOTE:** The `prebuilt` benchmark for the standard library can't actually |
| 145 |
avoid measuring searcher construction at some level, because there is no API |
| 146 |
for it. Instead, the benchmark consists of building the searcher once and then |
| 147 |
finding all matches in a single string via an iterator. This tends to |
| 148 |
approximate a benchmark where searcher construction isn't measured, but it |
| 149 |
isn't perfect. While this means the comparison is not strictly |
| 150 |
apples-to-apples, it does reflect what is maximally possible with the standard |
| 151 |
library, and thus reflects the best that one could do in a real world scenario. |
| 152 |
|
| 153 |
While there is more to the story than just API design here, it's important to |
| 154 |
point out that even if the standard library's substring search were a precise |
| 155 |
clone of this crate internally, it would still be at a disadvantage in some |
| 156 |
workloads because of its API. (The same also applies to C's standard library |
| 157 |
`memmem` function. There is no way to amortize construction of the searcher. |
| 158 |
You need to pay for it on every call.) |
| 159 |
|
| 160 |
The other reason for the difference in performance is that |
| 161 |
the standard library has trouble using SIMD. In particular, substring search |
| 162 |
is implemented in the `core` library, where platform specific code generally |
| 163 |
can't exist. That's an issue because in order to utilize SIMD beyond SSE2 |
| 164 |
while maintaining portable binaries, one needs to use [dynamic CPU feature |
| 165 |
detection][dynamic-cpu], and that in turn requires platform specific code. |
| 166 |
While there is [an RFC for enabling target feature detection in |
| 167 |
`core`][core-feature], it doesn't yet exist. |
| 168 |
|
| 169 |
The bottom line here is that `core`'s substring search implementation is |
| 170 |
limited to making use of SSE2, but not AVX. |
| 171 |
|
| 172 |
Still though, this crate does accelerate substring search even when only SSE2 |
| 173 |
is available. The standard library could therefore adopt the techniques in this |
| 174 |
crate just for SSE2. The reason why that hasn't happened yet isn't totally |
| 175 |
clear to me. It likely needs a champion to push it through. The standard |
| 176 |
library tends to be more conservative in these things. With that said, the |
| 177 |
standard library does use some [SSE2 acceleration on `x86-64`][std-sse2] added |
| 178 |
in [this PR][std-sse2-pr]. However, at the time of writing, it is only used |
| 179 |
for short needles and doesn't use the frequency based heuristics found in this |
| 180 |
crate. |
| 181 |
|
| 182 |
**NOTE:** Another thing worth mentioning is that the standard library's |
| 183 |
substring search routine requires that both the needle and haystack have type |
| 184 |
`&str`. Unless you can assume that your data is valid UTF-8, building a `&str` |
| 185 |
will come with the overhead of UTF-8 validation. This may in turn result in |
| 186 |
overall slower searching depending on your workload. In contrast, the `memchr` |
| 187 |
crate permits both the needle and the haystack to have type `&[u8]`, where |
| 188 |
`&[u8]` can be created from a `&str` with zero cost. Therefore, the substring |
| 189 |
search in this crate is strictly more flexible than what the standard library |
| 190 |
provides. |
| 191 |
|
| 192 |
[burntsushi-bstr-blog]: https://blog.burntsushi.net/bstr/#motivation-based-on-performance |
| 193 |
[dynamic-cpu]: https://doc.rust-lang.org/std/arch/index.html#dynamic-cpu-feature-detection |
| 194 |
[core-feature]: https://github.com/rust-lang/rfcs/pull/3469 |
| 195 |
[std-sse2]: https://github.com/rust-lang/rust/blob/bf9229a2e366b4c311f059014a4aa08af16de5d8/library/core/src/str/pattern.rs#L1719-L1857 |
| 196 |
[std-sse2-pr]: https://github.com/rust-lang/rust/pull/103779 |