* chore: deps: Only use frizbee on x86_64 and aarch64
* chore: update docs for frizbee support
* chore: docs [skip ci]
---------
Co-authored-by: LoricAndre <57358788+LoricAndre@users.noreply.github.com>
* 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>
This PR has grown beyond its initial scope due to me over-optimizing everything, but it leads to:
Paving the way for future actually interactive previews
Consistently better performance than fzf in our bench thanks to thread and concurrency optimizations as well as the use of kanal for the items channels
Given the scope, I'm marking this as breaking because:
setting wrap in the preview window layout disables the pty since we don't want to manipulate the raw buffer to word-wrap it manually
kanal channels work slightly differently and might break library usage, even though switching to them did not require any modifications of the examples so it's unlikely that users will see anything break
* fix: force cwd for preview
* fix: correctly set cwd & kill pty child in the right order
* fix: use std threads & reopen new pty for each preview
* feat: use tui-term for displaying
* feat: scroll in pty
* fix: make nested skim previews work
* fix: clippy mistake
* feat: reactive preview triggering
* chore: generate completions & manpage
* chore: optimizations & thread cleanup
* chore: use kanal for faster channels
* fix: tests
* fix: only send items if the matcher hasn't been killed in the meantime (#947)
* tests: add coverage
* tests: fix bin path with coverage
* tests: upload tests to codecov
* chore: make pty opt-in through preview-window
* chore: generate completions & manpage
---------
Co-authored-by: Skim bot <skim-bot@skim-rs.github.io>
