Benchmarking

[LiamKearn]

I could have sworn there was some sort of benchmarking vs other plugins at some point in that past?

Lately fff.nvim has popped up (making pretty bold claims imo) and I'd be interested in how it stacks up given how greenfield it is.

[wincent]

I never collected or published actual benchmark numbers, because every time I ever stress-tested another fuzzy finder by pointing it a very large monorepo it was obviously slower. People would say "X is fast", but that just shows to me that they are using it on a smaller repo than the kind I work in. If that's their use case, then fine, they can use whatever they want. 😁

Instead, I focused on benchmarking Command-T against itself, so I could measure improvements over time. You can see this in my commit messages, where I paste the results of running bin/benchmarks/matcher.lua and they show the performance delta before and after the change along with a p value to indicate the statistical significance of the change. See a commit like this one for an example:

Here are the full benchmark results at `chunk_size=64`,
relative to the baseline before this commit:

    Summary of cpu time and (wall time):

                        best    avg      sd      +/-      p     (best)    (avg)      (sd)      +/-      p
         pathological 0.20668 0.21656 0.06613  [-0.5%]        (0.20668) (0.21657) (0.06607)  [-0.5%]
            command-t 0.16608 0.17331 0.05442  [-0.8%]  0.005 (0.16608) (0.17333) (0.05438)  [-0.7%]  0.005
    chromium (subset) 1.33381 1.34116 0.02801 [-11.9%] 0.0005 (0.28610) (0.29204) (0.01362)  [-6.5%] 0.0005
     chromium (whole) 1.11411 1.11723 0.01549 [-27.4%] 0.0005 (0.12261) (0.12580) (0.00886) [-23.0%] 0.0005
           big (400k) 1.67405 1.68004 0.02904 [-33.4%] 0.0005 (0.18104) (0.18354) (0.00748) [-29.1%] 0.0005
                total 4.50370 4.52830 0.09764 [-22.7%] 0.0005 (0.97287) (0.99130) (0.10292) [-10.4%] 0.0005

Here we see a highly significant improvement (p-value of 0.0005) in both
average CPU time (33.4%) and averaged wall clock time (29.1%) for the
big test case. As expected, for small workloads the improvement is
smaller but still beneficial. Overall across the mixed workloads the
average CPU time improves by 22.7% and the average wall clock time
improves by 10.4%.

Having said that, I wouldn't be averse to publishing results compared to other fuzzy finders if I could figure out a way to do it reliably and without too much maintenance. FWIW, I wasn't aware of dmtrKovalenko/fff.nvim but I had heard of the fuzzy matcher it's using, saghen/frizbee, which is notable because it does truly fuzzy (ie. typo-resistant) matching, uses SIMD to go fast, and is written in Rust. Having not used it myself, I would expect that it is probably not as fast as Command-T because it is not an apples-to-apples comparison: it is solving a different problem (ie. typo-resistant matching).

I am curious to know how it performs though, so I did a git clone of fff.nvim just now and gave it a shot; here are my findings.

cargo build --release dies with errors:

   Compiling neo_frizbee v0.6.0
error[E0554]: `#![feature]` may not be used on the stable release channel
 --> /$HOME/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/neo_frizbee-0.6.0/src/lib.rs:2:1
  |
2 | #![feature(avx512_target_feature)]
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: remove the attribute
  |
  = help: the feature `avx512_target_feature` has been stable since `1.89.0` and no longer requires an attribute to enable

error[E0554]: `#![feature]` may not be used on the stable release channel
 --> /$HOME/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/neo_frizbee-0.6.0/src/lib.rs:3:1
  |
3 | #![feature(portable_simd)]
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0554]: `#![feature]` may not be used on the stable release channel
 --> /$HOME/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/neo_frizbee-0.6.0/src/lib.rs:4:1
  |
4 | #![feature(get_mut_unchecked)]
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

   Compiling icu_provider v2.0.0
For more information about this error, try `rustc --explain E0554`.
error: could not compile `neo_frizbee` (lib) due to 3 previous errors
warning: build failed, waiting for other jobs to finish...

So I gather it relies on unstable Rust features that require a nightly Rust... Temporarily installed that now and got a working build, but then I face this:

