memchr

B/s (1.00x) 25.3 GB/s (1.42x) memmem/subtitles/common/huge-en-you 15.9 GB/s (1.00x) 9.5 GB/s (1.67x) memmem/subtitles/common/huge-en-one-space 1376.4 MB/s (1.00x) 1364.0 MB/s (1.01x) memmem/subtitles/common/huge-ru-that 29.0 GB/s (1.00x) 15.5 GB/s (1.87x) memmem/subtitles/common/huge-ru-not 16.0 GB/s (1.00x) 3.5 GB/s (4.53x) memmem/subtitles/common/huge-ru-one-space 2.6 GB/s (1.00x) 2.4 GB/s (1.08x) memmem/subtitles/common/huge-zh-that 31.2 GB/s (1.00x) 23.8 GB/s (1.31x) memmem/subtitles/common/huge-zh-do-not 19.4 GB/s (1.00x) 12.1 GB/s (1.59x) memmem/subtitles/common/huge-zh-one-space 5.3 GB/s (1.05x) 5.6 GB/s (1.00x) memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x) memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x) memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x) memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x) memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x) memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x) memmem/subtitles/rare/huge-en-sherlock-holmes 40.8 GB/s (1.05x) 42.9 GB/s (1.00x) memmem/subtitles/rare/huge-en-sherlock 36.7 GB/s (1.16x) 42.5 GB/s (1.00x) memmem/subtitles/rare/huge-en-medium-needle 47.7 GB/s (1.00x) 31.3 GB/s (1.52x) memmem/subtitles/rare/huge-en-long-needle 44.5 GB/s (1.00x) 32.0 GB/s (1.39x) memmem/subtitles/rare/huge-en-huge-needle 45.7 GB/s (1.00x) 33.4 GB/s (1.37x) memmem/subtitles/rare/huge-ru-sherlock-holmes 42.1 GB/s (1.00x) 42.2 GB/s (1.00x) memmem/subtitles/rare/huge-ru-sherlock 42.3 GB/s (1.01x) 42.9 GB/s (1.00x) memmem/subtitles/rare/huge-zh-sherlock-holmes 46.7 GB/s (1.00x) 33.1 GB/s (1.41x) memmem/subtitles/rare/huge-zh-sherlock 47.4 GB/s (1.00x) 42.8 GB/s (1.11x) But I would say they are overall pretty competitive. If you want to run the benchmarks yourself, you can. First, get rebar[1]. Then, from the root of the `memchr` repository[2]: $ rebar build -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' stringzilla/memmem/oneshot: running: cd "benchmarks/./engines/stringzilla" && "cargo" "build" "--release" stringzilla/memmem/oneshot: build complete for version 3.12.3 rust/memchr/memmem/prebuilt: running: cd "benchmarks/./engines/rust-memchr" && "cargo" "build" "--release" rust/memchr/memmem/prebuilt: build complete for version 2.7.4 $ rebar measure -e 'rust/memchr/memmem/prebuilt' -e 'stringzilla/memmem/oneshot' | tee results.csv $ rebar rank results.csv Engine Version Geometric mean of speed ratios Benchmark count ------ ------- ------------------------------ --------------- rust/memchr/memmem/prebuilt 2.7.4 1.14 57 stringzilla/memmem/oneshot 3.12.3 1.43 54 $ rebar cmp results.csv --intersection -f never/huge benchmark rust/memchr/memmem/prebuilt stringzilla/memmem/oneshot --------- --------------------------- -------------------------- memmem/subtitles/never/huge-en-john-watson 41.2 GB/s (1.00x) 31.2 GB/s (1.32x) memmem/subtitles/never/huge-en-all-common-bytes 47.9 GB/s (1.00x) 37.5 GB/s (1.28x) memmem/subtitles/never/huge-en-some-rare-bytes 43.4 GB/s (1.00x) 42.7 GB/s (1.02x) memmem/subtitles/never/huge-en-two-space 42.2 GB/s (1.00x) 30.7 GB/s (1.37x) memmem/subtitles/never/huge-ru-john-watson 42.2 GB/s (1.00x) 42.1 GB/s (1.00x) memmem/subtitles/never/huge-zh-john-watson 47.6 GB/s (1.00x) 34.0 GB/s (1.40x) See also: https://github.com/BurntSushi/memchr/discussions/159 [1]: https://github.com/BurntSushi/rebar [2]: https://github.com/BurntSushi/memchr

