* 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>
