IntelliSense filtering has become slow again in huge lists

[Wosi]

Copied from the inital issue (https://github.com/Microsoft/vscode-extensionbuilders/issues/80)

Let's see this scenario:

• The cursor is placed on whitespace inside a method
• The user asks for completions by pressing CTRL + Space
• The language service is being asked to provide all suggestions
• The suggestion box pops up containing all 20k symbols
• The user types the character f
• VSCode hangs for ~8 seconds until the letter is displayed and the suggestion box shows only suggestions containing an f. (VSCode doesn't ask for suggestions twice. All the time is spent outside the language service. )
• typing the next letter is being processed faster but it's still slow.

@joaomoreno fixed this issue on 2015-11-06 telling that there were too many event listeners. With the December update it has become slow again. VSCode hangs now for ~10 seconds working on the same suggestion list.
I really hope it's going to be fast again with the January update. It's not funny to work in huge projects now.

[joaomoreno]

I can't really reproduce the 10 second hang on a 20k suggestion filter, but I do see some slowness. More like 1-2 seconds here.

[Wosi]

May be it has something to do with the camel case smart search? I face the slowdowns with OmniPascal (case insensitive language and all symbols use PascalCase or UPPER_CASE).

With JavaScript I can reproduce it with a hang of ~5 seconds using the following file: https://gist.github.com/Wosi/0487f72965a26de07c92

See the instructions in the comments. The speed of filtering depends strongly on the typed characters. Filtering for "2" is very slow in this case.

[joaomoreno]

Excellent, I can now reproduce, thanks for the sample!

[Wosi]

Here is a much slower real world example: https://gist.github.com/Wosi/9603b02b0fc4268abc16
It causes a hang of ~14 seconds on my machine.

[alexdima]

This is almost blocking my selfhosting:

Here I am typing "_updateMatchesCount". The suggestion list is empty after the first 2 characters and still it eats so much time.

[alexdima]

Here is a saved profile
CPU-20160125T170756.cpuprofile.txt

[joaomoreno]

We might have to move from localeCompare(label, otherLabel) to label < otherLabel ? -1 : 1 for comparisons.

[joaomoreno]

Did a bunch of optimisations:

• moved the sorting and filtering out of the tree and into the model
• dropped localeCompare in favour of < and >
• moved cleanup of suggestions to happen on hide instead of show
• added a heuristic on whether the diff algorithm should run
• added another heuristic on whether the diff algorithm results should be used at all
• cached the previous list of suggestions for quicker narrowing down
• tightened the heuristic for camel case suggestions

@Wosi it would be cool if you could give it a try, building from our sources. Both your examples take just under 1 second on my machine now.

I have a few more ideas of how to make this faster, by dropping a lot of the tree machinery and just implementing a virtual list, but this'll do for now.

[alexdima]

Thank you, can't wait to try them out ❤️

[Wosi]

@joaomoreno First of all: Thank you! When the real world example runs in under a second then it's a powerful improvement. Unfortunately I can't build VSCode from source and check it against the real world project until wednesday evening. Since the insider channel will be updated tomorrow I think it's better to test against the insider build, isn't it? I'll give you feedback as soon as possible!

P.S: The real world example is a full adaptation of the completion items I receive from the OmniPascal language service to JavaScript. So it's a good indicator when it works nicely now.

[joaomoreno]

@Wosi sure, let's do that then!

Here are my results on the real world example, when triggering Intellisense and then typing abcde.

The first peak is the trigger and takes 526ms. Second peak is the a and takes 886ms. Third peak is the b and goes for 543ms. The rest of the letters are pretty much instant.

[dbaeumer]

With the test case from #1923 (comment) I see a ~ 1 second delay

[Wosi]

Sorry, I wasn't able to setup a proper dev environment in order to build VSCode on my own.
I see a ~ 1 second delay with the insiders build, too.

Thanks a lot! it's a big improvement even though it's still not working fluently.

[joaomoreno]

@Wosi I'm currently working on a separate widget implementation for this. 👍

[joaomoreno]

Given the changes in #2702, here are some updated results: 237ms for the trigger, 86ms for the first letter (a), 29ms for the second (b), etc... 👍

[Wosi]

Awesome! Good job, @joaomoreno!

[nrj]

I'm still seeing really long load times on version 1.0.0 when using as my external editor for Unity. For example triggering IntelliSense via hotkey with my cursor at the end of Mathf.Clamp takes 8 seconds to offer me suggestions. Consecutive invocations don't immediately get faster.

[dbaeumer]

@joaomoreno moving back to you to response to additional comments.

[nrj]

Even a variable in the same scope takes ~5 seconds of loading.

[Wosi]

@nrj Your screenshot shows the initial loading process for code completion which is handled by a plugin. VSCode's internal code completion filtering (= the topic of this ticket) takes place after the plugin has delivered the suggestion items. The bahviour you are facing seems to be an issue of the plugin which provides the code completion (I guess it's OmniSharp).

[joaomoreno]

Thanks @Wosi, you are absolutely right.

@nrj You should file an issue to the page of the extension which provides those suggestions.