ccomplete#Complete very slow on large tags file

[Pratyush Yadav]

Hi,

I am using the built-in ccomplete#Complete omnifunc for tags-based
completion. It works pretty well with a small or medium sized project.
But on larger projects like Linux or U-Boot, the tags file is pretty big
(~650k lines/70 for U-Boot and ~4.8 mil lines/630MB for Linux).

On these projects, especially Linux, if I use ccomplete, completion
takes a huge amount of time. And since the completion is synchronous,
vim just freezes up for that time and I have to wait for the completion
results to show up. On Linux the wait times can go more than a minute on
my modest quad core 4th gen i7 and a SATA SSD.

So, I intend to set aside some time and try to speed up the completion
and make it asynchronous. I haven't read or written much vimscript so I
don't expect it to be easy or quick. So before I do that, I'd like to
know if anyone here attempted this before.

If someone did succeed, could you please point me to the optimized
version? If someone tried but failed, could you please let me know where
you had trouble? Is it that the ctags format just not suitable for large
projects? Is there some limitation with vim that makes it impossible? Is
it something else entirely?

--
Regards,
Pratyush Yadav

[Tony Mechelynck]

The Vim tags file is pretty large, but how is your tags file built? In
particular, is it case-fold-sorted? If your Vim is built with
+tag_binary (nowadays it always is, if yours isn't you need a newer
model), and 'tagbsearch' is on (which is the default), then finding a
tag in an unsorted tags file uses linear time, in a case-folded sorted
tags file it uses logarithmic time, which is much faster, especially
for large tags files.

Best regards,
Tony.

[Tony Mechelynck]

On Wed, Apr 1, 2020 at 8:02 PM Pratyush Yadav <m...@yadavpratyush.com> wrote:
>
> Hi Tony,

> Yes, the tags file is sorted and vim is built with +tag_binary and
> 'tagbsearch' is on. The tags file wasn't case-folded sorted, but I tried
> with that too and I see similar performance.
>
> Anyway, just to remove any potential confusion, jumping to tags via
> 'CTRL-]' is blazing fast. So is listing all alternatives with 'g]'. Does
> ccomplete use the same mechanism for searching tags file as those two?
> If so, then I wonder why it is so much slower.
>
> Also if I have a struct foo, doing something like 'foo->' takes a huge
> amount of time because I think there is no other way to get a list of
> members of a struct without a linear search, but that is a different
> problem entirely.
>
> --
> Regards,
> Pratyush Yadav

Hm, check the help for 'complete' and for the following completion
options (in the current helpfile, options.txt dated 2020 Mar 02, there
are 127 lines for them all). Maybe something will ring a bell with
you.

Best regards,
Tony.

[Christian Brabandt]

[I did not receive the original mail, so answering to Tonys mail, please
keep the list on CC]

On Mi, 01 Apr 2020, Tony Mechelynck wrote:

> > Yes, the tags file is sorted and vim is built with +tag_binary and
> > 'tagbsearch' is on. The tags file wasn't case-folded sorted, but I tried
> > with that too and I see similar performance.
> >
> > Anyway, just to remove any potential confusion, jumping to tags via
> > 'CTRL-]' is blazing fast. So is listing all alternatives with 'g]'. Does
> > ccomplete use the same mechanism for searching tags file as those two?
> > If so, then I wonder why it is so much slower.

Hm, I had a quick look at ccomplete.vim. It not only does a tag search,
but also searches the current file and more importantly, it might call
:vimgrep and :vimgrep is known to be slow if many files have to be
searched. Not sure if there is anything to improve, perhaps adding a
switch to only do tag completion would already help?

Anyhow, first please create a vimscript profile, so we can exactly see
when it is slow. See :h :profile and this stackoverflow answer:
https://stackoverflow.com/a/12216578/789222

Perhaps this can share some more light on the slowness.

Thanks,
Christian
--
Dieser Satz beinhalten drei Fehller.

[Tony Mechelynck]

…and note that the :profile command requires the +profile feature,
normally excluded at compile-time except in Huge builds.

>
> Perhaps this can share some more light on the slowness.
>
> Thanks,
> Christian
> --
> Dieser Satz beinhalten drei Fehller.

Best regards,
Tony.

[Pratyush Yadav]

