* feat: initial work on skim v3
wip
* wip: SW
* chore: refactor SkimV3 to make it more maintainable
* chore: remove SIMD batch scores
* fix: fix Skim V3 tests
* feat: small optimizations
* feat: bigger optimizations
* chore: generate completions & manpage
* chore: remove unused wide dependency
* chore: update deps
* chore: generate completions & manpage
* fix: make sure all subsequences pass in non-typos mode
* chore: trade some performance against more precision with typos
* feat: gain the performance back using unchecked accesses
* chore: remove failing tests
* feat: use banding across whole upper triangle
* chore: remove useless DEAD_COL checks
* feat: make sure we match everything `frizbee` does while enforcing first char
* feat: minor optimizations
* feat: more minor optimizations
* chore: tweak parameters to find a good balance between performance and accuracy
* chore: accept snap
* chore: penalize consecutive typos
* chore: revert consecutive typos penalization as it seems useless in practice
* wip: optimizations
* feat: multiple optimizations
* perf(skim_v3): use 2-row rolling buffer for score-only DP path
When compute_indices=false (fuzzy_match), the full (n+1)×mcols matrix
was allocated and populated even though traceback was never performed.
Introduce score_only_dp() which maintains only two rows at a time,
reducing memory from O(n×m) to O(m) and improving cache utilization
for long choice strings.
* perf(skim_v3): add early termination when DP rows are all-zero
Track consecutive rows where no cell has a positive score. After 2
consecutive dead rows, return None immediately: gap penalties can only
decrease existing scores, so no downstream row can produce a positive
result. Applied to both score_only_dp and full_dp.
* perf(skim_v3): add range_dp for fuzzy_match_range, avoiding full index vec
fuzzy_match_range previously called fuzzy_indices (full traceback collecting
every matched index) just to extract the first and last. Introduce range_dp
which performs the same full-matrix DP but during traceback only records the
begin and end positions, avoiding the Vec allocation and index collection.
Add range_consistent_with_indices test to verify correctness.
* perf(skim_v3): remove redundant is_subsequence scan in exact mode
In non-typo mode, is_subsequence was called before compute_banding, but
compute_banding -> compute_first_match_cols already validates the same
subsequence property (returning None if any pattern char is absent).
Remove the redundant O(m) scan and delete the now-unused is_subsequence
function. Typo mode retains cheap_typo_prefilter as its guard.
* perf(skim_v3): avoid clone in traceback by using mem::take on thread-local buffer
Previously full_dp returned indices via indices_ref.to_vec() which copies
all n index values into a new allocation. Replace with std::mem::take which
moves ownership of the populated Vec out of the thread-local without copying,
trading the reuse-across-calls benefit for zero-copy return per call.
* perf(skim_v3): tighten typo-mode upper band bound in typo_vband_row
Previously the upper column bound in typo mode was always m (the full
choice length), even for early rows where the diagonal sits far from the
right edge. Compute hi = (j + bandwidth).min(m) symmetrically with the
existing lower bound, skipping cells that cannot contribute to a valid
alignment and reducing work for short patterns on long strings.
* perf(skim_v3): use memchr SIMD for first-char search in prefilter and banding
Add memchr as a direct dependency and implement Atom::find_first_in with
a u8-specialization that calls memchr() for case-sensitive search and a
two-call min-of-two approach for case-insensitive. Use this in:
- cheap_typo_prefilter: first-character existence check
- find_first_char: typo-mode banding anchor computation
This replaces scalar byte-by-byte loops with SIMD-vectorized searches for
ASCII inputs, the common case.
* revert(skim_v3): restore m upper bound in typo_vband_row
The tightened hi = (j + bandwidth).min(m) bound incorrectly rejected valid
typo-mode alignments where the optimal path takes many LEFT (gap) steps
past the bandwidth boundary. The snapshot test confirms 5 fewer matches vs
the expected 37. Revert to hi = m; the affine gap penalty alone prevents
poor alignments from winning.
* perf(skim_v3): add ASCII fast path to char::eq_ignore_case
Replace the to_lowercase() iterator comparison with eq_ignore_ascii_case()
for the common case where both chars are ASCII. This avoids creating two
ToLowercase iterators per comparison in the non-ASCII DP path, using a
single bitwise comparison instead.
* perf(skim_v3): replace RefCell with UnsafeCell (TLCell) in thread-locals
ThreadLocal<RefCell<T>> incurs a runtime borrow-check on every access.
Since ThreadLocal already guarantees per-thread isolation and we never
re-enter the same thread-local within a single call stack, the RefCell
check is redundant.
Replace with TLCell<T>, a Send newtype over UnsafeCell<T>, and a tl_get_mut
helper that returns &mut T directly. Document the safety invariant at each
call site. Also remove the now-unused SWMatrix::zero constructor.
* fix(skim_v3): fix precompute_bonuses reserve logic
The previous reserve(cho.len().saturating_sub(buf.len())) computed the
needed additional capacity relative to the current length, which could
be wrong if buf.len() was stale (e.g. after a set_len call on a longer
buffer). Replace with clear() + reserve(cho.len()) for a correct and
clear-intent O(1) reset followed by a single exact reservation.
* guard: return None for pat.len() > MAX_PAT_LEN in exact mode
Patterns longer than MAX_PAT_LEN (16) used the stack-allocated
[usize; MAX_PAT_LEN] banding arrays with out-of-bounds indices,
causing undefined behaviour in the exact (non-typo) DP path.
Add an early return of None in compute_first_match_cols and
compute_last_match_cols so callers gracefully skip overlong patterns
rather than reading past the end of a fixed-size array. Typo mode
is unaffected: its dummy arrays are never indexed by the pattern
length.
* perf: re-encode Dir::None=0 so CELL_ZERO is all-zero bytes
Previously Dir::None=3 made Cell::new(0,Dir::None) encode as
0x00030000, preventing bulk-zeroing with write_bytes(0).
Re-assign discriminants to None=0, Diag=1, Up=2, Left=3 so that
CELL_ZERO is now all-zero. Update:
- Dir discriminants in the enum
- Cell::is_diag() (checks tag==1 instead of 0)
- compute_cell branchless arithmetic (base is Left=3, subtract 2 for
Diag wins, 1 for Up wins; None=0 so no OR needed)
- score_only_dp: replace init loop with write_bytes(0)
- full_dp / range_dp: replace row-0 init loop with write_bytes(0)
* perf: 128-bit ASCII bitset for cheap_typo_prefilter tail scan
Add Atom::count_tail_present with a u8 specialisation that builds a
two-u64 presence bitset from the choice in a single O(m) pass, making
each subsequent pattern-char lookup O(1) instead of O(m).
The char (non-ASCII) path delegates to count_tail_present_ordered, the
same ordered linear scan that was previously inlined in the function.
The change is observationally equivalent: the prefilter remains a
lenient superset of the old check (unordered vs. ordered presence),
and the snapshot test count is unchanged.
* perf: early exit in count_tail_present_ordered when match is impossible
Add a hopeless-state check at the top of each iteration: if matched
plus remaining pattern chars cannot reach min_needed, bail out
immediately rather than completing the full scan.
This prunes the non-ASCII (char) ordered-scan fallback inside
cheap_typo_prefilter when the pattern is long and many chars are
missing from the choice.
* cleanup: remove unused constants SEPARATOR_MASK_LO/HI and FIRST_CHAR_BONUS_MULTIPLIER
All three were suppressed with #[allow(dead_code)] and are not
referenced by any live code. SEPARATOR_TABLE is the active lookup;
the mask constants were documentation remnants.
* refactor: replace unsafe transmute in Cell::dir() and compute_cell with safe match
Both usages converted a u8 (guaranteed 0..=3) to Dir via transmute.
Replace with an exhaustive match on the 2-bit tag value — no unsafe
required, and the compiler generates the same conditional-move
sequence.
* perf: Atom::is_sep() trait method avoids u8→char→u32 in separator check
Add is_sep() to the Atom trait with a u8 specialisation that indexes
SEPARATOR_TABLE directly with self as usize, skipping the into::<char>
conversion required by the generic default.
Remove the now-unnecessary is_separator free function; callers use
prev.is_sep() instead.
* refactor: precompute_bonuses rewritten as safe iterator chain
Replace the unsafe raw-pointer write loop with a safe iterator that
starts with START_OF_STRING_BONUS and maps windows-of-2 to the
separator/camelCase bonus formula. buf.extend() dispatches through
ExactSizeIterator, so no extra allocation occurs.
The safe form exposes the element-independent structure to the
compiler, enabling auto-vectorisation on release builds.
* refactor: extract match_slices_range; simplify run_range
Add match_slices_range<C: Atom> that mirrors match_slices but calls
range_dp instead of dispatch_dp. run_range now delegates the ASCII
path to match_slices_range and keeps only the non-ASCII char-buf
setup inline, eliminating the duplicated prefilter + bonus +
range_dp block.
* mem: SWMatrix::resize shrinks when buffer is 4× over-allocated
After a one-off large input, the full-DP matrix buffer could hold
significantly more memory than typical inputs require. Add a
shrink-or-cap heuristic: if the current capacity exceeds 4× the
needed size, truncate and shrink_to(2×needed) to release excess
memory without thrashing on stable-sized inputs.
* Revert "mem: SWMatrix::resize shrinks when buffer is 4× over-allocated"
This reverts commit 9c8571ebe8.
* Revert "refactor: replace unsafe transmute in Cell::dir() and compute_cell with safe match"
This reverts commit 8805fa14ce.
* Revert "perf: Atom::is_sep() trait method avoids u8→char→u32 in separator check"
This reverts commit 175f26af81.
* Revert "perf: early exit in count_tail_present_ordered when match is impossible"
This reverts commit 29721558f0.
* Revert "perf: 128-bit ASCII bitset for cheap_typo_prefilter tail scan"
This reverts commit d79947fcb5.
* Revert "refactor: extract match_slices_range; simplify run_range"
This reverts commit 0fb7f05513.
* Revert "perf(skim_v3): replace RefCell with UnsafeCell (TLCell) in thread-locals"
This reverts commit 0806683251.
* Revert "perf(skim_v3): add ASCII fast path to char::eq_ignore_case"
This reverts commit 069710ad7c.
* Revert "revert(skim_v3): restore m upper bound in typo_vband_row"
This reverts commit 90ffc46633.
* Revert "perf(skim_v3): tighten typo-mode upper band bound in typo_vband_row"
This reverts commit f38ca3a10d.
* Revert "perf(skim_v3): avoid clone in traceback by using mem::take on thread-local buffer"
This reverts commit ffa9a21167.
* Revert "perf(skim_v3): add early termination when DP rows are all-zero"
This reverts commit 073195be58.
* Revert "perf(skim_v3): use 2-row rolling buffer for score-only DP path"
This reverts commit 3acacaad74.
* fix: reverse only order of frizbee indices
* chore: rename & refactor into multiple files
* chore: optimizations to the main flow
* fix: correct banding in non-typo path
* chore: generate completions & manpage
* docs: add algorithms section to the README [skip ci]
* fix(ari): correctly bound vband low
* chore(ari): specific pre-separator bonuses
* fix(ari): boost consec a bit more to beat start/sep
* chore: generate completions & manpage
* feat: run matcher over chunks
* chore: adjust penalties to keep typos under subsequences
* chore: accept snapshot
* fix: replace greedy ordered prefilter with looser unordered
* chore: finish up rename
* chore: review
---------
Co-authored-by: Skim bot <skim-bot@skim-rs.github.io>
* wip: stable rust, but no match indices
* feat: use restored indices api
* chore: use crates.io pushed 0.8.0
* chore: generate completions & manpage
* fix: remove nightly-specific coverage annotations
---------
Co-authored-by: Skim bot <skim-bot@skim-rs.github.io>
* refactor: move filter mode into run_with via should_enter
Remove the standalone `filter` function from main.rs and integrate
filter mode into the main `run_with` pipeline. When `options.filter`
is set, `should_enter` now waits for all items to be processed and
returns false (skipping TUI), and `App::results` returns all matched
items. This unifies filter mode with the rest of the codebase so it
benefits from all other flags (sorting, tiebreaks, etc.).
https://claude.ai/code/session_01T7pa2RRX85MvBtnH7PWtmw
* perf: optimize filter mode to match single-pass performance
Three changes that eliminate the performance regression from routing
filter mode through run_with:
1. should_enter(): Wait for reader to finish BEFORE starting matcher,
then run matcher exactly once. The old polling loop called
restart_matcher() repeatedly, each time resetting the ItemPool taken
counter and re-processing all items from scratch. With 1M items
arriving in batches, items were matched multiple times.
2. matcher.run(): Remove unnecessary .enumerate() (index was discarded)
and remove item.clone() — into_par_iter() yields owned values so the
Arc can be moved directly into MatchedItem.
3. App::results(): In filter mode, drain items instead of cloning to
avoid 271K MatchedItem clones + Arc allocations.
Benchmark (1M file paths, query "test", 10 runs):
Old standalone filter: 5.306s ± 0.085s
New unified filter: 4.932s ± 0.099s (1.08x faster)
https://claude.ai/code/session_01T7pa2RRX85MvBtnH7PWtmw
* perf: make restart_matcher incremental when force=false
When force=false, skip the item pool reset so take() only returns new
(untaken) items. The callback merges new sorted matches into the
existing sorted result list using an O(n+m) merge, instead of
replacing it. This fixes the root cause: previously every
restart_matcher call re-processed ALL items from scratch because
reset() set the taken counter to 0.
This benefits all polling callers (filter, select-1, exit-0, sync),
not just filter mode. Items arriving in batches are now each matched
exactly once, and matching overlaps with I/O since batches are
processed as they arrive.
When force=true (query changed), behavior is unchanged: full reset
and re-match.
Reverts the filter-specific workaround from the previous commit in
favor of this general fix; the original polling loop in should_enter
is now efficient.
Benchmark (1M file paths, query "test", 10 runs):
Old standalone filter (master): 4.566s ± 0.055s
Incremental restart_matcher: 3.654s ± 0.035s (1.25x faster)
https://claude.ai/code/session_01T7pa2RRX85MvBtnH7PWtmw
* refactor: extract sorted_merge into MatchedItem method
Move the two-sorted-list merge from the restart_matcher closure into
MatchedItem::sorted_merge() for clarity and reusability. The method
merges two Vec<MatchedItem> lists that are already sorted by rank
into a single sorted Vec in O(n+m) time.
https://claude.ai/code/session_01T7pa2RRX85MvBtnH7PWtmw
* fix: preserve incremental matches across render cycles
When restart_matcher runs with force=false, the callback marks results
with a MergeStrategy so the render loop knows how to combine them with
existing items. Previously, render's .take() would drain processed_items
to None, and the next incremental callback would create a fresh batch —
causing the render to replace all items with just the latest batch,
losing previously matched items.
Now:
- Replace: full re-match (force=true), replaces item list entirely
- SortedMerge: incremental sorted results, merged into item_list.items
- Append: incremental unsorted results (--no-sort), appended
This fixes match count consistency in interactive mode. With 1M items
and query "test", match count is now 290,083 on every run (matching
fzf's consistency), vs wildly varying counts before (min 13, max 56,950).
https://claude.ai/code/session_01T7pa2RRX85MvBtnH7PWtmw
* chore: fmt & clippy
---------
Co-authored-by: Claude <noreply@anthropic.com>
* Initial commit
* Disable Matcher when query is empty
* Revert
* Cleanup
* Use par_chunks for faster search
* Cleanup
* Skip updating atomic on every iter
* Item index unnecessary?
* Cleanup
* Build thread pool at App level
* Initial commit
* Disable Matcher when query is empty
* Revert
* Cleanup
* Use par_chunks for faster search
* Cleanup
* Skip updating atomic on every iter
* Item index unnecessary?
* Cleanup
* Build thread pool at App level
* Make suggested improvements
* chore: cleanup after rebase
* refactor: rewrite insta test harness to use fine-grained Skim:: methods
Split `impl Skim` into a generic `impl<Backend> Skim<Backend>` block so
that `Skim::init()`, `Skim::start()`, `Skim::tick()`, etc. work with
any backend, not just the default CrosstermBackend.
New public API on Skim<B>:
- `init_tui_with(tui)` – inject a caller-provided TUI (e.g. TestBackend)
- `app()` / `app_mut()` – access the application state
- `tui_ref()` / `tui_mut()` – access the TUI
- `app_and_tui()` – simultaneous mutable access to both (avoids borrow
conflicts in render and handle_event calls)
- `final_event()` – inspect the quit event
TestHarness now wraps `Skim<TestBackend>` and initializes via
`Skim::init()` + `Skim::init_tui_with()`, sharing the production
init path (theme, reader, command expansion) instead of duplicating it.
https://claude.ai/code/session_016PtHKc9YVEpHftDxG5Nger
* chore: make insta harness more realistic
* Cleanup merge errors
* Remove duplicate check
* Cleanup
* No need to clone twice
* fix: fix thread pool race condition
---------
Co-authored-by: Loric ANDRE <loric.andre@pm.me>
Co-authored-by: Claude <noreply@anthropic.com>
