iTranslated by AI
Returning to CtrlP
Introduction
When we talk about fuzzy finders for Vim, there are many options. Which one are you using?
- CtrlP
- fzf.vim
- denite
- vim-fz
- Not using a fuzzy finder, just netrw
- Not using a fuzzy finder, just NERDTree
- Not using a fuzzy finder, just dirvish
- Not using a fuzzy finder, just fern
- Others
There are many. Each has its own characteristics, and I believe everyone uses what they like. If you want to know the specific features of each, @yutakatay has written a great article, so please check that out.
First, let me tell you a story of the past
I originally used CtrlP. CtrlP is a Vim plugin developed by Mr. kien, a fast fuzzy finder implemented entirely in Vim script.
The surprisingly little-known convenient vim plugin "ctrlp.vim"
The Encounter
At the time, CtrlP was very snappy, and I fell in love with it at first sight. It contained many small hacks to achieve performance. A characteristic hack was the use of shortest keywords. In Vim script, you can omit the reserved words of commands. For example, the shortest keyword for the command function to define a function is fu. Since Vim script parses scripts sequentially, even a slightly shorter string makes the parsing faster, even if only by a tiny amount.
Mr. kien incorporated various other hacks as well, and I was very impressed by his stance of not including code that would make it slower. I also sent many patches to the GitHub repository kien/ctrlp.vim. At that time, Mr. kien was very active, and the number of users was growing rapidly.
The Parting
However, perhaps exhausted by the overly active issues, Mr. kien's activity gradually diminished, and eventually, he retired from development.
CtrlP, which had many fans, didn't have other maintainers; there was just an inactive development repository. Fearing this situation, a CtrlP user forked kien/ctrlp.vim and gave maintenance rights to several people who had been actively sending patches to kien/ctrlp.vim. That is ctrlpvim/ctrlp.vim.
And I was chosen as one of those maintainers.
Independence
I felt that I was the only one left to keep kien's ctrlp.vim running, so I continued to maintain it.
I made sure to maintain Mr. kien's style as much as possible. Of course, including the aforementioned shortest keywords.
However, implementing a fuzzy finder entirely in Vim script sometimes became an ordeal.
The Unclimbable Wall
To reiterate, CtrlP is implemented entirely in Vim script. Even though it's already a slow script interpreter, there were particularly problematic issues like:
- It takes time to list files when there are a large number of them.
- Filtering becomes slow when there are a large number of files.
The latter was particularly serious; in the worst cases, typing just one character would result in a wait of several seconds.
Seeing this unclimbable wall, some users switched to competing plugins.
And I, too, ended up switching.
vim-fz
The reason it becomes slow when there are many files is that it repeatedly goes back and forth between Vim, which is implemented in C, and the Vim script written by the user. CtrlP also provides a method to use external commands to list files, but once started, it remains unresponsive until all those large file lists are obtained.
So, I thought of a method using Vim's :terminal.
This method involves using a terminal command that lists files asynchronously and outputs the selected filename to standard output, launching it with Vim's :terminal, and using that command's output to provide the same interface as CtrlP.
Similar plugins include fzf.vim and others. This method certainly worked well. Even if there are tens of thousands of files, they are executed asynchronously, so the user doesn't have to worry about anything. I thought that I would probably continue to use vim-fz from now on.
The Few Milliseconds a Human Feels
However, while using vim-fz regularly or flirting with fzf.vim, there was one part I simply couldn't accept. It was the startup speed of the external commands.
vim-fz launches a command called gof, and fzf.vim launches fzf. To launch these commands, :terminal is used. A virtual terminal is prepared, a shell is launched within it, and then the external command is launched on that shell.
The time this takes is probably around a few milliseconds. This delay of a few milliseconds was something I simply couldn't forgive.
When you launch a fuzzy finder, you probably already have an idea of the filename you're about to open. What you want is the shortest key sequence to that filename. You want to type the characters that match the filename right now.
Whether the number of files is large or small, this startup time is always incurred.
Returning
This method isn't good either. Feeling that way, I tried other plugins as well. But I just couldn't be satisfied. Then, I suddenly recalled.
CtrlP was slow at filtering when typing characters, but for a small number of files, the screen appeared instantly.
That's natural. After all, the Vim process is already running, the Vim user interface is already prepared, and once the file list is displayed on the screen, all it has to do is wait for keys from the user.
Making CtrlP Faster
Well then, why not just make the filtering faster?
With that thought, I opened CtrlP's source files for the first time in a while. What's slow is listing files when not using commands. It searches directories recursively and creates a file list. Whether by chance or not, I had previously added a function called readdir to the Vim core, so I decided to try using it.
The initial implementation had various oversights and didn't become as fast as the capture in the link, but the GlobPath process for listing files became a few percent faster than the existing one.
master (d93d978): 8.49551 sec
readdir (8857c17): 7.33068 sec
This pull request actually includes fixes other than GlobPath. There was a heavy process in the logic that rebuilds the list according to the characters typed after CtrlP creates the file list. That was the function called mixedsort.
fu! s:mixedsort(...)
let ct = s:curtype()
if ct == 'buf'
let pat = '[\/]\?\[\d\+\*No Name\]$'
if a:1 =~# pat && a:2 =~# pat | retu 0
elsei a:1 =~# pat | retu 1
elsei a:2 =~# pat | retu -1 | en
en
let [cln, cml] = [ctrlp#complen(a:1, a:2), s:compmatlen(a:1, a:2)]
if s:ispath
let ms = []
if s:res_count < 21
let ms += [s:compfnlen(a:1, a:2)]
if ct !~ '^\(buf\|mru\)$' | let ms += [s:comptime(a:1, a:2)] | en
if !s:itemtype | let ms += [s:comparent(a:1, a:2)] | en
en
if ct =~ '^\(buf\|mru\)$'
let ms += [s:compmref(a:1, a:2)]
let cln = cml ? cln : 0
en
let ms += [cml, 0, 0, 0]
let mp = call('s:multipliers', ms[:3])
retu cln + ms[0] * mp[0] + ms[1] * mp[1] + ms[2] * mp[2] + ms[3] * mp[3]
en
retu cln + cml * 2
endf
mixedsort is a comparison function passed to the sort function. In other words, if there are tens of thousands of files, this function is called tens of thousands of times. I noticed that the function s:curtype() called within this function was taking dozens of milliseconds.
Therefore, I changed it to a method that uses the partial application feature introduced in Vim 8 to pass the pre-called s:curtype() to the function while using it.
As a result, even if there are tens of thousands of files, I was able to improve it to the point where it doesn't slow down.
ctrlp-matchfuzzy
CtrlP originally has a mechanism called a matcher. This allows you to speed up the part where file lists are filtered by using Python or other external commands. Essentially, it means delegating only the fuzzy matching part to something other than Vim script.
This was good in its own right, but it also involves loading Python or using external commands. I still couldn't accept the delay of several milliseconds that occurs when launching this matcher.
Fortunately, right around the same time, a built-in function called matchfuzzy() was added to the Vim core. This function takes a string array and a pattern string and returns an array of the fuzzy-matched results.
This function is almost as if it was prepared specifically for CtrlP.
Thinking so, I created a plugin to use this matchfuzzy() as a matcher.
And as it turns out, it is incredibly fast. That's natural, of course. It doesn't use external commands, and since it's a built-in Vim function to begin with, it's bound to be fast. There's no delay either.
I've already been using it for about 10 days, and no particular problems have occurred.
Conclusion
I encountered CtrlP, parted with CtrlP, and then returned to CtrlP again. I will continue to use CtrlP for a while. And I'm also thinking of gradually resuming my work as a maintainer for CtrlP. So as not to break Mr. kien's CtrlP.
Discussion