Commit: patch 9.2.0909: insert completion is slow to collect many matches

[Christian Brabandt]

patch 9.2.0909: insert completion is slow to collect many matches

Commit: https://github.com/vim/vim/commit/31b7b1a7da4e282ebdf09f3c1c3e16ded7b76e8a
Author: Samuel Schlesinger <sgschl...@gmail.com>
Date: Tue Aug 4 20:31:44 2026 +0000

patch 9.2.0909: insert completion is slow to collect many matches

Problem: ins_compl_add() checks for a duplicate by scanning the whole
match list, making collection of N matches quadratic.
Solution: Look matches up in a hashtab instead; each entry counts the
matches with that string (Samuel Schlesinger).

closes: #20926

Co-Authored-By: Claude <nor...@anthropic.com>
Signed-off-by: Christian Brabandt <c...@256bit.org>

diff --git a/src/hashtab.c b/src/hashtab.c
index 6d3774879..9533337c4 100644
--- a/src/hashtab.c
+++ b/src/hashtab.c
@@ -95,7 +95,6 @@ hash_clear(hashtab_T *ht)
vim_free(ht->ht_array);
}

-#if defined(FEAT_SPELL) || defined(FEAT_TERMINAL)
/*
* Free the array of a hash table and all the keys it contains. The keys must
* have been allocated. "off" is the offset from the start of the allocate
@@ -118,7 +117,6 @@ hash_clear_all(hashtab_T *ht, int off)
}
hash_clear(ht);
}
-#endif

/*
* Find "key" in hashtable "ht". "key" must not be NULL.
diff --git a/src/insexpand.c b/src/insexpand.c
index 16b2e7b52..b12f69eb0 100644
--- a/src/insexpand.c
+++ b/src/insexpand.c
@@ -136,6 +136,56 @@ static compl_T *compl_curr_match = NULL;
static compl_T *compl_shown_match = NULL;
static compl_T *compl_old_match = NULL;

+// Hashtab with the strings of the matches in the list above, except the
+// original-text entries. Used to make the duplicate check O(1) instead of
+// a scan of the whole list. Each entry owns a copy of the string and
+// counts the matches with that string, so that when matches were added
+// with "adup" the entry remains until the last match with the string is
+// removed.
+typedef struct
+{
+ int cse_count; // number of matches with this string
+ char_u cse_str[1]; // the string, actually longer
+} complstr_T;
+
+#define CSE_OFF ((int)offsetof(complstr_T, cse_str))
+#define HI2CSE(hi) ((complstr_T *)((hi)->hi_key - CSE_OFF))
+
+static hashtab_T compl_strings_ht;
+
+/*
+ * Count the string of a new match in the duplicate-check hashtab.
+ * "hash" is the hash of "str" when it is not zero, saving hashing the
+ * string again.
+ */
+ static void
+compl_strings_add(char_u *str, size_t len, hash_T hash)
+{
+ hashitem_T *hi;
+ complstr_T *entry;
+
+ if (compl_strings_ht.ht_array == NULL)
+ hash_init(&compl_strings_ht);
+ if (hash == 0)
+ hash = hash_hash(str);
+ hi = hash_lookup(&compl_strings_ht, str, hash);
+ if (HASHITEM_EMPTY(hi))
+ {
+ entry = alloc(CSE_OFF + len + 1);
+ if (entry == NULL)
+ // Out of memory: the duplicate check degrades, an equal string
+ // added later is not recognized as a duplicate.
+ return;
+ entry->cse_count = 1;
+ vim_strncpy(entry->cse_str, str, len);
+ if (hash_add_item(&compl_strings_ht, hi, entry->cse_str, hash)
+ == FAIL)
+ vim_free(entry);
+ }
+ else
+ ++HI2CSE(hi)->cse_count;
+}
+
// list used to store the compl_T which have the max score
static compl_T **compl_best_matches = NULL;
static int compl_num_bests = 0;
@@ -902,6 +952,8 @@ ins_compl_add(
int dir = (cdir == 0 ? compl_direction : cdir);
int flags = flags_arg;
int inserted = FALSE;
+ char_u *new_str = NULL;
+ hash_T str_hash = 0; // hash of the match string, when not 0

if (flags & CP_FAST)
fast_breakcheck();
@@ -913,22 +965,53 @@ ins_compl_add(
len = (int)STRLEN(str);

// If the same match is already present, don't add it.
- if (compl_first_match != NULL && !adup)
+ if (compl_first_match != NULL && !adup && compl_strings_ht.ht_used > 0)
{
- match = compl_first_match;
- do
+ // Use a stack buffer for the NUL-terminated key when it fits, so
+ // that rejecting a duplicate does not allocate memory.
+ char_u keybuf[128];
+ char_u *key;
+ hashitem_T *hi;
+
+ if (len < (int)sizeof(keybuf))
+ {
+ mch_memmove(keybuf, str, (size_t)len);
+ keybuf[len] = NUL;
+ key = keybuf;
+ }
+ else
+ {
+ new_str = vim_strnsave(str, len);
+ if (new_str == NULL)
+ return FAIL;
+ key = new_str;
+ }
+ str_hash = hash_hash(key);
+ hi = hash_lookup(&compl_strings_ht, key, str_hash);
+ if (!HASHITEM_EMPTY(hi))
{
- if (!match_at_original_text(match)
- && STRNCMP(match->cp_str.string, str, len) == 0
- && ((int)match->cp_str.length <= len
- || match->cp_str.string[len] == NUL))
+ if (is_nearest_active() && score > 0)
{
- if (is_nearest_active() && score > 0 && score < match->cp_score)
- match->cp_score = score;
- return NOTDONE;
+ // The duplicate may need its score updated, scan the
+ // matches to find it.
+ match = compl_first_match;
+ do
+ {
+ if (!match_at_original_text(match)
+ && STRNCMP(match->cp_str.string, str, len) == 0
+ && ((int)match->cp_str.length <= len
+ || match->cp_str.string[len] == NUL))
+ {
+ if (score < match->cp_score)
+ match->cp_score = score;
+ break;
+ }
+ match = match->cp_next;
+ } while (match != NULL && !is_first_match(match));
}
- match = match->cp_next;
- } while (match != NULL && !is_first_match(match));
+ vim_free(new_str);
+ return NOTDONE;
+ }
}

// Remove any popup menu before changing the list of matches.
@@ -938,14 +1021,17 @@ ins_compl_add(
// Copy the values to the new match structure.
match = ALLOC_CLEAR_ONE(compl_T);
if (match == NULL)
+ {
+ vim_free(new_str);
return FAIL;
+ }
match->cp_number = flags & CP_ORIGINAL_TEXT ? 0 : -1;
- if ((match->cp_str.string = vim_strnsave(str, len)) == NULL)
+ if (new_str == NULL && (new_str = vim_strnsave(str, len)) == NULL)
{
vim_free(match);
return FAIL;
}
-
+ match->cp_str.string = new_str;
match->cp_str.length = len;

// match-fname is:
@@ -1035,6 +1121,10 @@ ins_compl_add(
compl_first_match = match;
compl_curr_match = match;

+ if (!match_at_original_text(match))
+ compl_strings_add(match->cp_str.string, match->cp_str.length,
+ str_hash);
+
// Find the longest common string if still doing that.
if (compl_get_longest && (flags & CP_ORIGINAL_TEXT) == 0 && !cot_fuzzy()
&& !ins_compl_preinsert_longest() && !ctrl_x_mode_thesaurus())
@@ -2263,6 +2353,25 @@ find_line_end(char_u *ptr)
static void
ins_compl_item_free(compl_T *match)
{
+ // Uncount the match string in the duplicate-check hashtab; the entry is
+ // only removed with its last match. The hashtab is empty when it was
+ // already cleared as a whole by ins_compl_free().
+ if (compl_strings_ht.ht_used > 0 && match->cp_str.string != NULL
+ && !match_at_original_text(match))
+ {
+ hashitem_T *hi = hash_find(&compl_strings_ht, match->cp_str.string);
+
+ if (!HASHITEM_EMPTY(hi))
+ {
+ complstr_T *entry = HI2CSE(hi);
+
+ if (--entry->cse_count <= 0)
+ {
+ hash_remove(&compl_strings_ht, hi, "completion match");
+ vim_free(entry);
+ }
+ }
+ }
VIM_CLEAR_STRING(match->cp_str);
// several entries may use the same fname, free it just once.
if (match->cp_flags & CP_FREE_FNAME)
@@ -2292,6 +2401,11 @@ ins_compl_free(void)
ins_compl_del_pum();
pum_clear();

+ // Free the duplicate-check hashtab entries all at once, then freeing
+ // the matches below does not need to uncount them one by one.
+ hash_clear_all(&compl_strings_ht, CSE_OFF);
+ hash_init(&compl_strings_ht);
+
compl_curr_match = compl_first_match;
do
{
diff --git a/src/testdir/test_ins_complete.vim b/src/testdir/test_ins_complete.vim
index 5dd18ecf2..a0ee08dc1 100644
--- a/src/testdir/test_ins_complete.vim
+++ b/src/testdir/test_ins_complete.vim
@@ -5903,7 +5903,9 @@ func Test_completetimeout_autocompletetimeout()
set completetimeout=1
call feedkeys("Gof\<C-N>\<F2>\<Esc>0", 'xt!')
let match_count = len(b:matches->mapnew('v:val.word'))
- call assert_true(match_count < 4000)
+ " How many matches are collected in 1 msec varies with machine speed, only
+ " check the timeout truncated the collection.
+ call assert_true(match_count < 60000)

set completetimeout=1000
call feedkeys("\<Esc>Sf\<C-N>\<F2>\<Esc>0", 'xt!')
@@ -5912,9 +5914,14 @@ func Test_completetimeout_autocompletetimeout()

set autocomplete
set autocompletetimeout=81
+ " Use enough long words that collecting all of them takes well over the
+ " timeout even on a fast machine.
+ let pad = repeat('y', 60)
+ call setline(1, map(range(200000), '"foo" . v:val . pad'))
call feedkeys("\<Esc>Sf\<F2>\<Esc>0", 'xt!')
let match_count = len(b:matches->mapnew('v:val.word'))
- call assert_true(match_count < 50000)
+ " The timeout must have truncated the collection.
+ call assert_true(match_count < 200000)

set complete& omnifunc& autocomplete& autocompletetimeout& completetimeout&
bwipe!
@@ -6634,4 +6641,90 @@ func Test_complete_check_mapped_typed_key()
unlet g:compl_iterations
endfunc

+" Test for the duplicate check when adding completion matches
+func Test_ins_complete_dedup()
+ new
+ setl complete=.
+
+ " a word that occurs several times only results in one match
+ call setline(1, ['alpha beta alpha gamma', 'beta alpha delta beta', ''])
+ call cursor(3, 1)
+ call feedkeys("Aal\<C-N>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['alpha'], g:compl_info.items->mapnew('v:val.word'))
+
+ " the duplicate check is case-sensitive
+ %delete _
+ call setline(1, ['Foo foo FOO fooBar Foo foo', ''])
+ call cursor(2, 1)
+ call feedkeys("Afo\<C-N>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['foo', 'fooBar'], g:compl_info.items->mapnew('v:val.word'))
+
+ " with 'ignorecase' and 'infercase' case variants fold into one match
+ setl ignorecase infercase
+ %delete _
+ call setline(1, ['Word word WORD wordy Word', ''])
+ call cursor(2, 1)
+ call feedkeys("Awo\<C-N>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['word', 'wordy'], g:compl_info.items->mapnew('v:val.word'))
+ setl noignorecase noinfercase
+
+ " duplicate dictionary entries only appear once; with 'ignorecase' case
+ " variants all match but stay separate matches
+ call writefile(['apple', 'apple', 'Apple', 'apricot', 'apricot', 'banana'],
+ \ 'Xcompldict', 'D')
+ setl dictionary=Xcompldict
+ set ignorecase
+ %delete _
+ call feedkeys("Aap\<C-X>\<C-K>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['apple', 'Apple', 'apricot'], g:compl_info.items->mapnew('v:val.word'))
+ set noignorecase
+ setl dictionary&
+
+ " duplicate items passed to complete() are only added once
+ inoremap <buffer> <F5> <Cmd>call complete(1, ['dup', 'dup', 'uniq', 'dup'])<CR>
+ %delete _
+ call feedkeys("i\<F5>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['dup', 'uniq'], g:compl_info.items->mapnew('v:val.word'))
+
+ " restarting a completion rebuilds the matches without duplicates
+ %delete _
+ call setline(1, ['echo edit eecho edit echo', ''])
+ call cursor(2, 1)
+ call feedkeys("Ae\<C-N>\<C-E>\<Esc>", 'tx')
+ call feedkeys("A\<C-N>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['echo', 'edit', 'eecho'], g:compl_info.items->mapnew('v:val.word'))
+
+ " With "dup" matches from several sources, refreshing one source removes
+ " its duplicate but must not forget about the equal match of the other
+ " source: adding "dupword" again without "dup" is still a duplicate.
+ let g:dedup_calls = 0
+ func! DedupSrcA(findstart, base)
+ if a:findstart
+ return 0
+ endif
+ let g:dedup_calls += 1
+ if g:dedup_calls == 1
+ return #{words: [#{word: 'dupword', dup: 1}], refresh: 'always'}
+ endif
+ return #{words: [#{word: 'dupword'}], refresh: 'always'}
+ endfunc
+ func! DedupSrcB(findstart, base)
+ if a:findstart
+ return 0
+ endif
+ return #{words: [#{word: 'dupword', dup: 1}]}
+ endfunc
+ setl complete=FDedupSrcA,FDedupSrcB
+ %delete _
+ call feedkeys("Sdup\<C-N>\<BS>\<C-R>=GetCompleteInfo()\<CR>\<C-E>\<Esc>", 'tx')
+ call assert_equal(['dupword'], g:compl_info.items->mapnew('v:val.word'))
+ setl complete&
+ delfunc DedupSrcA
+ delfunc DedupSrcB
+ unlet g:dedup_calls
+
+ bwipe!
+ unlet g:compl_info
+endfunc
+
" vim: shiftwidth=2 sts=2 expandtab nofoldenable
diff --git a/src/version.c b/src/version.c
index bc604af0b..cba6e9a4f 100644
--- a/src/version.c
+++ b/src/version.c
@@ -763,6 +763,8 @@ static char *(features[]) =

static int included_patches[] =
{ /* Add new patch number below this line */
+/**/
+ 909,
/**/
908,
/**/