On 02/04/20 09:09AM, Christian Brabandt wrote:
> [I did not receive the original mail, so answering to Tonys mail, please
> keep the list on CC]

Strange. I did keep the list in Cc (v...@vim.org, but now I've also
included vim...@googlegroups.com). I think my emails are being held up
by something because I noticed that when I sent the first email it took
a while (multiple hours) to show up in the Google groups archive. And
now I see that my reply doesn't show up in the archive even though my
mail client shows v...@vim.org in Cc.

> On Mi, 01 Apr 2020, Tony Mechelynck wrote:
>
> > > Yes, the tags file is sorted and vim is built with +tag_binary and
> > > 'tagbsearch' is on. The tags file wasn't case-folded sorted, but I tried
> > > with that too and I see similar performance.
> > >
> > > Anyway, just to remove any potential confusion, jumping to tags via
> > > 'CTRL-]' is blazing fast. So is listing all alternatives with 'g]'. Does
> > > ccomplete use the same mechanism for searching tags file as those two?
> > > If so, then I wonder why it is so much slower.
>
> Hm, I had a quick look at ccomplete.vim. It not only does a tag search,
> but also searches the current file and more importantly, it might call
> :vimgrep and :vimgrep is known to be slow if many files have to be
> searched. Not sure if there is anything to improve, perhaps adding a
> switch to only do tag completion would already help?
>
> Anyhow, first please create a vimscript profile, so we can exactly see
> when it is slow. See :h :profile and this stackoverflow answer:
> https://stackoverflow.com/a/12216578/789222
>
> Perhaps this can share some more light on the slowness.

The profile log is pretty big (~3500 lines) since I use multiple
plugins. Trace of ccomplete#Complete and StructMembers() is pasted
below. Let me know if you need any more info, like traces of other
functions in the call chain.

The major time consumer looks like:

21 130.867568 exe 'silent! keepj noautocmd ' . n . 'vimgrep /\t' . typename . '\(\t\|$\)/j ' . fnames

inside StructMembers().

FUNCTIONS SORTED ON TOTAL TIME
count total (s) self (s) function
2 130.920294 0.013774 ccomplete#Complete()
21 130.873054 <SNR>77_StructMembers()
2 124.341230 0.001711 <SNR>77_Nextitem()
129 6.548978 0.004060 <SNR>77_Tagline2item()
129 6.544918 0.002094 <SNR>77_GetAddition()
128 6.542824 0.009213 <SNR>77_SearchMembers()
14 0.024376 0.001583 airline#check_mode()
2 0.022166 0.004144 airline#highlighter#highlight()
128 0.016388 0.003802 <SNR>77_Tag2item()
76 0.013935 0.003591 airline#highlighter#exec()
14 0.011462 0.000464 airline#extensions#branch#get_head()
14 0.010636 0.000383 airline#extensions#branch#head()
14 0.010169 0.000242 airline#extensions#wordcount#get()
6 0.009927 0.000111 <SNR>61_update_wordcount()
6 0.009742 <SNR>61_get_wordcount()
128 0.009439 <SNR>77_Dict2info()
116 0.009389 0.004537 airline#highlighter#get_highlight()
14 0.008767 0.000787 <SNR>57_update_branch()
20 0.007623 0.000636 <SNR>55_exec_separator()
14 0.007164 0.000748 <SNR>57_update_git_branch()

FUNCTIONS SORTED ON SELF TIME
count total (s) self (s) function
21 130.873054 <SNR>77_StructMembers()
2 130.920294 0.013774 ccomplete#Complete()
6 0.009742 <SNR>61_get_wordcount()
128 0.009439 <SNR>77_Dict2info()
128 6.542824 0.009213 <SNR>77_SearchMembers()
116 0.009389 0.004537 airline#highlighter#get_highlight()
232 0.004197 <SNR>55_get_syn()
2 0.022166 0.004144 airline#highlighter#highlight()
129 6.548978 0.004060 <SNR>77_Tagline2item()
128 0.016388 0.003802 <SNR>77_Tag2item()
76 0.013935 0.003591 airline#highlighter#exec()
128 0.003147 <SNR>77_Tagcmd2extra()
14 0.004693 0.003079 fugitive#Find()
34 0.002095 <SNR>55_GetHiCmd()
129 6.544918 0.002094 <SNR>77_GetAddition()
14 0.001898 <SNR>75_generate_names()
2 124.341230 0.001711 <SNR>77_Nextitem()
76 0.001710 <SNR>55_CheckDefined()
14 0.024376 0.001583 airline#check_mode()
14 0.001486 0.001300 <SNR>57_update_untracked()

