Performance profile

[liuchengxu]

To fix the performance issue, ensure you have Rust installed on your system and run :call clap#helper#build_all().

---

Introduction

The one selling point of vim-clap is in pure vimscript, having a good platform compatibility and minimal pain to set it up, which is apparently an advantage. However, it becomes a disadvantage when you do a large scale searching/filtering job for the limit of vimscript language.

Profile of async job at scale

For instance, using :Clap files from my home directory and input sr, the result is [791970/823172]. The following profile info is based on this commit dfffb5e.

Profile of NeoVim:

FUNCTIONS SORTED ON TOTAL TIME
count  total (s)   self (s)  function
16737   2.416528   0.592996  <SNR>181_on_event()
16732   1.816953   0.267504  <SNR>181_append_output()
16731   1.505205   0.146196  <SNR>181_set_matches_count()
16732   1.379571   0.310434  clap#impl#refresh_matches_count()
16732   0.821710   0.141712  clap#indicator#set_matches()
16732   0.679998   0.317742  <SNR>183_apply_indicator()
    3   0.492807   0.472198  <SNR>172_on_event()
16732   0.362257   0.177423  <SNR>183_padding()
16733   0.247077   0.140285  clap#sign#reset_to_first_line()
    8   0.195782             provider#python3#Call()
16740   0.184996   0.100084  16()
    5   0.147412             UltiSnips#TrackChange()
16732   0.106776             <SNR>184_sign_of_first_line()
16740   0.084913             clap#util#nvim_buf_get_first_line()
    3   0.078762   0.000110  clap#handler#on_typed()
    2   0.078562   0.003062  41()
    2   0.075139   0.000245  clap#impl#on_typed()
    5   0.067303   0.000438  clap#rooter#run()
    2   0.063340   0.004730  <SNR>179_on_typed_async_impl()
    2   0.052697   0.000056  clap#dispatcher#job_start()

Profile of Vim:

FUNCTIONS SORTED ON TOTAL TIME
count  total (s)   self (s)  function
1613221  70.847359  38.246657  <SNR>172_out_cb()
1613224  31.405335  18.249628  clap#job#vim8_job_id_of()
1613229  13.155912             clap#job#parse_vim8_job_id()
791899   1.191679             <SNR>172_handle_cache()
    1   0.537275   0.517298  <SNR>167_close_cb()
   61   0.183191   0.007911  ElelineGitBranch()
   60   0.170001   0.154896  FugitiveExtractGitDir()
   18   0.021677   0.001292  <SNR>162_popup_filter()
    2   0.020385   0.000444  142()
    3   0.020079   0.019061  clap#impl#refresh_matches_count()
    1   0.019937   0.000054  <SNR>167_on_complete()
    2   0.019428   0.000085  <SNR>162_apply_input()
    2   0.019320   0.001760  117()
    5   0.018673   0.001056  clap#rooter#run()
    2   0.016882   0.000210  clap#impl#on_typed()
   10   0.014478   0.003716  traces#init()
    2   0.014044   0.000092  <SNR>172_post_check()
    2   0.013604   0.000199  <SNR>172_on_exit_common()
    2   0.013177   0.000034  clap#impl#add_highlight_for_fuzzy_indices()
    2   0.013143   0.010832  <SNR>170_apply_add_highlight()

For the result set having about 1M items, neovim is still tolerable if you seldom run into that case, but for vim it's totally unusable. The core idea of vim-clap is to spawn a new job on your typing and then react on the callback, the callback of the job is called too many times on the surface.

Related providers

The performance issue only happens to these providers that can have a huge result set.

Searching

• :Clap files
• :Clap grep

Filtering

The current strategy is to use the built-in fzy written in python running synchronously when the items are no more than 10,000, switching the async way if it's more than the threshold and then it meets the same callback issue.

• :Clap blines
• :Clap lines
• :Clap bcommits
• :Clap commits

The challenge is to make clap#filter#() fast enough even when candidates is terrific.

vim-clap/autoload/clap/filter.vim

Line 164 in 77631c1

function! clap#filter#(query, candidates) abort

Possible solution

