Store just the indices of the matching items in matches. The text is
looked up in selectable_items, and the positions to highlight are
computed in get_matches_to_print() only for the rendered matches, using
the query that produced the current matches. This reduces useless work
of computing highlight positions when only handful of items can be
displayed at the time on screen in practice.
Sort matches without lua comparator, this significantly speeds up
sorting of big lists, where C->Lua round-trip was problematic.
Overall it's 10x-20x times faster in my testcase.
Replace those conditions with precomputed lookup. It's not huge win, but
it's free, so we can do it.
JIT:
* score() x 44875 matches: 35 -> 25 ms
* filter_range 'p': 50 -> 25 ms
* filter_range 'pf': 61 -> 37 ms
interpreter:
* score() x 44875 matches: 295 -> 254 ms
* filter_range 'p': 412 -> 284 ms
* filter_range 'pf': 531 -> 388 ms
The lookup is dense, to avoid hash tables, which makes things slower,
but in fact the tables are reused, so it's low on memory.
Add fzy.filter_range() which computes only scores, appends to
caller-provided arrays instead of allocating tables per match, takes
an inclusive range so callers can process a large list in slices while
handling pending input in between, and accepts optional pre-lowercased
haystacks so repeated calls don't allocate a lowercase copy of the whole
list each time.
There could be a lot more done if we target luajit only. Or if we port
this to C. But for now let's keep it this way. It's 2-3x faster than
before, and the issue is mostly only on very big inputs, which are not
that common in practice.
Previously computing scores allocated two matrices of lua tables per
call. With hundreds of thousands of items this made fuzzy matching in
console.lua GC-bound.
When only the score is needed, keep two reused rolling matrix rows,
making repeated scoring allocation-free. positions() still keeps all
rows since tracing back the matched positions requires them.
fzy.filter() of 300000 items drops from 1013 ms to 356 ms (on my setup)
for a worst-case single-character needle, and a standalone score() call
no longer allocates at all.
This are char comparisions, but in lua they are expressed as full string
compare. Compare as bytes instead, this is significantly faster,
especially with luajit compiled code.
This allows scripts to make the user choose from a list of entries by
typing part of their text and/or by navigating them with keybindings,
like dmenu or fzf.
Closes#13964.
Kacper Michajłow