FUNCTION ccomplete#Complete()
Defined: /usr/share/vim/vim82/autoload/ccomplete.vim:10
Called 2 times
Total time: 130.920294
Self time: 0.013774

count total (s) self (s)
2 0.000004 if a:findstart
" Locate the start of the item, including ".", "->" and "[...]".
1 0.000003 let line = getline('.')
1 0.000003 let start = col('.') - 1
1 0.000001 let lastword = -1
4 0.000005 while start > 0
4 0.000012 if line[start - 1] =~ '\w'
3 0.000003 let start -= 1
1 0.000002 elseif line[start - 1] =~ '\.'
if lastword == -1
let lastword = start
endif
let start -= 1
1 0.000002 elseif start > 1 && line[start - 2] == '-' && line[start - 1] == '>'
if lastword == -1
let lastword = start
endif
let start -= 2
1 0.000001 elseif line[start - 1] == ']'
" Skip over [...].
let n = 0
let start -= 1
while start > 0
let start -= 1
if line[start] == '['
if n == 0
break
endif
let n -= 1
elseif line[start] == ']' " nested []
let n += 1
endif
endwhile
1 0.000000 else
1 0.000001 break
3 0.000001 endif
4 0.000002 endwhile

" Return the column of the last word, which is going to be changed.
" Remember the text that comes before it in s:prepended.
1 0.000001 if lastword == -1
1 0.000002 let s:prepended = ''
1 0.000001 return start
endif
let s:prepended = strpart(line, start, lastword - start)
return lastword
1 0.000001 endif

" Return list of matches.

1 0.000002 let base = s:prepended . a:base

" Don't do anything for an empty base, would result in all the tags in the
" tags file.
1 0.000001 if base == ''
return []
1 0.000000 endif

" init cache for vimgrep to empty
1 0.000001 let s:grepCache = {}

" Split item in words, keep empty word after "." or "->".
" "aa" -> ['aa'], "aa." -> ['aa', ''], "aa.bb" -> ['aa', 'bb'], etc.
" We can't use split, because we need to skip nested [...].
" "aa[...]" -> ['aa', '[...]'], "aa.bb[...]" -> ['aa', 'bb', '[...]'], etc.
1 0.000001 let items = []
1 0.000001 let s = 0
1 0.000001 let arrays = 0
1 0.000001 while 1
1 0.000005 let e = match(base, '\.\|->\|\[', s)
1 0.000001 if e < 0
1 0.000002 if s == 0 || base[s - 1] != ']'
1 0.000003 call add(items, strpart(base, s))
1 0.000000 endif
1 0.000001 break
endif
if s == 0 || base[s - 1] != ']'
call add(items, strpart(base, s, e - s))
endif
if base[e] == '.'
let s = e + 1 " skip over '.'
elseif base[e] == '-'
let s = e + 2 " skip over '->'
else
" Skip over [...].
let n = 0
let s = e
let e += 1
while e < len(base)
if base[e] == ']'
if n == 0
break
endif
let n -= 1
elseif base[e] == '[' " nested [...]
let n += 1
endif
let e += 1
endwhile
let e += 1
call add(items, strpart(base, s, e - s))
let arrays += 1
let s = e
endif
1 0.000001 endwhile