libc/memmem/oneshot' Engine Version Geometric mean of speed ratios Benchmark count ------ ------- ------------------------------ --------------- rust/memchr/memmem/prebuilt 2.7.1 1.07 57 rust/memchr/memmem/oneshot 2.7.1 1.39 54 libc/memmem/oneshot unknown 3.15 54 rust/memchr/memmem/twoway 2.7.1 5.26 54 The "prebuilt" benchmarks also demonstrate the API deficiencies of routines like `memmem`. Because of their API, they need to rebuild the state necessary to execute a search for the needle given. But it is often the case that the needle is invariant across repeated calls with different haystacks. So you end up doing that repeated work for no gain.

om/BurntSushi/memchr/blob/746182171d2e886006... Because it's faster to do that than it is to reuse the generalized `memchr` API for finding the location of matching bytes. And counting matches in a multi-threaded context is way easier than actual managing the printing of matches in the same order that you get them. krep isn't big. You can skim its source code in a few minutes and get a good idea of how it works.

Warning: Ignoring non-zero exit code. Benchmark 2: krep -c 'ZQZQZQZQ' subtitles2016-sample.en Time (mean ± σ): 122.8 ms ± 1.4 ms [User: 372.6 ms, System: 24.4 ms] Range (min … max): 120.2 ms … 125.5 ms 24 runs Summary rg -c 'ZQZQZQZQ' subtitles2016-sample.en ran 1.52 ± 0.03 times faster than krep -c 'ZQZQZQZQ' subtitles2016-sample.en That's a benchmark with no matches, which is the best case essentially for throughput. Now I want to try a benchmark with a high match frequency: $ hyperfine "rg -c 'the' subtitles2016-sample.en" "krep -c 'the' subtitles2016-sample.en" Benchmark 1: rg -c 'the' subtitles2016-sample.en Time (mean ± σ): 411.8 ms ± 3.6 ms [User: 389.7 ms, System: 21.1 ms] Range (min … max): 404.8 ms … 415.7 ms 10 runs Benchmark 2: krep -c 'the' subtitles2016-sample.en Time (mean ± σ): 121.2 ms ± 1.9 ms [User: 364.6 ms, System: 24.9 ms] Range (min … max): 113.2 ms … 123.0 ms 24 runs Summary krep -c 'the' subtitles2016-sample.en ran 3.40 ± 0.06 times faster than rg -c 'the' subtitles2016-sample.en Which is very nice. So I decided to poke at it: $ krep -c the subtitles2016-sample.en Found 29794426 matches $ rg -c the subtitles2016-sample.en 6123710 $ grep -c the subtitles2016-sample.en 6123710 The counts are way off here. At first I thought maybe it was counting every occurrence of `the` instead of every matching line, but when I ask ripgrep to do that, it gets a different answer: $ rg -oc the subtitles2016-sample.en 7739791 $ rg -o the subtitles2016-sample.en | wc -l 7739791 $ grep -o the subtitles2016-sample.en | wc -l 7739791 So not sure what's going on here, but it looks like `krep` might not be giving accurate results. Pushing it a bit more, it seems like it just kind of falls over? $ time rg -c 'You read Sherlock Holmes to deduce that\?' subtitles2016-sample.en 10 real 0.076 user 0.049 sys 0.026 maxmem 923 MB faults 0 $ time krep -c 'You read Sherlock Holmes to deduce that?' subtitles2016-sample.en Found 0 matches real 0.935 user 3.597 sys 0.029 maxmem 918 MB faults 0 I ran the above benchmarks in `/dev/shm` on Linux with an i9-12900K. In terms of the approach here, ripgrep is already using a pretty sophisticated substring search algorithm: https://github.com/BurntSushi/memchr?tab=readme-ov-file#algo... And it uses memory maps (sometimes, when it thinks it will be fast, but it will do so in the single file case on Linux). ripgrep also uses parallelism, but at inter-file level. It sounds like `krep` also uses parallelism, but will use multiple threads when searching a single file. I've considered doing the same in ripgrep, but haven't done enough experiments (or seen enough from someone else) to be convinced that it's the right way to go in general. It might edge out single threaded search in some cases for sure though. EDIT: Looking at the timings in https://dev.to/daviducolo/introducing-krep-building-a-high-p..., I see, for example, ripgrep taking >40 seconds to search for the literal pattern `error` in a 5GB file. Even if you're reading from disk (which the OP is using an SSD), that does not seem right at all. Even for an exceptionally common word like `the` in this haystack, ripgrep can chew through a 13GB file in 5 seconds on my machine: $ time rg -c the full.txt 83499915 real 5.404 user 5.092 sys 0.302 maxmem 12511 MB faults 0 Even if I force reading from disk, we get nowhere near 40 seconds: $ sudo sh -c 'echo 3 > /proc/sys/vm/drop_caches' $ time rg -c the full.txt 83499915 real 10.577 user 5.191 sys 2.105 maxmem 12511 MB faults 42 I'm not saying the benchmark results are definitely wrong, but something looks off here that I can't easily explain. OP, can you please share a way to fully reproduce your benchmark? (Like I did above for `subtitles2016-sample.en`.)

