sift

An async, thread-pooled fuzzy-match engine for large, streaming item lists — the kind a file picker / command palette needs when the candidate set is huge (100k+) and arrives incrementally.

sift is the upper half of a nucleo-style split:

• sift-matcher — the SIMD matching primitives (scoring, top-k, prefilter). Pure, no threads.
• sift (this) — the engine: an item store, a worker pool, query state, and a published snapshot. Depends on sift-matcher.

Why

Matching a 200k-item list on every keystroke blocks the UI thread. sift runs matching on a pool of worker threads, so:

• typing never blocks — setPattern just flags a re-match;
• items stream in — the producer (e.g. a background file walk) calls push from any thread while matching continues;
• the UI reads a cheap snapshot each frame via tick + matches.

Model

producer (any thread) ──push──▶ Store (segmented, stable addresses)
main thread ──setPattern──▶ coordinator ──fork/join──▶ worker pool
worker pool (N × BatchMatcher) ──scores shards──▶
coordinator merges + sorts ──publish──▶ Snapshot ◀──tick/snapshot── main

• A single coordinator thread owns job lifecycle, so there's one starter — no race over who begins a round. Workers are pure chunk-scorers driven by a fork/join barrier.
• Jobs are serialized + coalesced: at most one re-match in flight; requests that arrive mid-job collapse into one re-match when the current finishes.
• Items live in a segmented store whose slots never move, so workers read already-published items lock-free while the producer appends.
• Results are sorted score-desc, then shorter-candidate, then index (fzf/nucleo tie-break). The main thread copies the published set into its own buffer only when it actually changed.

Usage

const sift = @import("sift");

var engine = try sift.Engine.init(allocator, .{
    .config = sift_matcher.Config.pathMatchingUnix(),
    .threads = 0, // 0 → derive from CPU count
});
defer engine.deinit();

// Producer (any thread):
try engine.push("src/main.zig");

// Main thread, on keystroke:
engine.setPattern("main");

// Main thread, each frame:
const status = engine.tick();           // { running, changed }
for (engine.matches()) |m| {
    const text = engine.item(m.index);  // ranked result
}

Status

Single-process, in-memory. Worker pool + fork/join + segmented store + coalesced re-match are implemented and tested (including concurrent push-while-match and rapid pattern coalescing). Not yet: incremental append-narrowing on the worker side (re-match currently re-scores the full list per job), per-match position highlights in the snapshot.

License

MIT