" Find the variable items[0].
" 1. in current function (like with "gd")
" 2. in tags file(s) (like with ":tag")
" 3. in current file (like with "gD")
1 0.000001 let res = []
1 0.000027 if searchdecl(items[0], 0, 1) == 0
" Found, now figure out the type.
" TODO: join previous line if it makes sense
1 0.000002 let line = getline('.')
1 0.000002 let col = col('.')
1 0.000003 if stridx(strpart(line, 0, col), ';') != -1
" Handle multiple declarations on the same line.
let col2 = col - 1
while line[col2] != ';'
let col2 -= 1
endwhile
let line = strpart(line, col2 + 1)
let col -= col2
1 0.000000 endif
1 0.000003 if stridx(strpart(line, 0, col), ',') != -1
" Handle multiple declarations on the same line in a function
" declaration.
let col2 = col - 1
while line[col2] != ','
let col2 -= 1
endwhile
if strpart(line, col2 + 1, col - col2 - 1) =~ ' *[^ ][^ ]* *[^ ]'
let line = strpart(line, col2 + 1)
let col -= col2
endif
1 0.000001 endif
1 0.000001 if len(items) == 1
" Completing one word and it's a local variable: May add '[', '.' or
" '->'.
1 0.000001 let match = items[0]
1 0.000001 let kind = 'v'
1 0.000005 if match(line, '\<' . match . '\s*\[') > 0
let match .= '['
1 0.000001 else
1 124.341163 0.000009 let res = s:Nextitem(strpart(line, 0, col), [''], 0, 1)
1 0.000001 if len(res) > 0
" There are members, thus add "." or "->".
1 0.001138 if match(line, '\*[ \t(]*' . match . '\>') > 0
1 0.000003 let match .= '->'
else
let match .= '.'
1 0.000000 endif
1 0.000000 endif
1 0.000001 endif
1 0.000011 let res = [{'match': match, 'tagline' : '', 'kind' : kind, 'info' : line}]
elseif len(items) == arrays + 1
" Completing one word and it's a local array variable: build tagline
" from declaration line
let match = items[0]
let kind = 'v'
let tagline = "\t/^" . line . '$/'
let res = [{'match': match, 'tagline' : tagline, 'kind' : kind, 'info' : line}]
else
" Completing "var.", "var.something", etc.
let res = s:Nextitem(strpart(line, 0, col), items[1:], 0, 1)
1 0.000000 endif
1 0.000001 endif

1 0.000002 if len(items) == 1 || len(items) == arrays + 1
" Only one part, no "." or "->": complete from tags file.
1 0.000001 if len(items) == 1
1 0.002090 let tags = taglist('^' . base)
else
let tags = taglist('^' . items[0] . '$')
1 0.000001 endif

" Remove members, these can't appear without something in front.
1 0.000605 call filter(tags, 'has_key(v:val, "kind") ? v:val["kind"] != "m" : 1')

" Remove static matches in other files.
1 0.008299 call filter(tags, '!has_key(v:val, "static") || !v:val["static"] || bufnr("%") == bufnr(v:val["filename"])')

1 0.017006 0.000618 call extend(res, map(tags, 's:Tag2item(v:val)'))
1 0.000000 endif

1 0.000001 if len(res) == 0
" Find the variable in the tags file(s)
let diclist = taglist('^' . items[0] . '$')

" Remove members, these can't appear without something in front.
call filter(diclist, 'has_key(v:val, "kind") ? v:val["kind"] != "m" : 1')

let res = []
for i in range(len(diclist))
" New ctags has the "typeref" field. Patched version has "typename".
if has_key(diclist[i], 'typename')
call extend(res, s:StructMembers(diclist[i]['typename'], items[1:], 1))
elseif has_key(diclist[i], 'typeref')
call extend(res, s:StructMembers(diclist[i]['typeref'], items[1:], 1))
endif

" For a variable use the command, which must be a search pattern that
" shows the declaration of the variable.
if diclist[i]['kind'] == 'v'
let line = diclist[i]['cmd']
if line[0] == '/' && line[1] == '^'
let col = match(line, '\<' . items[0] . '\>')
call extend(res, s:Nextitem(strpart(line, 2, col - 2), items[1:], 0, 1))
endif
endif
endfor
1 0.000000 endif

1 0.000002 if len(res) == 0 && searchdecl(items[0], 1) == 0
" Found, now figure out the type.
" TODO: join previous line if it makes sense
let line = getline('.')
let col = col('.')
let res = s:Nextitem(strpart(line, 0, col), items[1:], 0, 1)
1 0.000000 endif

" If the last item(s) are [...] they need to be added to the matches.
1 0.000002 let last = len(items) - 1
1 0.000001 let brackets = ''
1 0.000001 while last >= 0
1 0.000003 if items[last][0] != '['
1 0.000001 break
endif
let brackets = items[last] . brackets
let last -= 1
1 0.000001 endwhile

1 6.549648 0.000670 return map(res, 's:Tagline2item(v:val, brackets)')

