[vim/vim] ins_compl_add(): use a hashtab for the duplicate check (PR #20926)
Samuel Schlesinger
Problem
ins_compl_add() checks for an existing match by scanning the whole
match list, so collecting N candidates is O(N²). Large dictionaries
and keyword-rich buffers hang; 'autocomplete' pays this per keystroke.
Solution
Keep match strings in a hashtab and look candidates up there. The old
scan is an exact-match, case-sensitive test, so the lookup is
equivalent; the scan is kept for "nearest" scoring, which must visit
matches to update scores. complete_info() output is byte-identical to
an unpatched build across ten dedup scenarios.
Benchmarks (min of 3): CTRL-X CTRL-K on /usr/share/dict/words
0.23s -> 0.020s; CTRL-N over 20k unique words 0.83s -> 0.016s.
Adds Test_ins_complete_dedup(); it also passes unpatched, pinning the
existing behavior.
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/20926
Commit Summary
- 3dd8788 ins_compl_add(): use a hashtab for the duplicate check
- 37abbab test: cover the completion duplicate check
File Changes
(2 files)
- M src/insexpand.c (99)
- M src/testdir/test_ins_complete.vim (67)
Patch Links:
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.