Kernel Fuse

Kernel: Fuse

fuse-mojo is a drop-in faster replacement for Fuse.js fuzzy search — the same API, bit-identical results — powered by a clean-room Bitap kernel in Mojo. Package: typescript/fuse-mojo (npm install @fuse-mojo/core) · Kernel: kernels/fuse

The algorithm

Fuse.js runs the Bitap (Shift-And) bitmask dynamic program over every document for every query, in JavaScript — and re-lowercases every document on every search. fuse-mojo moves exactly that loop into a compiled kernel:

1. Index build (per instance): the JS wrapper extracts searchable strings, lowercases them once, and flattens them into a UTF-16 buffer handed to the native index. (This is why our build is ~1.4–1.7× slower than Fuse.js's — it pays for itself within the first couple of queries.)
2. Word-parallel DP: the kernel runs the Shift-And recurrence 32 text positions per 32-bit word, over the pre-lowered index.
3. Thread-parallel across documents: a small C shim (kernels/fuse/src/shim.c) fans the collection across pthreads; jobs own disjoint document ranges and results are assembled in fixed document order, so threading is deterministic.
4. Bit-compat scoring in JS: chunk combination, key weights × field-norm scoring, sort, and result formatting stay in JavaScript on both backends — only the hot DP moved.

Batch ABI: search_begin (per pattern chunk: alphabet + per-thread scratch) → search_range × threads → search_end. FFI cost is per query, not per document.

Parity proof

• The differential suite compares @fuse-mojo/core against published fuse.js 7.1.0 on seeded corpora: ~200 generated patterns (exact, typo'd, substrings, multi-token, absent, unicode, >32-code-unit chunked) across 20 option cells, asserting identical refIndex order (the reference sort is a total order over (score, idx), so ties cannot reorder), scores within 1e-9, and structurally identical match spans.
• Measured agreement on the benchmark corpus: exactly 0 — bit-identical, asserted by the gate before every timing pass. All DP arithmetic is 32-bit two's complement and all scoring IEEE-754 float64 in the reference's operation order.
• 39 tests pass native, 37 forced-fallback (2 native-only cells skip there by design).
• Unicode, honestly: the kernel operates on UTF-16 code units exactly like Fuse.js (String.length, charAt) — including astral behavior (an emoji is two units and can match as two). The suite covers accented, CJK, Cyrillic, and emoji documents/patterns, case-sensitively and not.

Autopsy: why Fuse.js is slow (measured)

V8 CPU profile (node --cpu-prof) of Fuse.js 7.1.0 searching the 100k corpus, self time by function: 48.1% search (the Bitap bitmask DP itself) + 45.2% the chunks.forEach closure driving the DP per document + 1.8% GC + 1.1% searchIn dispatch. ~94% of query CPU is the Bitap DP executed in JavaScript — a pure-interpreter loop, the factory's "10–100× available" classification. Everything else (tokenization, scoring, sort) is noise.

Measured numbers

Apple M4 Max (16 threads), macOS arm64, Node v23.10.0, fuse.js 7.1.0, Mojo 1.1.0; seeded corpora, median of 5. Reproduce: pixi run bench-fuse.

Warm (ms/query): 10k/len-8: 34.5 → 1.6 (21.8×); 100k/len-16: 1,239.5 → 32.0 (38.7×); short len-3 patterns gain least (8.8–9.1× — fixed costs dominate). Cold (fresh index + first query): 2.9–13.4×, growing with pattern length. Index build: 1.41–1.65× slower than Fuse.js (the one-time lowercase+copy), amortized within the first couple of queries.

Options matrix

Supported — the 90% case, bit-exact vs Fuse.js 7.1.0: keys (strings, dotted paths, {name, weight}, array-valued), threshold, location, distance, minMatchCharLength, includeScore, includeMatches, shouldSort (default comparator), ignoreLocation, isCaseSensitive, findAllMatches, ignoreFieldNorm, fieldNormWeight, limit. String lists and object lists with nested/array keys.

Unsupported — constructor throws UnsupportedOptionError listing the supported set, on both backends: extended search (useExtendedSearch: true — '-exact, ^ prefix, ! negation, | OR, space-AND) and logical $and/$or query objects; ignoreDiacritics; custom getFn / sortFn; external indices (Fuse.createIndex / parseIndex / constructor index); non-integer location/minMatchCharLength, non-finite threshold. The vendored fallback is Fuse.js's basic build, which has the same restrictions — so both backends behave identically by construction. The extended-search gap is deliberate and discussed in the FAQ.

Controls

Surface	Behavior
$FUSE_MOJO_NATIVE_LIB	explicit library override (first in resolution order)
FUSE_MOJO_DISABLE_NATIVE=1	force the vendored Fuse.js fallback
FUSE_MOJO_THREADS=N	cap native threads (default: online CPUs, max 64)
FUSE_MOJO_MIN_CHUNK=N	override min documents-per-thread (default 2048)
Fuse.backendInfo() / Fuse.nativeAvailable() / fuse.backend	inspect active backend

---

Benchmarks · Kernels · How It Works · Apache-2.0, © 2026 Algenta (Fuse.js vendored under its own Apache-2.0 license — see the package NOTICE)