find took 22 seconds to list the first two million files in my Developer folder.
A new Rust tool says it answers a fuzzy name search over 8.3 million files in about a tenth of a millisecond.
That gap is not a faster loop. It is a loop that, for almost every file, never really runs.
The tool
fsearch is whole-disk file search for macOS, by Noah Dunnagan. It went public on October 8 and passed 1,900 stars within days. It is MIT licensed, written in Rust, and ships as a CLI with a small daemon you talk to over a Unix socket (or as a crate you link into an app).
It crawls the disk once with getattrlistbulk, a macOS call that returns hundreds of entries with size, type and mtime attached, so there is no stat per file. Then it follows FSEvents and re-reads only folders that changed. Names live in one memory-mapped file, and text files get a trigram index for searching inside them.
The README's speed table is the project's own: an M4 Max, 8.3 million files, medians, against its previous version. A name search sits at 0.13 ms there. I have not reproduced it.
I did not build or run fsearch. There are no release binaries yet, cargo build runs build scripts I would rather not run for a post, and the tool wants Full Disk Access and a login item to do its job. So I read the core source, then rebuilt its main trick in Node and measured it on my own files.
64 bits that say no
Every file name gets a 64-bit mask. Each of the first 41 bits stands for a class of character: one per letter (case folded), one per digit, and a few catch-alls for dot, dash or underscore, space, any non-ASCII byte, and everything else. A name's mask is the OR of its characters.
A fuzzy match needs every letter of the query to appear in the name, in order. So if the query has a letter class the name lacks, the name cannot match. That check is one AND and one compare. No string is read.
The other 23 bits hold a hash of the first letter of the name and of each space-separated word in it. Those exist for typos, which I will get to.
The index does not even test names one at a time. It turns the masks sideways: one bitmap per character class, where bit k says whether name k has that class. One 64-bit word then answers for 64 names at once. It checks the query's rarest letters first and stops as soon as a word of 64 names goes all zero.
Two more cheap tests ride along. Each name has a bitmap for the letters in its first half and one for its second half; since a fuzzy match is in order, some prefix of the query must fit the first half and the rest the second. Another bitmap marks letters a name holds twice, so dockerfile skips names with one e. And names are interned: index.rs counts 7.5 million entries sharing about 2 million names, so the work scales with names, not files.
The typo rule fits in the same 64 bits
A typo-tolerant search sounds like it should defeat all of this. If the user typed chnagelog, the right answer is not a subsequence match at all.
The trick is that one edit can cost the query at most one letter class. So a five-letter-plus word passes the prefilter if it misses no class, or if it misses exactly one class that is not its first letter, and the name has a word starting with that first letter. This is the check in src/query.rs, written without branches so the compiler can vectorize the scan:
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))
}
miss & (miss - 1) == 0 is the old bit trick for "at most one bit set". Only names that survive get the real edit check: a wrong, extra, missing or swapped letter, at the start of the name or of a space-separated word. Digits are never treated as typos, so hat_18 never finds hat_98.
I rebuilt it in Node
I ported the mask, the typo fits rule, the halves test, the doubled-letter test and the one-edit check to a 250-line Node script, then pointed it at a real file list:
find ~/Developer -type f 2>/dev/null | head -2000000 > files.txt
node bitmap.js files.txt
That is two million files, which collapse to 301,766 distinct names. Fair warning about my disk: 72% of those paths sit inside node_modules.
For each query, the script counts how many names the letter mask rules out, how many survive the halves and doubled-letter tests, and how many truly match. Then it scores every single name the slow way and checks that no real match was thrown out:
query | ruled out by letters | left after halves+doubles | real matches | lost
main | 257,843 (85.4%) | 30,381 | 15,881 | 0
readme | 265,212 (87.9%) | 22,644 | 3,129 | 0
changelog | 284,115 (94.2%) | 7,879 | 200 | 0
chnagelog | 284,115 (94.2%) | 7,850 | 69 | 0
tsconfig | 287,678 (95.3%) | 9,160 | 794 | 0
kubectl | 295,876 (98.0%) | 2,085 | 22 | 0
dockerfile | 297,733 (98.7%) | 1,409 | 5 | 0
zshrc | 298,123 (98.8%) | 2,202 | 196 | 0
The "lost" column matters most. A prefilter that is wrong once is a bug, not an optimization, and across eight queries it never dropped a real match. It may say "maybe" too often (30,381 survivors for main, about half real). It may never say "no" wrongly.
Speed, in plain JavaScript on an M1 Max, measured across two runs: scoring every name took 30 to 57 ms per query. Running the mask first and scoring only the survivors took 1.5 to 7 ms. The mask scan by itself was under 1.5 ms for all 301,766 names. Those are my toy's numbers, not fsearch's.
The short version: for a specific query like dockerfile, 98.7% of names were rejected without reading a single character of them.
What it costs
The same idea runs the content search, and that is where the bill shows. A trigram index finds files holding every three-letter slice of your pattern, but a file can hold every slice without the word. A comment in content.rs uses "different" and "reference" for "difference". So fsearch stores, per file, bloom filters of its 5- and 7-byte substrings. The README is upfront about it: the Chromium content index went from 0.32 GB to 0.76 GB, 2.4 times bigger, so that search can skip files without the text. The filters are not exact either. The source says a missing gram still slips through 24% of the time at three bits per gram.
The typo rule has an edge too. My chnagelog query found the 14 names that start with "changelog", but not .auto-changelog, because the dash is not a word start. The code says checking _, - and camelCase starts would cost a scan of every name, about ten times the price. A deliberate trade, and worth knowing.
And it is young. It is macOS only by the maintainer's choice (issue #9), with Linux living in a fork. Release builds are an open PR. Issue #16 flags two places memory may grow in a long-running daemon.
The idea worth stealing
You do not need a disk index to use this. Any search over a list (a command palette, an autocomplete, a log filter) can keep a letter mask per item and reject most of the list with one AND before the real matcher runs. Put the cheapest test first, check the rarest letters first, and prove the filter never says no to a real match. Then make it fast.
Where in your own code is an expensive check running on things a cheap one could have ruled out first?
Top comments (0)