her factors at play here, and, importantly, what "long" means in this context. In many practical circumstances, "short" might be a few bytes, while "long" is 16 bytes. But maybe your idea of "long" is actually much longer. If you're curious how your own algorithm stacks up to ripgrep's, you can plug your implementation into the `memchr` crate's benchmark harness: https://github.com/BurntSushi/memchr It uses rebar: https://github.com/BurntSushi/rebar

he core/alloc/std split). [1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf... [3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

defined in `std` directly, but rather, in `core`. There are plans to fix this[6]. With all that said, I wouldn't necessarily disagree with the broader point in this thread. .NET's regex engine performance is quite impressive[7]. (And I still have to merge the PR updating to .NET 8.) I'm really only replying here to correct more narrow points. [1]: https://doc.rust-lang.org/std/arch/index.html [2]: https://doc.rust-lang.org/std/simd/index.html [3]: https://github.com/dotnet/runtime/blob/72fae0073b35a404f03c3... [4]: https://github.com/dotnet/runtime/pull/88394#issuecomment-16... [5]: https://github.com/BurntSushi/memchr#why-is-the-standard-lib... [6]: https://github.com/rust-lang/rfcs/pull/3469 [7]: https://github.com/BurntSushi/rebar#summary

t it scales constantly with input size? I'll answer your question with another: in what cases does it make sense to describe the scaling behavior of an algorithm as O(1)?

o very very badly for longer needles. * It seems quite likely that your [confirmation step](https://github.com/ashvardanian/Stringzilla/blob/fab854dc4fd...) is going to absolutely kill performance for even semi-frequently occurring candidates. The [`memchr` crate utilizes information from the vector step to limit where and when it calls `memcmp`](https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22...). Your code might do well in cases where matches are very rare. I took a quick peek at your benchmarks and don't see anything that obviously stresses this particular case. For substring search, the `memchr` crate uses a variant of the "[generic SIMD](http://0x80.pl/articles/simd-strfind.html#first-and-last)" algorithm. Basically, it takes two bytes from the needle, looks for positions where those occur and then attempts to check whether that position corresponds to a match. It looks like your technique uses the first 4 bytes. I suspect that might be overkill. (I did try using 3 bytes from the needle and found that it was a bit slower in some cases.) That is, two bytes is usually enough predictive power to lower the false positive rate enough. Of course, one can write pathological inputs that cause either one to do better than the other. (The `memchr` crat benchmark suite has a [collection of pathological inputs](https://github.com/BurntSushi/memchr/blob/46620054ff25b16d22...).) It would actually be possible to hook Stringzilla up to `memchr`'s benchmark suite if you were interested. :-) [1]: https://old.reddit.com/r/rust/comments/163ph8r/memchr_26_now... [2]: https://github.com/BurntSushi/memchr