• python multi thread. Since we have introduced the optional dependency for the built-in fzy support, we could also use the thread of python to improve the performance as suggested in Plugin hangs when Cmd files in executed from $HOME CWD #75 (comment). As I'm not a python expert, I'm not sure if this will land in vim-clap eventually.

• lua. Could be faster than vimscript at least in some filtering cases. I observe something promissing based on the this script measuring the vimscript with the other script languages:

  • lua is 4x faster than python.

  • luajit is 100x faster than python.

• Boost python filtering using Rust. I'm interested if https://github.com/rochacbruno/rust-python-example would help, which can replace fuzzy_match():

  vim-clap/pythonx/clap/fzy.py

  Line 9 in f4d280c

  def fuzzy_match(query, candidates):

  The result shows that using Rust could be 10x faster, see Speed up the Python filtering using Rust #146, 10X faster filtering by speeding up Python using Rust #147.

• job

  • [-] Use a timer for reading the output of vim job periodly, then the callback won't be called that many times. This branch is my try with timer. Using a timer helps a lot, but some messages are dropped unexpected, not sure if that's bug of Vim or my code. I did not investigate further as I have achived the same goal with maple as follows.
  • Don't have to output all the fuzzy filtered items, we only show the top N candidates and care about the number of total candidates. The payload of async job will be significantly decreased if only these essential information is returned.(Only return the neccessary info using maple --number option #181)

[issue-label-bot]

Issue-Label Bot is automatically applying the label feature_request to this issue, with a confidence of 0.65. Please mark this comment with 👍 or 👎 to give our bot feedback!

Links: app homepage, dashboard and code for this bot.

[gitbugr]

Glad to see you addressing the slowness. Perhaps take a look at fzf.vim, as I use neovim and experience slowness with both vim-clap and LeaderF

[liuchengxu]

I would say it's not appropriate to compare fzf.vim with vim-clap in this performance improvement perspective, for fzf.vim essentially does not handle the logic itself but invokes the go binary fzf instead. You can't just talk about fzf.vim as it won't work without fzf. The core logic and heavy tasks are processed by the external program fzf not by the vim plugin fzf.vim. That's not the way of vim-clap.

Edit: The author of fzf.vim junegunn clearly indicates the distincition between fzf.vim and the other similar plugins(vim-clap, Leaderf) in junegunn/fzf.vim#821 (comment) and vim/vim#4063 (comment):

fzf is not a native Vim plugin but an external TUI program you can run on your shell and the Vim plugin for fzf is a just thin wrapper that starts an fzf process in a terminal buffer and lets the users "interact" with the program.

