Commit: patch 9.2.0909: insert completion is slow to collect many matches
Christian Brabandt <[email protected]> Tue, 4 Aug 2026 22:45:04 +0200
| Newsgroups | gmane.editors.vim.devel |
|---|---|
| Message-ID | <[email protected]> |
patch 9.2.0909: insert completion is slow to collect many matches Commit: https://github.com/vim/vim/commit/31b7b1a7da4e282ebdf09f3c1c3e16ded7b76e8a Author: Samuel Schlesinger <[email protected]> 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 <[email protected]> Signed-off-by: Christian Brabandt <[email protected]> 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, /**/ -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion visit https://groups.google.com/d/msgid/vim_dev/E1wrM0W-00D9Eh-IZ%40256bit.org.