a few days ago i saw that @itsnoahd built fsearch, a fast whole-disk search for macos written in rust. i forked it because i wanted to make it faster with cpu-specific instructions: neon on arm, avx2 and avx-512 on intel.
while i was working on the fork, i saw this tweet about tov, a new language by @richiemcilroy that claims to be "faster than rust and bun in lots of cases".
tov uses typescript syntax (plus number types like int and f64), compiles to c, and gives you one native binary.
so i changed the plan and ported the search to tov, mostly to see how far a 0.0.1 language can go. the result is tov-search.
//the problem
whole-disk search means one search box over every file and folder on your disk. you type part of a name and the matches show up while you type, including hidden files, node_modules, and the pdf you downloaded a minute ago.
windows has everything for this. mac and linux don't really have an equivalent:
- spotlight tries to guess what you want, skips most hidden folders,
node_modulesandLibrary, and results come in slowly. - find walks the whole disk on every search, which takes minutes on a full disk.
- locate reads an index, but the index is only as fresh as the last
updatedb, and it only matches exact text, so a typo returns nothing.
here's a small disk of about 2,000 files and folders, searched with each tool. it runs on its own; type something or pick a tool to try it yourself.
a real developer's mac has around 10 million files and folders. most of that is node_modules, caches and app bundles, and your own files are a small part of it.
if a search takes 100 ms per key, it feels broken. i wanted about a millisecond per keystroke, even when the query has a typo.
//three steps per keystroke
the disk is loaded once into one flat table.
10M entries only have 3.5M distinct names (think of how many README.md files you have), so the engine scores names instead of entries.
on every keystroke it drops names that are missing a letter, scores the rest, and ranks the files. you can type below or hover a dot.
- 1prefilter2,232 entries, 467 names
one bit per letter. a name missing any bit of the query is dropped without reading it. point at a dot to test that name.
querynamedropped by maskread, no matchmatch - 2score names
letters in order. 16 each, +8 at a word start, +6 in a run, minus the gap before it (simplified).
- 3rank entries
each entry gets its name's score, plus points for where it lives.
none of this is new. it's fsearch's algorithm, ported to tov without changes. the port started at about 2,000 lines and is about 3,400 now, split across 19 files.
//typescript in, c out
the whole search is written in typescript. below is one of the hot functions, which finds the first byte in a name that matches a letter, and the c that tov generates for it.
press next (or play) to compile the first line.
that's the actual output. tov type-checks the program, writes every function out like this into one c file, and passes it to clang. the c is verbose, with a temporary variable for every step and a number on every name, but it's plain c.
the first version ran on one core without vector instructions and took 30.8 ms per keystroke on my m1 pro (10 cores). that's fine for a 0.0.1 language, but too slow for a search box.
//where tov stops
most of the early speed-ups in my rust fork came from two things: vector instructions and using every core. plain tov can't do either. you can't write cpu instructions in it, and it has no threads. you write typescript and you get whatever c tov generates.
but the generated c is just a file, and clang will compile whatever is in it. so my plan was to let tov compile the program, then replace a few of its functions with c that i write myself.
//vectors: neon, avx2, avx-512
a normal loop checks one byte at a time. a vector instruction loads a whole register of bytes and compares all of them in one go. how many bytes depends on the cpu:
- neon is on every arm chip, including every apple silicon mac: 16 bytes per compare.
- avx2 is on most intel and amd chips from the last ten years: 32 bytes.
- avx-512 is on newer server chips and some desktops: 64 bytes.
the compare returns a bit mask with one bit per byte (neon uses four bits per byte). the number of zeros before the first 1 is the position of the match.
i knew vectors make loops like this faster, but i'd never measured how much they help in a real program, where most of the time might be spent somewhere else. so i wrote them to find out.
one source file covers every cpu. the compiler's vector types build to neon, sse2, avx2 or avx-512 depending on the target, and the only raw intrinsics are the few lines that turn a compare into a bit mask.
//swapping functions in
tov doesn't support any of this, so it's all done by a small python script i wrote that runs after tov.
the swap is driven by comments in the typescript.
// hook: marks a function, and // reads: and // writes: list the globals it uses.
the script reads these comments and generates a typed c header, with one struct per hook and one named field per input.
tov's version of the function then becomes a single call into a kernel, which is a short c file i write by hand:
you add two comments above a typescript function. // hook: says a c kernel will replace it, and // reads: lists the globals the kernel needs.
because the typescript body stays as the reference, there is something to check the kernel against: a shadow build runs both and compares the results, so a broken kernel gets caught before it ships.
so how much did the vectors help? on my m1 pro it went from 30.8 to 29.0 ms per keystroke, about 6%. that's less than i hoped. the byte scans got a lot faster, but they were never where most of the time went.
on 2-core ci machines the full engine takes 28 ms per keystroke with avx-512, 33 with avx2, and 47 with neon. those runs use different cpus and compilers, so they're not directly comparable.
//the big win: every core
at this point the whole engine still ran on one core of a ten-core machine, which was the bigger problem.
the injected c can use threads, though.
the par kernels move the hot loops (the prefilter, the name scoring, the folder scores and the entry pass) into c and split the names into chunks for a small thread pool.
that took it from 29.0 to 2.61 ms per keystroke, about 11× faster.
//catching bugs in the c
hand-written c is where bugs hide. an off-by-one in a kernel returns almost the right files, and nobody notices for weeks.
so there are two checks.
the oracle. every keystroke's answer has to match a saved reference exactly: same files, same scores, same order. a single wrong byte fails the run.
shadow builds. the oracle tells you that an answer is wrong, but not which kernel broke it. for that, the same script has a shadow mode: every hooked function runs twice, once as the original typescript and once as the c kernel. if the two ever disagree, the program stops and tells you which function, on which input.
below, you typed m. for each name, the engine asks findFolded where the first m is, and a shadow build asks both versions.
as long as they point at the same letter, it keeps going. press plant a bug to break the c version on one name:
the check script also plants a real bug on every run, to make sure shadow mode still catches it.
//the race
the benchmark disk is synthetic: 10,000,541 files and folders shaped like a real developer's mac, generated from a fixed seed so it's the same on every machine.
the queries are things people actually type, like readme, mian.rs and docker compose, and every query is timed one keystroke at a time.
there are 409 keystrokes in the dev trace and 371 in holdout. i never tune on holdout, so it catches overfitting.
after the kernels, my tuned rust fork was still about 3× faster. the difference came from caches and pruning, not from the language, so i ported those tricks to tov one by one: ranked name bitmaps that let the search stop early, cached matches for multi-word queries, and a cheaper walk for queries that only exclude things.
each change had to beat the previous build on dev across nine paired runs and still match the oracle. three of them didn't, so i dropped them.
the rest made tov 35% faster on dev and 46% faster on holdout (on x86 linux with avx2).
then i ran a head-to-head on the same 6-core m4 in ci, with the same keystrokes and every engine on its default settings:
on the 10M-file disk, tov-search is about 2× faster than upstream fsearch. my rust fork is still faster, but the gap is down from 3× to about 1.25×. on the linux kernel tree, tov-search, my rust fork and fsearch are roughly tied. fff is 13× slower there, but it only indexes files and crawls the tree itself, so it's a different kind of tool.
as for ranking, the exact file i was looking for came first in 18 of 31 queries with tov-search, 17 with fsearch and 14 with fff. ci runs are noisy (fsearch ranged from 1.7 to 2.3 seconds across passes), so treat these as rough numbers.
//what 0.0.1 means
tov still has real gaps.
it can't read stdin, so even reading a line needs a hand-written c hook.
there's no regex, so the re: and path: filters didn't make it into the port.
i also hit a compiler bug where a switch on a string freed the string too early. i reduced it to a short repro.
still, the approach works. most of the code stays typescript. the few places that need c get c, and that c is checked against the typescript it replaces in shadow builds and against the oracle on every keystroke. the result is close to rust, and faster than the tool i forked.
next i want to close the last 1.25×, and ship one binary that picks avx2 or neon at startup, so a native build doesn't crash on an older cpu.