chore: Update docs for - wip: Stringzilla

Cargo.lock

@@ -645,7 +645,7 @@ name = "fff-grep"
 version = "0.5.1"
 dependencies = [
  "bstr",
- "memchr",
+ "stringzilla",
 ]
 
 [[package]]
@@ -741,6 +741,7 @@ dependencies = [
  "serde_json",
  "smallvec",
  "smartstring",
+ "stringzilla",
  "tempfile",
  "thiserror 2.0.18",
  "toml",
@@ -2230,6 +2231,13 @@ version = "1.1.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "a2eb9349b6444b326872e140eb1cf5e7c522154d69e7a0ffb0fb81c06b37543f"
 
+[[package]]
+name = "stringzilla"
+version = "4.6.0"
+dependencies = [
+ "cc",
+]
+
 [[package]]
 name = "strsim"
 version = "0.11.1"

crates/fff-core/Cargo.toml

@@ -39,7 +39,7 @@ glidesort = { workspace = true }
 globset = { workspace = true }
 fff-grep = { workspace = true  }
 aho-corasick = "1"
-memchr = "2"
+stringzilla = { path = "/Users/neogoose/dev/StringZilla" }
 heed = { workspace = true }
 ignore = { workspace = true }
 memmap2 = { workspace = true }
@@ -58,6 +58,7 @@ tracing-appender = "0.2"
 tracing-subscriber = { version = "0.3", features = ["env-filter"] }
 zlob = { workspace = true, optional = true }
 libmimalloc-sys = { version = "0.1", optional = true, features = ["extended"] }
+memchr = "2.8.0"
 # Platform-specific: dunce for Windows to avoid \\?\ extended path prefix
 [target.'cfg(windows)'.dependencies]
 dunce = { workspace = true }

crates/fff-core/src/case_insensitive_memmem.rs

@@ -9,6 +9,38 @@
 //! both simultaneously, verify candidates.  This gives quadratic selectivity
 //! over the single-byte memchr2 approach.
 
+use stringzilla::sz;
+
+/// Iterator yielding byte positions matching any byte in a `Byteset`.
+/// Replaces `memchr::memchr_iter` / `memchr::memchr2_iter`.
+pub(crate) struct BytesetPositions<'a> {
+    haystack: &'a [u8],
+    byteset: sz::Byteset,
+    pos: usize,
+}
+
+impl<'a> BytesetPositions<'a> {
+    pub(crate) fn new(haystack: &'a [u8], bytes: &[u8]) -> Self {
+        Self {
+            haystack,
+            byteset: sz::Byteset::from_bytes(bytes),
+            pos: 0,
+        }
+    }
+}
+
+impl Iterator for BytesetPositions<'_> {
+    type Item = usize;
+
+    #[inline]
+    fn next(&mut self) -> Option<usize> {
+        let offset = sz::find_byteset(&self.haystack[self.pos..], self.byteset)?;
+        let abs = self.pos + offset;
+        self.pos = abs + 1;
+        Some(abs)
+    }
+}
+
 // this is stolen from the memchr2 crate
 const BYTE_FREQUENCIES: [u8; 256] = [
     55, 52, 51, 50, 49, 48, 47, 46, 45, 103, 242, 66, 67, 229, 44, 43, // 0x00
@@ -327,19 +359,15 @@ unsafe fn search_packed_pair_neon(
         let tail_end = last_start + rare_pos + 1;
         if tail_start < tail_end {
             let tail_space = &haystack[tail_start..tail_end];
-            if rare_byte.is_ascii_lowercase() {
-                for pos in memchr::memchr2_iter(rare_byte, ascii_swap_case(rare_byte), tail_space) {
-                    let candidate = offset + pos;
-                    if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
-                        return true;
-                    }
-                }
+            let bytes: &[u8] = if rare_byte.is_ascii_lowercase() {
+                &[rare_byte, ascii_swap_case(rare_byte)]
             } else {
-                for pos in memchr::memchr_iter(rare_byte, tail_space) {
-                    let candidate = offset + pos;
-                    if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
-                        return true;
-                    }
+                &[rare_byte]
+            };
+            for pos in BytesetPositions::new(tail_space, bytes) {
+                let candidate = offset + pos;
+                if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
+                    return true;
                 }
             }
         }
@@ -458,19 +486,15 @@ unsafe fn search_packed_pair_avx2(
         let tail_end = last_start + rare_pos + 1;
         if tail_start < tail_end {
             let tail_space = &haystack[tail_start..tail_end];
-            if rare_byte.is_ascii_lowercase() {
-                for pos in memchr::memchr2_iter(rare_byte, ascii_swap_case(rare_byte), tail_space) {
-                    let candidate = offset + pos;
-                    if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
-                        return true;
-                    }
-                }
+            let bytes: &[u8] = if rare_byte.is_ascii_lowercase() {
+                &[rare_byte, ascii_swap_case(rare_byte)]
             } else {
-                for pos in memchr::memchr_iter(rare_byte, tail_space) {
-                    let candidate = offset + pos;
-                    if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
-                        return true;
-                    }
+                &[rare_byte]
+            };
+            for pos in BytesetPositions::new(tail_space, bytes) {
+                let candidate = offset + pos;
+                if unsafe { verify_dispatch(ptr.add(candidate), needle_lower) } {
+                    return true;
                 }
             }
         }
@@ -544,18 +568,14 @@ pub fn search(haystack: &[u8], needle_lower: &[u8]) -> bool {
     let search_space = &haystack[..=haystack.len() - n];
     let first = needle_lower[0];
 
-    if first.is_ascii_lowercase() {
-        let alt = ascii_swap_case(first);
-        for pos in memchr::memchr2_iter(first, alt, search_space) {
-            if unsafe { verify_dispatch(haystack.as_ptr().add(pos), needle_lower) } {
-                return true;
-            }
-        }
+    let bytes: &[u8] = if first.is_ascii_lowercase() {
+        &[first, ascii_swap_case(first)]
     } else {
-        for pos in memchr::memchr_iter(first, search_space) {
-            if unsafe { verify_dispatch(haystack.as_ptr().add(pos), needle_lower) } {
-                return true;
-            }
+        &[first]
+    };
+    for pos in BytesetPositions::new(search_space, bytes) {
+        if unsafe { verify_dispatch(haystack.as_ptr().add(pos), needle_lower) } {
+            return true;
         }
     }
     false

crates/fff-core/src/grep.rs

@@ -13,6 +13,9 @@ use crate::{
     types::{ContentCacheBudget, FileItem},
 };
 use aho_corasick::AhoCorasick;
+use stringzilla::sz;
+
+
 pub use fff_grep::{
     Searcher, SearcherBuilder, Sink, SinkMatch,
     lines::{self, LineStep},
@@ -329,11 +332,11 @@ pub struct GrepSearchOptions {
 }
 
 #[derive(Clone, Copy)]
-struct GrepContext<'a, 'b> {
+struct GrepContext<'a> {
     total_files: usize,
     filtered_file_count: usize,
     budget: &'a ContentCacheBudget,
-    prefilter: Option<&'a memchr::memmem::Finder<'b>>,
+    prefilter: Option<&'a sz::Finder<'a>>,
     prefilter_case_insensitive: bool,
     is_cancelled: Option<&'a AtomicBool>,
 }
@@ -389,6 +392,8 @@ struct PlainTextMatcher<'a> {
     /// Case-folded needle bytes for case-insensitive matching.
     /// When case-sensitive, this is the original pattern bytes.
     needle: &'a [u8],
+    /// Pre-compiled finder for the case-sensitive fast path.
+    finder: &'a sz::Finder<'a>,
     case_insensitive: bool,
 }
 
@@ -400,11 +405,10 @@ impl Matcher for PlainTextMatcher<'_> {
         let hay = &haystack[at..];
 
         let found = if self.case_insensitive {
-            // ASCII case-insensitive: lowercase the haystack slice on the fly.
-            // We scan with a rolling window to avoid allocating a full copy.
+            // ASCII case-insensitive: scan for first-byte candidates, then verify.
             ascii_case_insensitive_find(hay, self.needle)
         } else {
-            memchr::memmem::find(hay, self.needle)
+            self.finder.find(hay)
         };
 
         Ok(found.map(|pos| Match::new(at + pos, at + pos + self.needle.len())))
@@ -437,14 +441,14 @@ fn ascii_case_insensitive_find(haystack: &[u8], needle_lower: &[u8]) -> Option<u
 
     // Single-byte needle: just find either case variant.
     if nlen == 1 {
-        return memchr::memchr2(first_lo, first_hi, haystack);
+        return sz::find_byte_from(haystack, &[first_lo, first_hi]);
     }
 
     let tail = &needle_lower[1..];
     let end = haystack.len() - nlen;
 
     // Scan for candidates where the first byte matches (either case).
-    for pos in memchr::memchr2_iter(first_lo, first_hi, &haystack[..=end]) {
+    for pos in case_insensitive_memmem::BytesetPositions::new(&haystack[..=end], &[first_lo, first_hi]) {
         // Verify the remaining bytes with bitwise ASCII case-insensitive compare.
         // For ASCII letters, (a ^ b) & ~0x20 == 0 when they match ignoring case.
         // For non-letters, exact equality is required; OR-ing with 0x20 maps both
@@ -657,7 +661,7 @@ fn truncate_display_bytes(bytes: &[u8]) -> &[u8] {
 /// No regex engine is involved at any point.
 struct PlainTextSink<'r> {
     state: SinkState,
-    finder: &'r memchr::memmem::Finder<'r>,
+    finder: &'r sz::Finder<'r>,
     pattern_len: u32,
     case_insensitive: bool,
 }
@@ -1059,7 +1063,7 @@ const PAGINATED_CHUNK_SIZE: usize = 512;
 fn perform_grep<'a, F>(
     files_to_search: &[&'a FileItem],
     options: &GrepSearchOptions,
-    ctx: &GrepContext<'_, '_>,
+    ctx: &GrepContext<'_>,
     search_file: F,
 ) -> GrepResult<'a>
 where
@@ -1130,7 +1134,7 @@ where
                     let found = if ctx.prefilter_case_insensitive {
                         case_insensitive_memmem::search_packed_pair(&content, pf.needle())
                     } else {
-                        pf.find(&content).is_some()
+                        pf.find(&*content).is_some()
                     };
                     if !found {
                         return None;
@@ -1781,7 +1785,6 @@ pub fn grep_search<'a>(
     } else {
         effective_pattern.as_bytes().to_vec()
     };
-    let finder = memchr::memmem::Finder::new(&finder_pattern);
     let pattern_len = finder_pattern.len() as u32;
 
     // Bigram prefiltering: query the inverted index + merge overlay.
@@ -1887,8 +1890,10 @@ pub fn grep_search<'a>(
 
     // `PlainTextMatcher` is used by the grep-searcher engine for line detection.
     // `PlainTextSink` / `RegexSink` handle highlight extraction independently.
+    let finder = sz::Finder::new(&finder_pattern);
     let plain_matcher = PlainTextMatcher {
         needle: &finder_pattern,
+        finder: &finder,
         case_insensitive,
     };
 

crates/fff-grep/Cargo.toml

@@ -8,4 +8,4 @@ edition = "2024"
 
 [dependencies]
 bstr = { version = "1.6.2", default-features = false, features = ["std"] }
-memchr = "2.6.3"
+stringzilla = { path = "/Users/neogoose/dev/StringZilla" }

crates/fff-grep/src/lines.rs

@@ -65,7 +65,15 @@ impl LineStep {
 
 /// Count the number of occurrences of `line_term` in `bytes`.
 pub fn count(bytes: &[u8], line_term: u8) -> u64 {
-    memchr::memchr_iter(line_term, bytes).count() as u64
+    use stringzilla::sz;
+    let bs = sz::Byteset::from_bytes(&[line_term]);
+    let mut count = 0u64;
+    let mut pos = 0usize;
+    while let Some(idx) = sz::find_byteset(&bytes[pos..], bs) {
+        count += 1;
+        pos += idx + 1;
+    }
+    count
 }
 
 /// Given a line that possibly ends with a terminator, return that line without

crates/fff-nvim/Cargo.toml

@@ -40,6 +40,10 @@ name = "bench_grep_query"
 ppath = "src/bin/bench_grep_query.rs"
 path = "src/bin/bench_grep_query.rs"
 
+[[bin]]
+name = "bench_memchr_vs_sz"
+path = "src/bin/bench_memchr_vs_sz.rs"
+
 [dependencies]
 # Workspace dependencies
 ahash = { workspace = true }

doc/fff.nvim.txt

@@ -1,4 +1,4 @@
-*fff.nvim.txt*         For Neovim >= 0.10.0         Last change: 2026 April 03
+*fff.nvim.txt*         For Neovim >= 0.10.0         Last change: 2026 April 06
 
 ==============================================================================
 Table of Contents                                 *fff.nvim-table-of-contents*