FUNCTION <SNR>77_StructMembers()
Defined: /usr/share/vim/vim82/autoload/ccomplete.vim:496
Called 21 times
Total time: 130.873054
Self time: 130.873054

count total (s) self (s)
" Todo: What about local structures?
21 0.002335 let fnames = join(map(tagfiles(), 'escape(v:val, " \\#%")'))
21 0.000034 if fnames == ''
return []
21 0.000007 endif

21 0.000030 let typename = a:typename
21 0.000021 let qflist = []
21 0.000021 let cached = 0
21 0.000022 if a:all == 0
1 0.000001 let n = '1' " stop at first found match
1 0.000002 if has_key(s:grepCache, a:typename)
let qflist = s:grepCache[a:typename]
let cached = 1
1 0.000000 endif
20 0.000010 else
20 0.000019 let n = ''
21 0.000010 endif
21 0.000020 if !cached
21 0.000019 while 1
21 130.867568 exe 'silent! keepj noautocmd ' . n . 'vimgrep /\t' . typename . '\(\t\|$\)/j ' . fnames

21 0.000335 let qflist = getqflist()
21 0.000279 if len(qflist) > 0 || match(typename, "::") < 0
21 0.000043 break
endif
" No match for "struct:context::name", remove "context::" and try again.
let typename = substitute(typename, ':[^:]*::', ':', '')
21 0.000029 endwhile

21 0.000040 if a:all == 0
" Store the result to be able to use it again later.
1 0.000003 let s:grepCache[a:typename] = qflist
21 0.000014 endif
21 0.000031 endif

" Skip over [...] items
21 0.000035 let idx = 0
21 0.000019 while 1
21 0.000053 if idx >= len(a:items)
let target = '' " No further items, matching all members
break
21 0.000010 endif
21 0.000083 if a:items[idx][0] != '['
21 0.000039 let target = a:items[idx]
21 0.000006 break
endif
let idx += 1
21 0.000034 endwhile
" Put matching members in matches[].
21 0.000026 let matches = []
45 0.000051 for l in qflist
24 0.000103 let memb = matchstr(l['text'], '[^\t]*')
24 0.000042 if memb =~ '^' . target
" Skip matches local to another file.
24 0.000097 if match(l['text'], "\tfile:") < 0 || bufnr('%') == bufnr(matchstr(l['text'], '\t\zs[^\t]*'))
24 0.000048 let item = {'match': memb, 'tagline': l['text']}

" Add the kind of item.
24 0.000127 let s = matchstr(l['text'], '\t\(kind:\)\=\zs\S\ze\(\t\|$\)')
24 0.000021 if s != ''
24 0.000026 let item['kind'] = s
24 0.000018 if s == 'f'
let item['match'] = memb . '('
24 0.000012 endif
24 0.000007 endif

24 0.000036 call add(matches, item)
24 0.000009 endif
24 0.000007 endif
45 0.000035 endfor

21 0.000039 if len(matches) > 0
" Skip over next [...] items
1 0.000002 let idx += 1
1 0.000000 while 1
1 0.000002 if idx >= len(a:items)
1 0.000003 return matches " No further items, return the result.
endif
if a:items[idx][0] != '['
break
endif
let idx += 1
endwhile

" More items following. For each of the possible members find the
" matching following members.
return s:SearchMembers(matches, a:items[idx :], a:all)
20 0.000011 endif

" Failed to find anything.
20 0.000018 return []

--
Regards,
Pratyush Yadav

[Tony Mechelynck]

On Thu, Apr 2, 2020 at 11:06 AM Pratyush Yadav <m...@yadavpratyush.com> wrote:
>
> On 02/04/20 09:09AM, Christian Brabandt wrote:
> > [I did not receive the original mail, so answering to Tonys mail, please
> > keep the list on CC]
>
> Strange. I did keep the list in Cc (v...@vim.org, but now I've also
> included vim...@googlegroups.com). I think my emails are being held up
> by something because I noticed that when I sent the first email it took
> a while (multiple hours) to show up in the Google groups archive. And
> now I see that my reply doesn't show up in the archive even though my
> mail client shows v...@vim.org in Cc.

Anyone's first mail to the list may take hours to appear because it
has to be validated by a human moderator. If it is not spam but a
bona-fide support request or answer, the author is then whitelisted
and further messages by the same author will appear in a matter of
seconds. OTOH if it is spam, the author is blacklisted (banned) from
the list. This is the only way we found to keep the Vim lists
spam-free.

