atom/fuzzy-finder

Improve performance when filtering large projects

Closed this issue · 18 comments

rafeca commented

Prerequisites

Description

fuzzy-finder is super laggy when filtering results for large projects. The UI gets blocked and the user experience is not great.

bad

Steps to Reproduce

  1. Open a medium to large repo from Atom (large repo: https://github.com/mozilla/gecko-dev).
  2. Open the fuzzy finder and start searching for some text.
  3. Realize the lag.

Expected behavior: the fuzzy finder UI should either update faster or we should add some kind of debouncing behaviour for large projects

Actual behavior: The filtering seems to be happening on each key stroke, and they get queued so when the user stops typing the filtering of previous key strokes is still being processed and it takes some time to "empty the queue".

Reproduces how often: Always for large projects.

Aerijo commented

Expected behavior: the fuzzy finder UI should either update faster or we should add some kind of debouncing behaviour for large projects

Would it be possible to instead / also run it on a different thread (or whatever gets executed independently of the UI)? Much like how VS Code extensions cannot directly impact the core editor's performance.

rafeca commented

Would it be possible to instead / also run it on a different thread (or whatever gets executed independently of the UI)? Much like how VS Code extensions cannot directly impact the core editor's performance.

Yup, running as many things as possible outside of the UI thread is the ideal solution (in fact this is how the fuzzy-finder crawls the files). For this specific scenario there are two things that we need to consider though:

  • If the filtering gets run on a different thread, we'll have to add logic to handle/limit the concurrency: the filtering would become an async operation so if you start typing c + co + con we have to make sure that if the filtering process for co finishes after the one for con we don't display the wrong results.
  • We have to check if the overhead of creating a new process (or Task in Atom land) for every filter operation doesn't impact much the speed to show results: from my experience the filtering takes <16ms on most projects and it's only on medium to large projects where it takes ~300ms-800ms (the problem is that these hundreds of ms get queued up on each key press and end up being a few seconds). The overhead could be mitigated by reusing the same process between filterings (but anyways we're going to have to serialize the array with all the project files in order to send it to the filtering process, which may take some precious time for big repos).

The ideal solution here would be to refactor the logic of the fuzzy-finder and make the filtering in the same process where the crawling happens: the crawler process could have some state (and even have a watcher to avoid #88), so it could also handle the filtering by itself. Unfortunately, at the moment I don't think that right now it's worth to invest in that solution (it involves a huge amount of changes) and I'd rather first implement simpler solutions that gives us 80% of the wins (like adding some kind of debouncer).

  • 👍1
maxbrunsfeld commented

This might be useful; it's what Nuclide uses for its fuzzy filtering stuff I think:

https://github.com/hansonw/fuzzy-native

rafeca commented

Interesting! I'll take a look at it but with my first experiments by adding a small debouncer the experience already gets much better, and the change will be much easier to implement:

Currently in master

bad

With a simpler debouncer (no change in filtering logic)

good

maxbrunsfeld commented

Debouncing would avoid the problem of the matching computation blocking keyboard input, but in my opinion this benefit doesn't outweigh the drawbacks:

  1. In the common case of a small repo, debouncing makes the fuzzy finder feel substantially slower and less responsive. This change would improve the perceived performance for large repos while harming it for many other small projects, by increasing the latency before results appear.

  2. Debouncing doesn't completely avoid the problem of computations blocking keyboard input - it just makes it occur less frequently. If you happen to type a key right after the debounce interval elapses, there's still going to be a long delay before your character appears.

We have to check if the overhead of creating a new process (or Task in Atom land) for every filter operation doesn't impact much the speed to show results:

If you use a background thread (as opposed to a separate child process), the overhead is almost zero. This is what we do for most other performance-sensitive background logic in Atom, like the async fuzzy matching that powers autocomplete, the async load and diff that we perform when a file changes on disk, and the async parsing that we do on every buffer change (if tree-sitter is enabled).

All of these modules perform computations (written in C++) on a background thread, exposing a Promise-based interface to JavaScript.

maxbrunsfeld commented

I thought that fuzzy-native module might be useful because it already works, and is written in C++ and supports multi-threading.

I just realized though that it works a little bit differently from the other native modules I mentioned: it still exposes a synchronous interface to JavaScript, using threads internally to speed up the computation. Ultimately, I think it'd be better to switch to an asynchronous interface, but that wouldn't require too big of a change to the module. Also, maybe the existing sync interface is good enough, depending on how fast it is.

rafeca commented

In the common case of a small repo, debouncing makes the fuzzy finder feel substantially slower and less responsive. This change would improve the perceived performance for large repos while harming it for many other small projects, by increasing the latency before results appear.

The debouncing logic can be easily configured based on certain threshold (based on number of files in the repo or the time it took last time to do the filtering): even if we have the filtering happening in a separate process having some smart debouncing would be beneficial in some scenarios (fast typing, old machines, etc), but yeah I agree that improving filtering performance it's desired.

Debouncing doesn't completely avoid the problem of computations blocking keyboard input - it just makes it occur less frequently. If you happen to type a key right after the debounce interval elapses, there's still going to be a long delay before your character appears.

You're right, and the only way to avoid blocking the UI will be to have a separate thread with state that handles the filtering (what you mention later). This will be the ideal solution but it also adds complexity and requires almost rewriting the fuzzy finder if we want to do it the right way (that's what I mention in the last paragraph of my first comment)... What I want first is to explore potential solutions that we can quickly implement and give us substantial improvements.

So I see two potential paths forward:

  1. Improve filtering perf AND/OR add debouncer (keeping the UI getting blocked).
  2. Avoid blocking the UI by rearchitecting the fuzzy finder.

I much prefer to go for 1, mostly because it's less risky... In order to do so I'll build a prototype using fuzzy-native and see how much better the experience gets and then reevaluate (hopefully switching fuzzy-native will give us good enough results 😄).

maxbrunsfeld commented

and the only way to avoid blocking the UI will be to have a separate thread with state that handles the filtering (what you mention later). This will be the ideal solution but it also adds complexity and requires almost rewriting the fuzzy finder

The ideal solution here would be to refactor the logic of the fuzzy-finder and make the filtering in the same process where the crawling happens

I don't think you'd necessarily need any coupling between fuzzy filtering and the crawling. In my opinion, the ideal solution wouldn't require any changes to the fuzzy finder's architecture. Instead, it would involve changing the underlying module, atom-select-list, which powers all fuzzy-filtered modal dialogs in Atom, not just the fuzzy-finder package. This way, every modal dialog in Atom would become faster.

I think you could change this method in the atom-select-list module to call some native fuzzyFilter method that uses Nan::AsyncWorker and returns a promise.

And, as you said, you'd need to add some JS logic to handle the async work (limiting the concurrency, updating the calling code to expect a promise, etc), but I would think that the overall architecture wouldn't need to change too much.

In order to do so I'll build a prototype using fuzzy-native and see how much better the experience gets and then reevaluate (hopefully switching fuzzy-native will give us good enough results 😄).

👍 Yeah, makes sense.

rafeca commented

I think you could change this method in the atom-select-list module to call some native fuzzyFilter method that uses Nan::AsyncWorker and returns a promise.

The problem about just plugging that method to some native code is that we would then need to pass pass the whole array of project folders to the native side, paying the serialization and deserialization costs, which are going to block the UI on each keystroke (at least during the serialization) even if the native code runs in a different thread.

We could work around that by having a native worker for each atom-select-list instance and instead of passing the list of items on each filter call, just pass them when constructing it and whenever some items change (this is approximately what fuzzy-native expects), but this will be a large breaking change on atom-select-list, so at this point I'd prefer to do an adhoc integration for the fuzzy finder.

Related to that, I'm gonna check what's the performance hit when using native-fuzzy caused by having to send all the project folders to native-fuzzy every time Atom gets re-focused.

maxbrunsfeld commented

just pass them when constructing it and whenever some items change (this is approximately what fuzzy-native expects), but this will be a large breaking change on atom-select-list

I would think you could make that change without affecting any public APIs on atom-select-list, but maybe I'm missing something.

In any case, I think you're right that just integrating it into fuzzy-finder is probably the best first step.

rafeca commented

Ok I have a prototype with native-fuzzy working, these are my overall impressions:

Good stuff

  • Very simple change.
  • Filtering performance gets dramatically improved on large projects.
  • Easy to integrate at the moment (there are pre-built binaries).

Concerns

  • Introduces a quite noticeable regression on the time it takes to appear the fuzzy finder for large projects (it's around ~800ms). This is caused by the time it takes to pass the array of folders to the native fuzzy finder which has to process them, and it happens every single time the fuzzy finder is opened, since a new instance of the items array is always passed 😢.
  • The latest version of native-fuzzy is only available as part of nuclide-prebuilt-libs, which contains other native utilities. This increases the size of Atom by ~12MB (5MB gzipped), since it contains prebuilt binaries for many platforms. As a comparison, the compiled binary for native-fuzzy is ~30KB for darwin and ~188KB for win32.

To overcome the second issue, we can create a bridge package that downloads the appropriate binary on the postinstall phase from their release assets (as we do for ripgrep), or that it has nuclide-prebuilt-libs as a submodule and builds the appropriate binary during install (as we do for git-utils).

Overcoming the first issue is going to be more challenging... there may be an easy way to avoid calling setItems every time that the fuzzy finder window gets opened but the edge cases caused by the async logic on the fuzzy finder are crazy to debug, I'll take a look.

Perf comparison

The benchmarks show really impressive performance improvements when filtering, and makes the experience quite good even for large projects.

The regression when opening the fuzzy finder is slightly noticeable on medium projects and quite bad on large ones.

Type of project master native-fuzzy Perf improvements Regression when opening
Small 10-24ms 1ms 👍 17X faster 👎 4ms
Medium 25-160ms 1.5-9ms 👍 17X faster 👎 60ms
Large 400-1800ms 20-73ms 👍 22X faster 👎 800ms

For the benchmark I've configured native-fuzzy to use a single thread. When using 4 threads the time to filter improves by ~2-3X on large projects but stays almost the same for medium/small.

Next step is to figure out if we can easily solve both concerns. If that's the case this is going to be a great win 😄

maxbrunsfeld commented

The latest version of native-fuzzy is only available as part of nuclide-prebuilt-libs, which contains other native utilities.

It looks like the latest release is also published on npm, so you probably don't need a bridge package; I think you can just add fuzzy-native to the package.json directly. We don't necessarily need pre-built binaries for Atom; we already compile a lot other native modules from source as part of our builds.

maxbrunsfeld commented

Introduces a quite noticeable regression on the time it takes to appear the fuzzy finder for large projects (it's around ~800ms)

😬 Yeah, that's pretty long. I guess that's this AddCandidates() call? Two thoughts:

  • Is it possible to avoid creating a new Matcher if this.items hasn't changed?
  • Maybe you could add an async buildMatcher(candidates) factory function that constructs the Matcher on a background thread and returns a Promise that resolves with the Matcher. Or alternatively, and async addCandidates instance method. Then you could call that function immediately after the FS crawl (even before the user opened the fuzzy finder) so the matcher would often be ready when they did open it.
rafeca commented

It looks like the latest release is also published on npm, so you probably don't need a bridge package; I think you can just add fuzzy-native to the package.json directly. We don't necessarily need pre-built binaries for Atom; we already compile a lot other native modules from source as part of our builds.

The latest publish of the fuzzy-native npm package is from november 2016, while the one in nuclide-prebuilt-libs was published this January.

It seems like the first commit of nuclide-prebuild-libs/fuzzy-finder is the last commit of the old fuzzy-finder repo (based on the commit message). There have been 32 new commits on the nuclide-prebuild-libs, some of them seem to not be much relevant but others are bugfixes... I wonder how important they are though...

Is it possible to avoid creating a new Matcher if this.items hasn't changed?

We would have to do a diff between the old and the new, it's possible but that would still be O(n) (though probably much faster).

Maybe you could add an async buildMatcher(candidates) factory function that constructs the Matcher on a background thread and returns a Promise that resolves with the Matcher. Or alternatively, and async addCandidates instance method. Then you could call that function immediately after the FS crawl (even before the user opened the fuzzy finder) so the matcher would often be ready when they did open it.

I think I found a way to modify the current logic of the fuzzy finder to not require to reset the paths every time it gets shown... this seems to improve a lot the user experience (the UI would still get blocked for 800ms when there's a file change or the Atom gets refocused, but the experience will be much better than now). I'll post some screen recordings with the different approaches tomorrow

  • 👍1
rafeca commented

With #373 I've ben able to mitigate the regression caused by the slowness of setItems

You can check a comparison between master, a naive fuzzy finder implementation and a fuzzy finder implementation with #373 applied:

demo

Next step is to address the second concern around file size caused by the precompiled binaries

  • ❤️2
rafeca commented

To overcome the second concern I'm gonna start using the fuzzy-native npm package instead of the nuclide-prebuilt-libs one, even if it does not currently contain the latest fixes...

Maybe @hansonw or @zertosh can give us access to https://github.com/hansonw/fuzzy-native and the npm package so we can do the backport of the commits from nuclide-prebuilt-libs if it's not maintained anymore (hey guys!! 👋)

rafeca commented

Closing this issue since this has already landed to atom@master

hansonw commented

Hey @rafeca - it's exciting to see that you got it to work in Atom! Sorry I missed your comment earlier.
I haven't had the chance to maintain the standalone repo so forking sounds good :) It'll have a much better home in the 'atom' repo anyway.

If you have some time I would strongly recommend backporting all the commits from https://github.com/facebook-atom/nuclide-prebuilt-libs/commits/master/fuzzy-native (these are all newer than the version in my repo.) Let me know if licensing prevents this for some reason and we can figure something out.

There are some bugfixes as well as significant perf improvements. I wouldn't be surprised if you saw a 2x speed boost (especially from the min_score and bitmask optimizations.)