# fsearch: whole-disk search on a Mac, and what the 17,000x is measured against
> Satyajit Ghana — Head of Engineering @ Inkers Technology
> canonical: https://ai.satyajit.si/articles/fsearch
> date: 2026-10-08
> tags: rust, search, performance, developer-tools, benchmarks
Noah Dunnagan posted a terminal recording on October 8: a search box, every keystroke answered across the whole disk of his M4 Max in a few milliseconds, "~60mb of ram". Later the same day he open-sourced it as [fsearch](https://github.com/noahdunnagan/fsearch) with the line "Full disk search, in milliseconds. 17,000x faster than Finder." A follow-up post in the same thread sets the tone better than any launch copy could: "this isnt mean to compete with fff or really any other file search. I was just curious what could be done for funzies."
I took him at his word and read it the way you read a friend's weekend project: all of it, with interest, and with the numbers checked. Two things surprised me. The name search, the part that answers in a millisecond, uses no clever index at all. And the 17,000x is not measured against Finder.
The repository is about 5,000 lines of Rust in ten files under `src/`, MIT-licensed, 27 commits written between October 5 and October 8. It is macOS only, and says so: the FSEvents bindings link Apple frameworks, which is why the first person in the replies who tried `cargo build` on Ubuntu got `link kind 'framework' is only supported on Apple targets`. I could not run it on this Linux machine, so everything below comes from reading the code, the two demo videos, the benchmark script and its JSON, plus one small measurement of my own that I describe at the end. There is no test suite in the repo; the earlier README instead reports accuracy measured against a fresh fd listing of the disk, with 99.95% of 2,000 random entries found by name.
## The number on the last frame
The launch video ends on this card. Everything else in this section is about the bar chart in it.
The 17,789x is fsearch against [fd](https://github.com/sharkdp/fd), not Finder. 62 seconds divided by 3.5 milliseconds is about 17,700; the printed figure presumably comes from unrounded times. The content number is the same shape: grep -r, killed after 7.7 minutes, against 8.2 ms.
So "faster than Finder" is a loose word for "faster than walking the disk". That matters because the comparison is between two different kinds of work. fd has no index. Every query reads every directory on the volume, 7.6 million entries, then filters. fsearch read those directories once, about 20 seconds by its own README, and every query after that touches a file it already holds. The ratio between "read the disk" and "read my copy of the disk" has no ceiling; it grows with the disk. Comparing an index lookup to a crawl tells you the index works. It does not tell you the index is fast compared to other indexes.
Two more details make the fd bar longer than it would be on most Macs. An earlier version of the README, at commit `f43261b`, measured "`fd` for one name, no index: 25.9 s" on the same machine, so the 62 s in the video is a slower run of the same thing, and the repo contains no script for it, so I can't tell how fd was invoked. And this Mac is unusually hostile to crawling. A comment in `src/walk.rs:104-107` explains:
```rust
// Children are opened with openat() relative to the parent's fd, so paths
// never get rebuilt and PATH_MAX never bites. Measured on this Mac: open() +
// close() is ~19us per directory (two Endpoint Security clients tax every
// open), getattrlistbulk ~14us; past ~8 threads the kernel side stops scaling.
```
Two Endpoint Security clients (the old README names MDM and a VPN) inspect every `open()`. A crawler pays that per directory, an index lookup never does. fsearch's own first crawl takes about 20 s under the same tax, roughly a third of fd's 62 s, which says something good about how it crawls (next section) and something about how much of fd's bar is the machine.
What would Finder actually be? Finder's search window and `mdfind` both query Spotlight, which is itself an index, kept live by the same kernel change stream, and which by default matches file contents and metadata as well as names. That is the comparison the tweet implies: index against index, names against names. Nobody has run it in public, I can't run it here, and I would expect Spotlight's `mdfind -name` to land in the tens to hundreds of milliseconds rather than a minute. That would still be a large win for fsearch. It would not be four orders of magnitude.
The headline compares a sports car to walking. The car is still nice, and the rest of this piece is about how it is built.
## Crawling without a stat per file
The usual way to list a tree is `readdir` for the names, then `stat` on each one for its size, type and time. On 7.6 million entries that is 7.6 million extra syscalls. macOS has a better call, `getattrlistbulk(2)`, that returns a buffer of entries with the attributes you asked for already attached. fsearch asks for exactly what the index stores (`src/walk.rs:165-170`): name, object type, modification time, BSD flags (for the Finder's hidden bit), the mount status of directories, and the data length of files. One syscall fills a 256 KB buffer with hundreds of entries.
Directories fan out over a rayon pool of 8 threads (`SCAN_THREADS` in `src/engine.rs:25`, chosen because the kernel side stops scaling past that). Each child is opened with `openat()` against its parent's descriptor, so no path string is ever rebuilt during the crawl. Mount points are flagged and not crossed; firmlinks are, which is how `/Users` on the data volume shows up under `/` exactly once (`src/walk.rs:1-6`).
Two small things in here show someone who has been bitten by macOS. `main.rs:81-84` and `engine.rs:110-118` call `setiopolicy_np` with `IOPOL_TYPE_VFS_MATERIALIZE_DATALESS_FILES` off, so that listing an iCloud-evicted folder fails fast instead of silently downloading it. And without Full Disk Access, the walker skips the consent-gated folders (Desktop, Downloads and friends) instead of opening them, because opening one pops a privacy prompt and blocks the call until somebody clicks (`src/walk.rs:16-19`). A crawler that hangs on a dialog nobody can see is a classic background-daemon bug, and he avoided it.
This is the macOS answer to what [Everything](https://www.voidtools.com/) does on Windows. Everything reads the NTFS Master File Table directly, a flat array of every file record on the volume, which is why it can index a Windows disk in seconds. macOS has no public equivalent of reading the APFS catalog wholesale, so fsearch does the next best thing: the fattest directory-listing syscall there is, in parallel.
## One file, laid out folder by folder
The whole name index is one blob, written to `index.bin` and read back with `mmap`. The format is sixteen flat arrays, each a section of the file (`src/index.rs:22-41`). There are no pointers, no tree nodes and no hash table on disk.
The layout trick is in the module comment, `src/index.rs:3-7`:
```rust
//! Layout trick: entries are emitted one directory *block* at a time, blocks
//! in depth-first order. So every directory's children are contiguous (and
//! sorted, for path lookup), and every directory's whole subtree is the single
//! range `dir_start..dir_end`. Scoping a search to a folder is a range bound,
//! not a filter.
```
Pick a folder below and watch the range. The green rows are the folder's own children, one sorted block, which is what lets `lookup()` resolve a path with a binary search per component (`src/index.rs:183-200`). The blue rows are everything beneath it.
Because a folder's block is emitted and then its child folders' blocks are pushed on a stack before any sibling's, everything under a folder ends up between two numbers. `in:~/Developer` becomes "scan entries 16 to 32" in the toy and "scan this slice" on the real disk. There is no per-entry path check. `Searcher::scope_range` in `src/query.rs:670-676` is four lines: look the folder up, read `dir_start` and `dir_end`, done.
The second trick is interning. On Noah's disk, 7.5 million entries share about 2 million distinct names (`src/index.rs:9-11`): every `README.md`, every `index.js` in every `node_modules`, every `Info.plist` in every app bundle. Each distinct name is stored once, with a precomputed 64-bit mask, and each entry holds a 4-byte name id. The query engine scores names, not entries, so `index.js` is scored once even if it appears 40,000 times.
### What an entry costs
The section sizes are in `section_lens` (`src/index.rs:449-451`), so the memory per file can be read straight off the code:
| Per | Bytes | What |
|---|---|---|
| entry | 21 | name id 4, kind and flags 1, parent folder 4, size 4, mtime 4, slot in the name-to-entries list 4 |
| folder | 21 | entry index, block start, block length, subtree end, parent, all 4 bytes, plus a 1-byte location prior |
| distinct name | 16 + its bytes | mask 8, offset 4, entries-list offset 4 |
Size fits in 4 bytes by going lossy above 2 GiB (`src/index.rs:453-460`): exact below, 2 MiB granularity above, which is fine for a `size:>1gb` filter.
To see what that comes to on a real tree I listed `/usr` on this Linux box: 189,110 entries, 20,155 folders, 99,825 distinct names averaging 15 bytes. The formula gives about 7.5 MB, around 40 bytes per entry all-in. Noah's disk interns harder (2 million names for 7.5 million entries, against roughly half on `/usr`), and the old README reports "280 MB names" on disk for it, which works out to about 37 bytes per entry.
The daemon's reported memory is a different number: 30 to 135 MB in the README, 50 MB on the benchmark card. The difference is not a contradiction. After a build, `src/engine.rs:492-493` re-maps the index from the saved file "so the index is clean, evictable page cache rather than anonymous memory." macOS's `footprint` tool, which is what the benchmark script calls (`demo/vs_fff.py:19-22`), charges a process for memory it has dirtied, not for clean pages mapped from a file. So the 280 MB index is in RAM when you search, but it shows up as file cache, and the kernel can drop it under pressure and fault it back in. That is a legitimate design and the right one for a daemon. It also means "50 MB" and "358 MB" in the fff comparison below are not the same kind of number.
## The name search has no index
I expected a trigram index for names. [plocate](https://plocate.sesse.net/) uses one over whole paths, and fsearch already has one for file contents. Instead, the name search is a brute-force pass over every distinct name, made cheap by a filter that costs one AND.
Each name's 64-bit mask records which character classes it contains: one bit per letter (case folded), one per digit, one each for `.`, `-` or `_`, space, non-ASCII and anything else. That is 41 bits (`char_bit`, `src/index.rs:509-520`). A fuzzy query token can only match a name that contains every one of its letters, so the test is whether the token's mask is a subset of the name's: `token.mask & !name.mask == 0`. For most queries that rejects most of the disk without reading a single name byte.
The spare high 23 bits hold a hash of the first letter of the name and of each space-separated word in it (`name_mask`, `src/index.rs:496-506`). That is for typos, and it lets the whole test stay branch-free (`src/query.rs:30-39`):
```rust
/// Can a name with mask `m` (`index::name_mask`) match? Cleanly it has
/// every char class; with a typo, a word in it starts with this token's
/// first letter and at most one `loose` class is missing. Branchless, so
/// the scan over every name stays vectorized.
#[inline(always)]
fn fits(&self, m: u64) -> bool {
let miss = self.mask & !m;
(miss == 0) | ((((miss & !self.loose) | (miss & miss.wrapping_sub(1))) == 0) & (m & self.start != 0))
}
```
Read it as two cases OR'd together. Either nothing is missing. Or exactly one class is missing (`miss & (miss - 1) == 0` is the power-of-two test), it is not the first letter's class (`loose` excludes it), and some word in the name starts with the query's first letter. Only names that pass go to the real scorer, an fzf-v1-style matcher (`src/query.rs:405-471`) that finds the leftmost-ending subsequence, shrinks it from the right, and adds bonuses for word boundaries, camelCase and consecutive runs, plus a big bonus when the query is the whole name or its stem.
I wanted to know how much the mask actually rejects on a real tree, so I ported `char_bit`, `name_mask` and `fits` to C and ran them over the 99,825 distinct names from `/usr`. For `json` 0.78% of names survive the mask; `zlib` 1.21%; `config` 2.94%; `python` 4.78%; `readme` 5.94%; `main` 8.00%. A one-letter query is the worst case, and `x` lets 17.00% through. The mask pass ran at about 1.5 ns per name on one core of a busy shared machine, against about 57 ns per name for a naive subsequence check over every name. At 2 million names that is around 3 ms on one thread for the mask, split across the M4 Max's cores, which is consistent with the 1.3 ms median the README reports.
After the names are scored, the query has to get back to entries, and there are two paths (`src/query.rs:686-701`). If the matching names cover at most 60,000 entries (`SELECTIVE`, line 660), fsearch walks a name-to-entries list, a second CSR-style array in the index, and touches only those entries. Otherwise it does one sequential pass over every entry in scope, looking each one's name id up in the scored table. Folder tokens (`dev main` meaning "a `main` somewhere under something matching `dev`") are resolved with a per-folder memo folded down the tree in parallel.
One more thing makes typing fast. The scored name table is cached, and when the new query only narrows the last one (`mai` becoming `main`), the scorer revisits only the names the previous query matched (`NameKey::narrows`, `src/query.rs:1053-1070`). With one exception that shows the author thought about it: "Gaining a typo widens the match: score afresh." A four-letter token takes no typos, and a five-letter one does, so `mian` to `mianr` cannot reuse the narrower set.
Try it on the toy disk. Each lane runs the same query through a different structure. `pyhton` and `wllpaper` show why the trigram lane is the wrong tool for this job: a typo or a fuzzy gap leaves no contiguous three-letter run to look up, so the index never proposes the right file. The sorted array is fast and almost useless, since binary search can only answer a prefix.
The toy is too small for the costs to mean much: it has 41 entries and 38 distinct names, so interning saves almost nothing, and a one-letter query like `a` lets so many names through the mask that the fsearch lane costs more than the plain scan. The shape is what carries over. The mask pass is a linear scan, but over the smallest thing that can answer the question, with the cheapest possible test first. Trigram indexes win when the query is a literal substring and the corpus is huge; fsearch wants fuzzy, typo-tolerant matching over a few million short strings, and for that a vectorised scan is simpler and fast enough.
### Typos at word starts only
Words of five or more letters forgive one typo: a wrong letter, an extra one, a missing one, or two letters swapped (`one_edit_prefix`, `src/query.rs:533-555`). Digits are never edited, because `hat_18` and `hat_98` are different files. The typo has to sit inside a word that starts with the query's first letter, and the comment at `src/query.rs:505-510` gives the reason:
```rust
/// ... Other word starts (`_`, `-`, camelCase) would cost
/// a scan of every name per query, ~10x the price.
```
That is a deliberate trade, and the first letter is the price: `mian.rs` finds `main.rs`, `pyhton` finds `python3`, but `ython` with a dropped `p` finds nothing. The benchmark script knows this, which matters in a moment.
## Staying current: diff a folder, never trust an event
The index is immutable once written. Changes go in a `Live` layer on top (`src/live.rs:1-7`): a bitset of base entries that are gone, plus an overlay map of entries added since. Every search scans the overlay too, at about 1 ms per 100,000 entries, so once 50,000 changes pile up (or every 12 hours), the overlay is folded into a new base: about 1 s of CPU and a 280 MB write (`src/engine.rs:19-24`).
Changes come from FSEvents, watching `/` at directory granularity with a 0.1 s latency (`src/fsevents.rs:84-86`, `src/engine.rs:308`). The handling is the part I like most. An event never says what changed, only which folder. fsearch lists that one folder again and diffs the listing against what it holds. Because the diff is idempotent, duplicate events, events replayed from history after a restart, and events racing a compaction are all harmless. That is how a new file shows up in about 0.1 s.
Restart is cheap for the same reason. The index header stores the last FSEvents id it applied, and FSEvents can replay history from an id, so a restart reloads the mmap'd file in milliseconds and replays only what changed while it was down. If the history is gone (FSEvents drops it, or the gap is too long), it does not recrawl. Adding, removing or renaming an entry bumps its folder's mtime, so one `lstat` per folder, in parallel, finds the folders to relist (`src/live.rs:320-324`). The old README timed that recovery at 8 to 13 seconds instead of a full crawl.
## Contents: here is the trigram index
File contents do get a trigram index, built the way Russ Cox described for Google Code Search, and the same idea our [tgrep teardown](/articles/tgrep) covers in depth. Every text file under your home folder is broken into case-folded three-byte runs; each run maps to the list of documents that contain it. A query becomes an AND/OR tree of trigrams. `regex-syntax` parses a regex into its HIR and the planner (`src/content.rs:1102-1209`) works out which literal strings every match must contain. The posting lists are intersected, and the surviving candidates are read fresh from disk and matched for real (`src/content.rs:1-8`), so results are never stale even when the index is a couple of seconds behind.
The storage is careful. Segments are immutable mmap'd files; a posting list is delta varints, or a bitset over the segment's documents once more than one document in 8 contains the trigram (`src/content.rs:33-35`, `:559-574`). Small segments merge in tiers of 8. Files are debounced per folder: indexed 2 s after the folder goes quiet, or 5 minutes after the first change if it never does, so a log written every second costs one reindex per 5 minutes (`src/engine.rs:398-401`). `sym:` is a nice extra: identifiers that follow a declaring keyword (`fn`, `def`, `class`, `struct` and about twenty-five more) are hashed into the same key table above the 24-bit trigram space, so "where is `apply_dir` defined" is a single posting list (`src/content.rs:287-325`).
The scope is narrower than "whole disk", and that is a reasonable choice that should be said out loud. Only files under `$HOME` are content-indexed. A file over 1 MiB (`MAX_FILE`, `src/content.rs:27`) is skipped, as is anything whose extension is not on a list of about 130 text types, anything with a NUL byte in its first 8 KB, and anything under `node_modules`, `.git`, `target`, `build`, `dist`, `vendor`, `Library`, the caches and about forty other names (`src/content.rs:37-72`). Outside the indexed area, `grep:` with `in:` picks files from the name index and reads them, which is slower but correct.
## Against fff, read closely
The repo's real comparison is with [fff](https://github.com/dmtrKovalenko/fff), Dmitriy Kovalenko's file finder: it began as a Neovim plugin, is now an MIT library and MCP server that powers file search in opencode and others, with typo-tolerant path and content search, frecency ranking and a background watcher. Someone in the first thread said "just use fff", and the benchmark was the reply. Unlike the fd card, this one has a script, `demo/vs_fff.py`, and its output is committed.
The method is decent. Both engines get the same 300 target names, picked at random from files fd also sees, each unique in the tree, then four typo variants of each, 1,500 queries in all; the engines alternate going first; content search uses 67 patterns. fsearch is even handicapped: it is timed through its Unix socket with JSON on both sides (`vs_fff.py:89-95`), while fff is called in-process through its Python binding. The name-search row, 1.05 ms against 13.8 ms at the median, I believe as stated. On the Linux kernel tree (95,939 files) the same script gives 1.15 ms against 1.04 ms, which the README honestly calls a tie.
Three rows need context.
The typo row tests the kind of typo fsearch handles. The generator's docstring, `vs_fff.py:46`: "One typo on a letter, never the first char (fsearch needs that one)." That is disclosed, and it is fair to test the common case, but a typo in the first letter would score zero for fsearch by design. The 98% against 88% is "typos after the first letter".
"Ready after launch" compares two different things. For fsearch it is the time from a killed daemon to the first answer, with a saved index already on disk: load the mmap, answer. For fff it is the time to scan the folder from nothing, 2.5 s, and 12.8 s until its content cache is warm. fsearch's equivalent would be its first crawl, about 20 s for the whole disk. Both numbers are true; they measure different events.
The memory row compares footprints, and as covered above, fsearch's index lives in clean file-backed pages that `footprint` does not count, while fff holds its index in anonymous memory. "7x less" is real in the sense that matters under memory pressure (fsearch's pages can be dropped and re-read), and not in the sense of bytes resident while you search.
And one honest disclosure from the README itself: fff finds about 9% more files with content matches on Chromium (353,276 against 323,688), because fsearch skips `build/`, `vendor/` and some file types. Faster partly because it reads less.
## Where it sits
| | How it learns the disk | Name matching | Stays current | Contents |
|---|---|---|---|---|
| fsearch | parallel `getattrlistbulk` crawl, once | mask filter, then fuzzy scan of distinct names, one typo | FSEvents, relist and diff the folder | trigram index under `$HOME` |
| Everything | reads the NTFS MFT | substring, wildcards, regex | NTFS USN change journal | not indexed by default; scans on demand |
| plocate | `updatedb`, a periodic full crawl | substring over paths, via trigrams | not live; as fresh as the last `updatedb` | none |
| mlocate | `updatedb` | linear scan of the whole database | not live | none |
| fd | none, walks every time | regex or glob | always current, by construction | none |
| fzf | none, filters whatever you pipe in | fuzzy scoring | n/a | none |
| fff | per-folder scan in a long-running process | typo-tolerant fuzzy, frecency | background watcher | in-memory content index |
| Spotlight (Finder, `mdfind`) | `mds` importers | names, metadata and contents | the same kernel change stream | yes, with importers |
The closest relative is Everything: same idea of a name index that is effectively free to query, built from the filesystem's own bulk metadata and kept live from the kernel's change stream. fsearch adds fuzzy and typo matching that Everything does not do by default, and a content index. It is also a fresh take on something people have built many times, which a few repliers pointed out with less warmth than they could have.
## What I'd take from it
If you build search for a few million short strings, the main lesson is the order of operations. Intern first so you score distinct values. Put the cheapest possible test in front of the expensive one, and make it a bitmask so it vectorises. Reach for an inverted index only when the query is a literal and the corpus is large, which is file contents, not file names. The layout trick, emitting blocks depth-first so a subtree is a range, is worth stealing for anything tree-shaped you need to scope.
On the claim: "17,000x faster than Finder" should read "about 17,700x faster than fd on a Mac whose security agents tax every directory open". fsearch's first-crawl time on that Mac is the honest bound on what an unindexed tool can do there, and against fff the honest summary is "about 13x faster on name search in a big tree, a tie in a small one".
Would I use it? On a Mac, as a launcher backend or an agent tool, yes; its JSON-lines socket and the crate API make it easy to wire in, and the owner/follower design (the first process owns the index files, others follow and take over when it exits) is thoughtful for that. On Linux it needs a port: fanotify or inotify instead of FSEvents, `getdents64` and `statx` instead of `getattrlistbulk`. The index and query code would carry over almost untouched.
## October 10: seven times faster than itself
Two days after the launch Noah posted again: "I made fsearch 7x faster. Find any file, in microseconds." The link goes to the same repository, which by then had 110 commits on top of the `af9476d` I read: 103 of them his, the rest from three outside contributors, +5,775 / −1,350 lines, almost all of it in `query.rs` and `content.rs`.
The first thing I wanted to know was what the 7x is measured against, since the last headline number was measured against fd. This time it is fsearch. The README's table compares the current build with commit `76d612f`, the October 9 merge that came seven commits after the one this article read. Its search code differs from `af9476d` only by a `type:app` fix for symlinked apps and some formatting. Same M4 Max, the same 8.3M files, medians, and two words that the launch card never had: "Same results."
This is a better kind of number than the launch card's, and the repository now ships tools to make one. `examples/rig.rs` samples a fixed query set from a frozen copy of an index (sixty unique names of 6 to 32 letters, a typo of each, common short words, folder-plus-name pairs, twenty filter queries, typing runs, and content searches), times them in process, and hashes every answer. `demo/abba.py` runs two builds in A B B A order so that a busy machine's drift hits both equally. `examples/e2e.rs` does the same from outside the daemon, through its socket or `fsearch stdio`. Most of the 110 commit messages paste their own A/B table and end with "0 queries with different results". The run behind the README table is the one thing that's missing. There is no corpus, no output and no note of which harness produced it, so I can follow the 7.7x through the commit messages but I can't reproduce it.
Read plainly, the rows say: name search went from 1.0 to 0.13 ms, typing a whole filename from 23 to 3.0 ms, content search from 14 to 2.3 ms, and the CLI from launch to answer from 5.5 to 3.3 ms. The "microseconds" are the 130 µs inside the daemon. Typed into a shell, a search still costs about 3 ms, almost all of it launching a process. The side-by-side in the same video uses the Chromium tree and shows a smaller gap per keystroke, 0.23 against 0.48 ms at the median.
### Where the 7x came from
I expected one trick. Instead there are dozens of commits, each with its own measured ratio. For names, three of them carry most of the gain.
The first turns the mask into an index. At `af9476d` each distinct name carried one 64-bit mask, and a query tested every mask in turn. Commit `2572bbd` turns that table on its side. For each of the 41 character classes, the index now stores a bitmap over every distinct name, one for names with that class in their first half and one for their second half. A query reads 64 names per machine word, rarest class first, and stops as soon as a word goes to zero. The two halves add a test the old mask could not express. A fuzzy match keeps the query's letters in order, so some prefix of the query has to fit the first half of the name and the rest has to fit the second. A later bitmap marks the classes a name contains twice, so `readme`, with its two e's, skips every name that has only one. The commit message says the order test "rejects ~93% of the names the old char-class mask let through", and puts name-scoring CPU at 6 ms before and 0.3-0.7 ms after.
I ported the new filter (`TokenBits::words` in `src/query.rs`, typo path included) to C next to my old port of `fits`, and ran both over the same 99,827 distinct names from `/usr`. My old port reproduces the earlier numbers exactly, which is a good sign the new one is faithful.
| Query | Old mask lets through | New bitmaps let through |
|---|---:|---:|
| `json` | 0.78% | 0.54% |
| `zlib` | 1.21% | 0.18% |
| `config` | 2.94% | 1.65% |
| `python` | 4.78% | 4.15% |
| `readme` | 5.94% | 1.98% |
| `main` | 8.00% | 4.67% |
| `x` | 17.00% | 17.00% |
On this tree the new filter removes between none and 85% of what the old one let through, depending on the query, not 93%. His figure comes from his own query set of long, unique filenames, which is where an order test bites hardest. A one-letter query gains nothing by construction. The speed per name changes more than the counts do. The old filter took 1.3 to 1.6 ns per name on one core of this busy machine, and the bit-sliced one takes 0.08 to 0.44 ns, because a single AND now covers 64 names.
The second change stops broad queries from visiting everything. Commits `69509bf` and `e1c758d` give each distinct name four bytes (`NameInfo`) that bound how well any entry with that name could score, without reading the name. Names are visited best bound first, in batches, and the visit stops once nothing left can beat the 50th hit. A query like `a` or `add` used to walk all 8.3 million entries; now it scores a few dozen names. Another commit, `a21af25`, keeps per-first-letter lists, so a 1- to 3-byte token never touches the bitmaps at all.
The third is one I would not have thought of. Commit `1a14bb8` notes that after about 20 ms of idle, macOS clocks the cores down, and the next search runs 3 to 6 times slower while they ramp back up. Every keystroke of someone typing pays that. So after it answers a client that is still connected, the daemon now spins one thread for 250 ms. Keystrokes 120 ms apart went from 1.442 to 0.525 ms each. The commit is just as specific about the bill: "+20.8 s daemon CPU over a 26 s session typed at 120 ms gaps". In other words, one core stays busy for as long as you type. For a launcher I think that is a fair trade, but on battery it is a real cost, and it is easy to miss when the release only says "faster".
The rest is smaller and well documented: NEON compares in the fuzzy scorer, JSON written straight from the hits (20 to 30 µs), `target-cpu=native` (0.92x) and a hoisted vector load (0.85x), both from an outside contributor, and `pgo.sh`, a profile-guided build trained on your own index that makes name searches 6 to 37% faster. The README's build line is plain `cargo build --release`, and the table doesn't say whether its "now" column used the PGO build.
Content search got per-file bloom filters over 5- and 7-grams, so a search can skip files that contain the right trigrams but not the text. That is where "slowest 10% inside files: 38 to 2.3 ms" comes from, and it is why the Chromium index on disk grew from 0.32 to 0.76 GB. Identical files are now indexed once.
### What it changes above
The heading "The name search has no index" is out of date. There is still no trigram index for names; trigrams are still for contents only. But per-class bitmaps over every distinct name are an index in the plain sense: a precomputed structure that answers "which names could match" without visiting each name. It is closer to a bit-sliced signature file than to an inverted index of n-grams. The mask section, the C numbers in it and the race widget all describe `af9476d`.
Memory per entry is unchanged at 21 bytes. Per distinct name it about doubled. The 8-byte mask gave way to 148 bitmap bits (18.5 bytes), plus 4 bytes of `NameInfo`, a 1-byte location prior and a 1-byte extension slot, so with the two 4-byte offsets that comes to 32.5 bytes plus the name's own bytes, up from 16. On `/usr` that moves my estimate from about 7.5 MB to 9.1 MB, or from about 40 to 48 bytes per entry. His own commit puts the step from mask to bitmaps at 17.7 MB to 29.7 MB on his disk.
The 17,000x is gone from the README, and nothing has replaced it. The new claim compares fsearch with itself, on hashed answers, with a harness in the repository, and that is the comparison I asked for.
The fff comparison had a short second life. Commit `ec25ffa` reran `demo/vs_fff.py`, which was unchanged: on Chromium, 0.21 ms against 15.4 ms by name; on the Linux kernel, 0.16 against 1.8 ms. The tie I described above had become an 11x win. Seven commits later, `ffcb37d` ("Remove the fff comparison") deleted the table, the script, both JSON files and the video, with no reason given. One detail from the rerun is worth keeping. fff's own median on the Linux kernel went from 1.04 to 1.78 ms between the two runs, a 70% swing on the side that none of fsearch's commits touched. That is how far a single run of that script can move. The "Against fff" section above cites files that are no longer at the head of the repository; they are still in its history at `af9476d`.
## October 13: 0.2, where speed stopped being the point
Two days later came a version number. "FSearch 0.2", Noah posted on October 12, with five lines under it: 150x faster to grep a file you just edited, a 74% smaller index ("for me 1.5g -> 388mb"), 35% more files covered, 65% less daemon memory on Chromium, and 32% less peak memory while indexing. Someone in the replies asked when it would hit sub-picosecond latency, and his answer explains the whole release: "Once in nanosecond I see no point in speed being faster. This version actually regresses by .4x in some areas when it comes to speed. Primary focus is better system impact and ability."
I liked that before I had read a line of it. After two rounds of headline multipliers, a release that says what it gave up is easier to trust.
The repository has tags now. `v0.2.0` is a single commit, `e96ebeb`, that adds 9,436 lines and removes 1,142 across 24 files, including four new modules (`alloc.rs`, `frecency.rs`, `git.rs` and a 1,338-line `mcp.rs`). The README's "before" column is commit `b88f4e9`, which is the parent of `ffcb37d`, the commit the October 11 update read, so for once the baseline is code this article has already been through. `v0.2.1` followed the same afternoon with 16 small fixes credited to @domfahey's issues, and a few outside pull requests, one of which (Leonhard Breuer's, #25) frees an FSEvents context the old code leaked on every stream restart. The numbers below all come from 0.2.0's own boards, so that leak fix is not in them.
One more thing from the replies. Asked to rerun the fff benchmark, Noah said he'd talked to Dmitriy, fff's author, and that comparing the two "is not the best thing... My project is just meant to replace finder nothing more!" That explains the commit that deleted the comparison, which I couldn't explain on the 11th.
### 150x: the edit you just saved
The demo appends `fsdemosamq9s` to `init/main.c` in the Linux tree and greps for it every few milliseconds. 0.1 finds it after 2.06 s, 0.2 after 13.8 ms, which is 149x.
The 2.06 s is no accident. The content worker debounces each folder until it has been quiet for two seconds (`CONTENT_QUIET`, `src/engine.rs:26`), and that constant is still 2 s in 0.2. I expected the fix to shorten that wait. Instead the index still waits, and grep stops waiting for it.
When a batch of FSEvents arrives, the worker now does one extra thing before it files the folders away for later. It asks the name index which text files those folders should hold right now, compares each one's size and mtime with what the content index holds, and puts the ones that differ on a list (`Dirty::mark`, `src/content.rs:2832-2880`). Every grep takes the files on that list that pass the query's filters, newest first, and reads them before it touches a posting list (`search_with`, `src/content.rs:2733`). The candidates that come out of the index then skip any path already read. When the two-second sync lands, the folder's entry is cleared. A folder with more than 4,096 changed files (`DIRTY_MAX`) only gets the first 4,096 on the list; the rest wait for the sync, which is the right bound for a `git checkout` that rewrites half a repo.
This works because of a decision from the very first version. Matches were always read fresh from disk, and the index only picks candidates, so reading a few extra files directly costs no correctness at all. The only thing that was ever stale was the candidate list, and the dirty list patches exactly that gap.
What's left is FSEvents itself. The stream's latency dropped from 0.1 s to 10 ms (`src/engine.rs:550-553`), and the comment says why: "a change shows in ~12 ms (fseventsd's own delay); at 0.1 s, one made within 0.1 s of another (save then rename) took ~100 ms". 10 ms of latency plus fseventsd's own delay is about the 13.8 ms on screen. The same change is why the README's "a rename or delete visible" row went from 45 and 47 ms to 18 and 15.
The README and the closing card print a different number for the same row, 2.1 s to 1.2 ms (1.3 ms in the README), labelled "in-process". I couldn't work out what it measures. The rig in the repo, `examples/fresh.rs`, starts the clock at the write and polls every 5 ms, and the code can't see a write before FSEvents reports it, which takes longer than 1.2 ms on its own. So I'd quote the demo's 13.8 ms and the 150x, which the code explains, and leave the 1,600x the table implies alone.
### 74% smaller, and why his number beats the board's
The bench board says something more modest than the post. Index on disk went from 503 to 309 MB with the Linux tree in home, and from 893 to 600 MB with Chromium: 39% and 33% smaller. Those totals are the whole data directory, names for the whole disk plus the content index for the tree, which is why they don't line up with the 0.76 GB Chromium content index in the October 10 table. Noah's own 1.5 GB to 388 MB is 74% (388 out of 1,500 leaves 26%). Four changes carry it, and I'd guess the fourth explains the gap.
The first is the filter added two days earlier. On October 10 every indexed file got two bloom filters, one over its 5-byte substrings and one over its 7-byte substrings, which is what grew the Chromium index from 0.32 to 0.76 GB. In 0.2 the 7-gram filter is gone, and the comment that replaced it gives the accounting (`src/content.rs:666-671`): it "read 0.66x the files on rare greps (0.82x their time) but took 30% of the index (0.87 bits per content byte)". Each file keeps one filter, 5-grams at 3 bits a gram, which the same file says still lets a missing gram through 24% of the time. Grep's first page got a little slower for it, 0.29 to 0.33 ms on Linux and 0.48 to 0.65 ms on Chromium, which is the regression he mentioned. I'd make the same trade.
The second is the posting lists. They were delta varints, a byte or more per document id. They are now binary interpolative code in blocks of 128 with a skip table (`ic_put`, `src/content.rs:4081`): encode the middle id in as few bits as its bounds allow, then recurse into each half. Files in one folder get neighbouring ids, so a run of consecutive ids costs, in the comment's words, "nothing". Paths in the doc table are front-coded in groups of 16 (`PATHS`, `src/content.rs:50`), so each path stores only what differs from the one before it, which in a source tree is usually the file name.
The third is the name index, which is now bit-packed and read in place (`src/index.rs:14-16`). An entry's name id takes as many bits as there are distinct names, 21 for two million, instead of 32. Its kind takes 4 bits instead of a byte. Its parent is no longer a 4-byte folder id: since each folder's children sit in one contiguous block, a bit per entry marking where blocks start, a rank count every 64 entries and one folder id per block are enough. Sizes and mtimes are stored in runs of 64 as a minimum plus each value's excess over it, which pays off because neighbours in a block tend to be close in both. Names with a long hex run or a UUID in them (every git object, every cache key) are stored two digits to a byte. On a disk like his, 8.3 million entries and about two million names, the fixed-width parts come to about 6.2 bytes an entry, plus a folder id per block, where the same fields took 13. Sizes and mtimes depend on the data, so I can't give a single per-entry figure the way I could for 0.1.
The fourth is cleanup. 0.1 rewrote a content segment only when more than half its documents were dead, deleted or replaced by a newer copy (`merge_plan` at `b88f4e9`). A segment that was 49% garbage stayed that way. 0.2 keeps the bytes of dead files under a sixteenth of the whole index and rewrites whichever segment has the largest dead share first (`DEAD`, `src/content.rs:47`, and `merge_plan` at line 2384). The bench board builds both versions from scratch, so neither has any dead weight. Noah's own index had presumably been running since launch, under a home where he was editing fsearch itself all week, and dead files are my guess for why his saving is twice the board's. There's a new rig for it, `examples/churn.rs`, which simulates weeks of edits, creates, deletes, growing log files and a weekly checkout. I can't check this guess without his data directory.
### "35% more files covered" is 35% more text
This is the one line in the post I'd correct. The board's own words are "holding 32% / 35% more text". The row that counts files is "files grep can search (rg's own set)", and it went from 96% to 99.9% on Linux and from 92% to 99.8% on Chromium, about 4% and 8% more files. More text and more files go together here, since the text comes from files 0.1 skipped, but they are different numbers.
The coverage change itself is real and sensible. Outside a git repo the old rules still apply: an extension list and a 1 MiB cap. Inside a repo, fsearch now reads what ripgrep would. Files up to 10 MB (`MAX_REPO_FILE`, `src/content.rs:40`, picked to match `rg --max-filesize 10M` and fff), whatever `.gitignore` and `.ignore` don't exclude, with text decided by sniffing the bytes rather than the extension. `target`, `build`, `dist` and the cache names used to be skipped by name everywhere. Now they're skipped only when the folder carries a marker, `CACHEDIR.TAG`, `CMakeCache.txt` or `build.ninja` (`MARKED_DIRS`, `src/content.rs:77`), because, as the comment puts it, "Linux's drivers/target is source". Lockfiles, JSON of 100 KB and up, minified bundles and linked git worktrees stay out. A reply asked whether a grep in a linked worktree says that it isn't indexed. From the code, the worktree's files are left out of the index and `in:` on the worktree falls back to reading files directly, which gives a correct answer, slowly; I didn't find a message that tells you.
### Memory a daemon gives back
The 65% is Chromium's daemon going from 100 to 35 MB. The same row for Linux went from 19 to 21 MB, slightly up, which tells you what the fix is. The process never held much data. It held memory it had already freed.
The new `src/main.rs:70-84` has the story. macOS's malloc "keeps freed small blocks dirty and its pressure relief does nothing, so after the first run or a compaction the daemon held 150-290 MB it no longer used, until restarted." Malloc has a space-efficient mode that hands those blocks back, but it is read only at launch, so `fsearch serve` re-executes itself with `MallocSpaceEfficient=1` set. It idles at 5 to 15 MB on his machine, for searches about 8% slower. Big blocks, 1 MB and up, now come straight from `mmap` and go straight back, because malloc kept those mapped and dirty too, "which left the daemon at ~1 GB footprint after a build while ~2 MB was live" (`src/alloc.rs:1-11`). Space-efficient mode also turns off malloc's per-thread caches, which cost searches about 10%, so the search threads keep small free lists of their own and drain them back a minute after searching stops.
Chromium's index build churns through far more memory than Linux's, so it had far more freed memory to give back, which is why its row fell and Linux's didn't.
Peak memory while indexing fell from 1.13 to 0.77 GB on Linux and from 1.37 to 0.94 GB on Chromium, 32% and 31%, which is the post's figure. The video's own run shows 710 to 291 MB, 59%. The main reason is in `src/engine.rs:874-877`. The content build used to keep two 64 MB batches in flight, so one batch's single-threaded tail overlapped the next batch's reads. Now it keeps one: "3.07 s instead of 3.33, but a first-run peak of 616 MB instead of 375." The name index's build also writes its blob section by section, freeing each source array once it has been copied (`src/index.rs:826-828`), and the smaller formats above shrink everything the build holds.
### What else 0.2 changed
The rest isn't in the post but it's on the card. Typos changed the most, and they make a section above out of date. At `af9476d` a typo had to sit in a word that started with the query's first letter. 0.2 runs the old search first, and if it doesn't find a good enough match, runs it again "deep" (`search_form`, `src/query.rs:2079-2085`), allowing a wrong, extra, missing or swapped first letter and two edits in words of eight letters or more. On his Linux bench set, the meant file for names with a wrong first letter came first 24% of the time before and 98% after, and names with two typos went from 11% to 74%. The second pass is why name search slowed from 0.045 to 0.054 ms on Linux and from 0.10 to 0.12 ms on Chromium, and why the typo sets' median doubled from 0.05 to 0.10 ms. My complaint that `ython` finds nothing is answered.
A first run also no longer blocks a search inside a folder. Until the whole disk is listed, a query with `in:` gets an index of just that folder, built on the spot with 16 threads (`with_names`, `src/engine.rs:492`), and that folder's contents are indexed first. 7.8 s to 0.18 s on Linux, 1.2 s on Chromium. The rest is new surface: globs, `git:` filters, frecency and nearby-file boosts, and `fsearch mcp`, an MCP server with `find_files`, `grep` and `multi_grep` for coding agents.
The post did undersell one thing. A daemon that sits in the background on every Mac it's installed on should be judged on what it costs when you aren't searching, and that is what this release went after. The multipliers in the post are mostly right, the 35% describes the wrong quantity, and the regressions are named in the README table rather than hidden. I trust this release more than either earlier headline.
## How I checked
I shallow-cloned `noahdunnagan/fsearch` at commit `af9476d` (October 8), then fetched the full history to read the earlier README at `f43261b`, and read every file under `src/` and `demo/`. Line references are to `af9476d`. The fd and grep -r figures come from the final frame of the launch video, which I pulled with ffmpeg; the repo has no script for them. The fff numbers are from `demo/vs_fff_chromium.json` and `demo/vs_fff_linux.json`, and the method from `demo/vs_fff.py`. The thread quotes are from the fxtwitter mirror of posts 2107993727809855570 and 2108257494841827721.
fsearch does not build on Linux, so I did not run it. The per-entry byte counts are read from `section_lens`; the `/usr` listing (189,110 entries) came from `find /usr -xdev`; the mask rejection rates and the 1.5 ns per name come from a single-threaded C port of `char_bit`, `name_mask` and `Token::fits` timed over 50 repetitions on a shared 16-core machine under load, so treat the timings as rough. The widgets port the same functions plus `one_edit_prefix` and `Index::build`'s ordering to TypeScript; their ranking is simplified. I could not measure Finder, Spotlight or `mdfind` here, so the Spotlight estimate above is a guess and labelled as one.
For the October 11 update I cloned the repository again at `ffcb37d` (October 10, 23:00 EDT), diffed it against `af9476d` and `76d612f`, and read the commit messages of all 110 commits in between along with the new `examples/rig.rs`, `examples/e2e.rs`, `demo/abba.py` and `pgo.sh`. The October 10 post (2108960053915267096) and its replies came through the fxtwitter mirror. Its short link, `nd.mt/g/fsearch`, redirects to the same GitHub repository. The two figures are frames from the post's video. The bitmap filter's survival rates and per-name times come from a C port of `name_bitmaps`, `doubled` and `TokenBits::words`, typo path included, run alongside the old port over `find /usr -xdev` (189,124 entries, 99,827 distinct names this time), 50 repetitions each on a loaded shared machine. The per-name byte count is read from `section_lens` at `ffcb37d`. The fff rerun figures are from `demo/vs_fff_chromium.json` and `demo/vs_fff_linux.json` at `ec25ffa`. I still could not run fsearch itself.
For the October 13 update I cloned the repository with its tags, at `v0.2.1` (`88e63fd`), and diffed `v0.2.0` (`e96ebeb`) and `v0.2.1` against `b88f4e9`, the README's baseline. Line references in that section are to `v0.2.1`; the ones marked `b88f4e9` are to the old code. The post (2109675745408930191), its thread and replies came through the fxtwitter mirror. I read the video's frames once every three seconds plus the last one, extracted on another machine; the three figures in that section are frames from it. The 149x is 2.06 s over 13.8 ms; 74% is 388 MB out of 1,500; 39% and 33% are 309 over 503 and 600 over 893; the 65% is 35 over 100 MB; 32% and 31% are 0.77 over 1.13 and 0.94 over 1.37 GB. The 6.2 bytes per entry is my arithmetic from `section_lens` at 8.3 million entries and two million names. The bench board's release candidate `427be0b` is not in the public history, and I could not find what produces the README's 1.3 ms fresh-grep figure. I did not run fsearch, and the explanation of why his own index shrank more than the board's is a guess.