Best regards,
Tony.

[Christian Brabandt]

On Do, 02 Apr 2020, Pratyush Yadav wrote:

> On 02/04/20 09:09AM, Christian Brabandt wrote:
> Strange. I did keep the list in Cc (v...@vim.org, but now I've also
> included vim...@googlegroups.com). I think my emails are being held up
> by something because I noticed that when I sent the first email it took
> a while (multiple hours) to show up in the Google groups archive. And
> now I see that my reply doesn't show up in the archive even though my
> mail client shows v...@vim.org in Cc.

Tony answered that already. I am one of those watching the pending
moderation list, but I did not see your message there.

BTW: v...@vim.org is just an alias for vim...@googlegroups.com so if you
add both, we might receive the mail twice. Not that it matters much for
me.

> > On Mi, 01 Apr 2020, Tony Mechelynck wrote:
> >
> > > > Yes, the tags file is sorted and vim is built with +tag_binary and
> > > > 'tagbsearch' is on. The tags file wasn't case-folded sorted, but I tried
> > > > with that too and I see similar performance.
> > > >
> > > > Anyway, just to remove any potential confusion, jumping to tags via
> > > > 'CTRL-]' is blazing fast. So is listing all alternatives with 'g]'. Does
> > > > ccomplete use the same mechanism for searching tags file as those two?
> > > > If so, then I wonder why it is so much slower.
> >
> > Hm, I had a quick look at ccomplete.vim. It not only does a tag search,
> > but also searches the current file and more importantly, it might call
> > :vimgrep and :vimgrep is known to be slow if many files have to be
> > searched. Not sure if there is anything to improve, perhaps adding a
> > switch to only do tag completion would already help?
> >
> > Anyhow, first please create a vimscript profile, so we can exactly see
> > when it is slow. See :h :profile and this stackoverflow answer:
> > https://stackoverflow.com/a/12216578/789222
> >
> > Perhaps this can share some more light on the slowness.
>
> The profile log is pretty big (~3500 lines) since I use multiple
> plugins. Trace of ccomplete#Complete and StructMembers() is pasted
> below. Let me know if you need any more info, like traces of other
> functions in the call chain.
>
> The major time consumer looks like:
>
> 21 130.867568 exe 'silent! keepj noautocmd ' . n . 'vimgrep /\t' . typename . '\(\t\|$\)/j ' . fnames

indeed, that is slow. I have no idea how to make this faster. This uses
Vims internal grep command and searches the tagfiles (fnames is the
result of the tagfiles() function earlier) for the typename. That sounds
wrong, because Vim has to load the file into a buffer, and do a regular
expression search for the pattern then.

I wonder if one could change this to a taglist() function call and add
the list to the quickfix list afterwards. I think this should be
possible, but I am don't know the tagsearch interface very well. I CC
Bram since he is the maintainer of that file and perhaps he can comment
:)

Another alternative to think of is, if you have installed ripgrep or ag
or another fast grep alternative, make use of that and do not use the
slower vimgrep alternative. So if you have:

`:set grepprg=rg\ --vimgrep\ --no-heading\ --smart-case` (I did a quick
google search for ripgrep and on how to make this work with Vim, so take
those arguments with a grain of salt)

and then replace that line:

exe 'silent! keepj noautocmd ' . n . 'vimgrep /\t' . typename . '\(\t\|$\)/j ' . fnames

with something like this:

exe 'silent! keepj noautocmd grep \b(?:'. typename . ')\b ' . fnames

would help? But that is just purely guessed.


Best,
Christian
--
Der Mensch ist erst wirklich tot, wenn niemand mehr an ihn denkt.
-- Bertold Brecht

[Pratyush Yadav]

Hi Tony,

On 01/04/20 07:26PM, Tony Mechelynck wrote:

Yes, the tags file is sorted and vim is built with +tag_binary and
'tagbsearch' is on. The tags file wasn't case-folded sorted, but I tried
with that too and I see similar performance.

Anyway, just to remove any potential confusion, jumping to tags via
'CTRL-]' is blazing fast. So is listing all alternatives with 'g]'. Does
ccomplete use the same mechanism for searching tags file as those two?
If so, then I wonder why it is so much slower.