Use `fuzzy-native` as an alternate scoring system

rafeca commented 5 years ago

Description of the Change

This PR does two things:

Renames the useAlternateScoring config option to convert it to an enum called scoringSystems (using the same default value as before).
Adds a new scoringSystem called fast (🤷‍♂️) which uses fuzzy-native to dramatically improve filtering times on large projects.

Alternate Designs

A few other options have been considered:

Adding a debouncer without changing the current filtering logic.
Keep the current filtering logic but move it to an async Task.
Use the nuclide-prebuilt-libs package instead of fuzzy-native.
Create a new package with the fuzzy-native filtering logic executed in a background thread.

At the end, this solution is what IMHO gives more benefits and less tradeoffs per unit of effort 😅

For more information about benefits/tradeoffs, check out the discussion on the applicable issue.

Benefits

Drastically faster filtering for large projects, which are now usable.

Type of project	master	`native-fuzzy`	Perf improvements
Small	10-24ms	1ms	👍 17X faster
Medium	25-160ms	1.5-9ms	👍 17X faster
Large	400-1800ms	20-73ms	👍 22X faster

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.

demo

Possible Drawbacks

Yet a new scoring system added. As a follow-up we may decided to remove the standard scoring system, which was superseeded by the alternate one 3 years ago.

Applicable Issues

https://github.com/atom/fuzzy-finder/issues/370

rafeca commented 5 years ago

uhm, appveyor shows failures due to python2 not being available on they vms... Investigating

rafeca commented 5 years ago

Ok, I've been able to build and use fuzzy-native locally on a Windows machine, but I found two things:

npm install on fuzzy-finder does not generate the correct binary on windows. I had to run apm install to be able to generate the correct one (for electron).
The package is not prepared to read binaries generated for electron 2.0 (more info: https://github.com/hansonw/fuzzy-native/blob/master/lib/main.js#L10-L11).

I think that both issues are related with the fact that the package is not prepared for electron v2.0.

I'm not sure if this is related to the issue that's happening on AppVeyor (I don't think so).

50Wliu commented 5 years ago

npm install on fuzzy-finder does not generate the correct binary on windows. I had to run apm install to be able to generate the correct one (for electron).

This is expected; apm install should always be used for installing Atom packages.

EDIT: Oh, and the python2 error is a red herring; the fallback is at C:\Python27\python.exe, which works.

50Wliu commented 5 years ago

Try adding image: Visual Studio 2015 to appveyor.yml

rafeca commented 5 years ago

This is expected; apm install should always be used for installing Atom packages.

Oh interesting, I still have to learn a lot about Atom 😅

Try adding image: Visual Studio 2015 to appveyor.yml

I'm gonna try, thanks!

rafeca commented 5 years ago

Ok, that fixed the issue 😄

Now the remaining issue is the one caused by these lines: https://github.com/hansonw/fuzzy-native/blob/master/lib/main.js#L10-L11

rafeca commented 5 years ago

Ok, using a fork that adds support for electron v2 we're able to run the tests (only that 2 of them fail 😅), I'm gonna try to reproduce the failures on my windows machine (on OSX all of them pass)

We're making progress!

rafeca commented 5 years ago

Yay! AppVeyor builds are finally passing 😄 There was a test that didn't contain correct Windows paths and it didn't work well with the path transformations that the logic for fuzzy-native does 😅

rafeca commented 5 years ago

For some reason Travis builds get queued forever: https://travis-ci.org/atom/fuzzy-finder/builds/512728958?utm_source=github_status&utm_medium=notification ... I'll check back tomorrow

rafeca commented 5 years ago

I've forked fuzzy-native to https://github.com/atom/fuzzy-native and created a @atom/fuzzy-native package with v0.7.0 that just contains the fix for electron v2.

It seems that npm caching logic is not super smart and the package cannot be found yet from CI systems... I'll wait some time and retrigger the build.

I'll also set up a similar CI system that the original fuzzy-native package has (again, I cannot do it now since Travis cannot find the new GitHub project yet)

rafeca commented 5 years ago

Ok, after a few retries all tests passing, I'm proceeding to merge this PR 🙏

atom / fuzzy-finder