I suggest you sticking to the combination of fzf and fzf.vim if you are sensitive about the speed, especially if you are using neovim mostly(fzf.vim already can work with neovim's floating window).

Edit: From the response of Bram in vim/vim#4063 (comment), I believe fzf.vim will support the vim popup eventually. In a word, if you are happy with fzf/fzf.vim, no need to play with the other alternatives then, it's great enough in most cases.

Although I'll continue to optimize vim-clap, I don't think vim-clap has a chance to make people feel faster than fzf.vim. That would not work in theory.

[gitbugr]

I suggest you sticking to the combination of fzf and fzf.vim if you are sensitive about the speed

I'm not "sensitive" about speed. However I get a little annoyed when I can't even finish typing what I'm trying to search for, without an unreasonable amount of lag. I would at least expect it to debounce (wait for a small bit and give the user a chance to finish what they were typing before executing the search) rather than my cursor freezing on each character typed. (this is only the case for large amounts of files.)

The core logic and heavy tasks are processed by the external program fzf not by the vim plugin fzf.vim. That's not the way of vim-clap.

While I won't argue that it shouldn't, if that's what you're going for. I'm not sure why. vim-clap does offload "the core logic and heavy tasks" in the case of Clap grep/files. You depend on fd/rg/find/etc. And you optionally support a python implementation, as well as rust for fuzzy finding. Why have you chosen to stop there?

[liuchengxu]

wait for a small bit and give the user a chance to finish what they were typing before executing the search

This is an input delay for vim popup, see :h g:clap_popup_input_delay. Maybe neovim also needs one?

vim-clap does offload "the core logic and heavy tasks" in the case of Clap grep/files.

This is not accurate.

• Clap grep uses the async job only. The Rust extension does not help Clap grep.
• The core logic includes the data collection(gather the output of other external command like rg), do the fuzzy filtering at scale and display the result in real time. What vim-clap delegates to Rust by far is the filtering only. As you can see the profile, gathering the output of async job of vim is the bottleneck.

You depend on fd/rg/find/etc.

This is not the point. Every finder needs these tool to produce the data.

Why have you chosen to stop there?

Even I am not against using Python to improve the performance, I won't write another complete stand-alone binary otherwise it is reinventing the wheel fzf. vim-clap can always work without any extra dependency. Without the optional Python and Rust, it's just a bit slower, missing the advanced fuzzy filtering.

[gitbugr]

This is an input delay for vim popup, see :h g:clap_popup_input_delay. Maybe neovim also needs one?

I had tried that and it didn't seem to help. If this disabled for neovim, I'd assume, yes?

This is not the point. Every finder needs these tool to produce the data.

I'm not sure what the limitations of vimscript are, but sure. Which is exactly my point. Drawing an arbitrary line between what is and isn't okay to offload to an external program because "That's not the way of vim-clap." is a little... counter-productive.

otherwise it is reinventing the wheel

But you are already "reinventing the wheel", no? Which is fine, but if your goal is optionally offloading for performance, why python? Why not allow offloading to fzf, or lotabout/skim if you want to go down the rust route?

[liuchengxu]

If this disabled for neovim, I'd assume, yes?

This no input delay option for neovim as neovim keeps usable on my machine, even with 1 million files. Neovim also needs a similar input delay then.

Why not allow offloading to fzf, or lotabout/skim if you want to go down the rust route?

Checkout the externalfilter feature of vim-clap, if that is what your so-called offloading. It's already supported. But using the external filter has to rely on the async job feature of Vim/NeoVim, and I have said the drawback of job in my post, see Problem of using job of Vim/NeoVim of section.

I'm not sure what the limitations of vimscript are

Well, see the profile above ..., and the related discussion, such as #75.

That's not the way of vim-clap." is a little... counter-productive.

By the way of vim-clap, I actually mean I don't want vim-clap can't work without some external binary. Without fzf, fzf.vim won't work. That's the difference. vim-clap is able to always work without any other dependency, even it could be a bit slower.

[ImmemorConsultrixContrarie]

The current strategy is to use the built-in fzy written in python running synchronously when the items are no more than 10,000, switching the async way if it's more than the threshold and then it meets the same callback issue.

Most python interpreters use GIL. CPython uses it too and CPython is a most used Python interpreter. In short, GIL makes any python multithreading slower; and when I say "slower" I mean "it makes it single threaded and then slows it down more with all this thread-to-thread jumps". And async python code with GIL is even more slower than simple multithreaded. Though, if python code invokes some non-python library, this library's work won't be GILed. It could even run in standalone mode concurrently with the python script if invoked function won't return any data back to script, IIRC.

So, yeah, python script should be either single-threaded and straightforward, or use non-python libs, to be fast.

[liuchengxu]

In short, GIL makes any python multithreading slower; and when I say "slower" I mean "it makes it single threaded and then slows it down more with all this thread-to-thread jumps". And async python code with GIL is even more slower than simple multithreaded.

Not a Python expert and I have not written any Python multithreading code,but that's ok as long as the multi-threading won't slow Vim/NeoVim down, keeping it well responsive.

---

Actually don't have to use python or lua, the performance issue of async job(callback overhead) will be resolved eventually as we could always move the heavy part into the maple Rust extension. Like #181, the overhead of async job callback has been decreased significantly.

However, as I have mentioned in section: Problem of async job of Vim and NeoVim, the redraw issue of async job still persists(it's basically unavoidable I think). But it's more like an user experience problem, not a performance issue, at least Vim/NeoVim can keep responsive anyway.

So I still want the built-in sync filter to be faster, that's why I made fuzzymatch-rs as it does not have the redraw issue of async job.