E5108: Error executing lua ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:53: attempt to perform arithmetic on field 'width' (a nil value)
stack traceback:
        ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:53: in function 'create_ui'
        ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:953: in function 'open'
        ...l/.config/nvim/pack/bundle/opt/fff.nvim/lua/fff/main.lua:424: in function 'find_files_in_dir'
        ...l/.config/nvim/pack/bundle/opt/fff.nvim/lua/fff/main.lua:279: in function 'find_in_git_root'
        [string ":lua"]:1: in main chunk

when trying to run :lua require('fff').find_in_git_root(). Looks like I need a setup call first:

require('fff').setup({})

And finally I can try it and the verdict is... noticeably laggy compared to Command-T, at least in the repo I'm testing this in (150K files). This is a proprietary repo though, so I can't share a video of it, so let me clone something big and record a quick screencast... Linux has only 85K files in it, so let's go with Chromium instead (470K files).

In the following screen recordings, I am using fff.nvim in the top split, and Command-T in the bottom one.

Scanning (ie. opening Neovim and opening the fuzzy finder)

Gr7nby3T.mp4

Holding down e and then holding down delete

6d9zQzAo.mp4

FWIW, the errors you see when using fff.nvim are:

Failed to search files: bad argument #1: error converting Lua string to String (invalid utf-8 sequence of 1 bytes from index 85)
stack traceback:
        [C]: in ?
        [C]: in function 'pcall'
        ...im/pack/bundle/opt/fff.nvim/lua/fff/file_picker/init.lua:95: in function 'search_files'
        ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:390: in function 'update_results_sync'
        ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:373: in function 'on_input_change'
        ...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:284: in function <...nfig/nvim/pack/bundle/opt/fff.nvim/lua/fff/picker_ui.lua:284>

Typing characters from a file name

In this instance, I am trying to open ios/chrome/browser/unit_conversion/model/unit_conversion_service_factory.h, so I open the fuzzy finder and type "unitconvservfact" (I made a typo first in fff.nvim, but the lagginess made it feel quite difficult to correct it):

V365pNUi.mp4

Not sure if it is debouncing my input or just slow to update. I think the typo illustrates an important difference between the two tools:

• When I typed "unitconvrsevfact", it still showed me a bunch of results. The one I really wanted wasn't the top-ranked hit, but it was a few entries away from the top-ranked hit. Arguably, with a busy UI like that and a bunch of files showing, the fuzzy match isn't going to help you much in a huge repo; it's always going to be quicker to correct your typo than it is to scan the list and find the item you were actually looking for.
• Command-T expects you to be precise with your input: if you enter it correctly, it will show you exactly what you are looking for, and nothing else. It rewards precision, and as part of the deal, it promises to be responsive.

I think you can tell which trade-off I prefer, but you probably already knew that... 😁

---

So, yeah, as I said above, this is not an apples-to-apples comparison, because the tools are doing different things¹. This little test session is enough for me to know which tool I prefer to use, because I value responsiveness and relevance above all else, but I'd still be happy to add actual numerical benchmarks if the set-up and maintenance costs weren't too high.

Footnotes

1. The main difference I'm focusing on here is the fuzzy (typo-resistant) matching. fff.nvim also shows a preview window, but Lua is fast, so I don't think that's a major contributor to the lagginess (another Lua plug-in I made shows a preview window, so I know it can be fast). The other fact at play here is that it looks like fff.nvim tries to do async scanning, and maybe other things async as well (I don't know). Async UIs are one of those things that sound good in practice, but it's actually quite hard to pull them off, as seen in the videos above: in my experience, it's far better to just make your sync operations fast enough that you can leave them sync, and for the repo sizes I'm working in, that's a viable option for now. ↩

[LiamKearn]

Thanks heaps for the in-depth reply and excellent maintenance of this project :)

I'm also a fan of the precision for speed tradeoff that command-T provides. I'm not working at massive scales atm but I weirdly find myself :wqing, re-invoking vim from the shell and using command-T to get back to a single file during debugging. I sometimes find it's just easier than c-z -> fg shell job management (which is what I use for longer editing sessions / bigger repositories) because it's so fast when you're precise. Despite all the tooling vim provides for searching/editing/generally-working-with open buffers I also like to keep a clean slate there so this workflow helps!

fff.nvim is new so it seems it's doesn't have the option to disable the typo resistance which frizbee mentions it has yet. Also seems to go through neo_frizbee which I didn't really look into.