Open Symbol in Workspace is far slower than it should be

[gspencergoog]

I've recently switched from using IntelliJ to VSCode as my full time Flutter editor, and the main thing I've noticed is that the searches for symbols are incredibly slow, when they work at all.

Often, I'll hit Ctrl-T/Cmd-T, and start typing, as I used to do with the "double-shift" from IntelliJ, and it sometimes quickly populates results for the "#" (which makes no sense, really), and then results for the first one or two letters of the search, but by the time I've completed typing the symbol I want to find, it just goes into the weeds waiting.

It will also sometimes just refuse to find a symbol that I know exists: if I let it sit there thinking for 5 minutes, it's still thinking (to make matters worse, I can't just go read email or something while it looks, because it closes when I click away from the window).

I've taken to just searching globally in the files for a symbol (Ctrl-Shift-F), and then click on a random search result, and then Ctrl-click on the symbol to go to the definition. That process should not be faster than the search for the symbol itself, but it is.

Since both IDE's searches are backed by the same analysis server, it seems like the VSCode search speed could be better. Could it be that it isn't terminating previous autocomplete searches when it gets a new letter, so they are piling up? Or some kind of deadlock or race condition?

(just FYI, I'm typically working on code in the Flutter framework itself, so there are a lot of symbols, but...)

Flutter extension: v3.46.0
Dart extension: v3.46.1
Flutter channel: master @ 5d2a13b4f0
VSCode: Version: 1.70.1 (6d9b74a70ca9c7733b29f0456fd8195364076dda)
OS: Linux x64 5.17.11-1rodete2-amd64

[gspencergoog]

It would also be nice if it did some caching, and maybe started by searching for symbols in the currently open tabs, and then continue to populate with results from the larger corpus as time goes on.

For example, I opened the file packages/flutter/lib/src/material/button_style_button.dart in the Flutter repo, copied the name of ButtonStyleButton to the clipboard, pressed Ctrl-T and pasted the name. It takes 25-30 seconds to come back with a result, and if I click away, and do the search again, it takes the same 25-30 seconds.

(I should point out that this is on a machine with seventy-two 3GHz cores, SSDs, and two hundred gigs of RAM, so it's probably not compute/memory limited.)

[DanTup]

Could it be that it isn't terminating previous autocomplete searches when it gets a new letter, so they are piling up?

It does start a new search, but it also sends a cancellation for the previous one, and in the search we check for cancellation periodically to abort those requests quickly.

I can reproduce similar performance to you're seeing. It took 32 seconds for me doing the search above with the whole Flutter repo open:

[5:31:56 PM] [Analyzer] [Info] ==> {"jsonrpc":"2.0","id":26,"method":"workspace/symbol","params":{"query":"ButtonStyleButton"},"clientRequestTime":1661185916253}
[5:32:28 PM] [Analyzer] [Info] <== Content-Length: 13140

There's some discussion related to performance of this search in dart-lang/sdk#48720 (the original request wasn't about performance, but the reason some items don't show up was a 500-item limit for performance reasons). In the case where there are >= 500 results, the search will end early at that point. If there are not (eg. in your example), the search will run for the entire workspace before completing (and therefore, before showing any results).

One thing that would help, is streaming the results. LSP now supports "partial results" where we can send incomplete lists periodically. If your class was found after 5% of the search, this would show you it much faster. If it's found after 95% of the search, you'd still be waiting a fair time though. We could perhaps prioritise the open files (if they're not already) though.

As for caching/indexing, I'm not sure of the cost of that. There's a little discussion about it in dart-lang/sdk#48720 (comment). It would need to support fuzzy searching and be selectively invalidated. I'll ping on that issue about that, and use this one for supporting partial results (which has been on my radar for a while and I think is a no-brainer).

[gspencergoog]

Thanks, Danny. One thing to look at is to see what IntelliJ is doing differently: I never noticed this kind of latency when I was searching for symbols there. I'm not sure what's different, but if I do the same search for ButtonStyleButton there, the latency would be measured in milliseconds (it's too short for me to measure, it feels instantaneous). I just tried it after clearing caches and restarting, waiting for indexing and analysis to settle down, and then searching.

Since they're using the same analysis server, it feels like a problem in how the IDE is using the server, not in the server itself.

[DanTup]

@scheglov do you know how the workspace symbol search works in IntelliJ? Is it parsing/keeping its own index? (I think you previously said it didn't use the APIs that VS Code/LSP are using).

[scheglov]

Yes, AFAIK Navigate | Symbol in IntelliJ uses its own index.

[gspencergoog]

The one I'm using is "Search Everywhere", but I assume that under the hood it just uses all three of those at the same time.

[gspencergoog]

@DanTup Is this something we can prioritize? It really has a huge impact on productivity for me. I've been trying to switch to VSCode for my everyday work, but I keep finding myself dropping back to IntelliJ because of this issue.

[DanTup]

I suspect having some sort of index (and keeping it updated) is a little involved. However, I just added some logging to have a quick look where all the time is going, and I noticed that in this particular case (the Flutter repo) we're searching the same files multiple times (and returning the same results many times - though the VS Code UI is merging them). The string Searching /Users/danny/Dev/Google/flutter/packages/flutter/lib/src/material/button_style_button.dart appears 59 times in my log, and there are 59 identical results.

It seems that we search in each analysis driver. There are 79 drivers if you open the Flutter repository root (because between dev, examples, packages there are a lot of projects). Each search looks in all referenced files, and across these 79 contexts the same files (the SDKs) are referenced a lot of times.

I don't know it's enough, but with the entire repo open (dev, examples and all) the search is taking 1m 7s for me today (I don't know what I had open above, since this is longer than the 32s I reported above). With a small change to track the files across each driver (so each one is searched only the first time) reduces it to 13s. If I open only the packages folder (22 drivers), then the time taken is 14s without the change, and 3.7s with the change.

I think it would be interesting to see how things are with both this change and support for streaming/partial results (unfortunately that's less trivial than this first change) before deciding whether an index is necessary.

@gspencergoog out of interest/for comparison, can you confirm exactly which folders you typically open, and how long the search in IntelliJ? (it may give some indication of the sort of performance an index could give us).

[gspencergoog]

I spend at least 90% of my time working on the main packages/flutter package, but I typically open the main flutter repo directory in order to have all of the files (especially examples/api) within easy reach. Most of my searches seem to take about 10-45 seconds, although, to be honest, I rarely have the patience, and I'll either do a full text search of the repo and then scan the results for the symbol I'm looking for, or I'll guess the filename and search within the file. My searches are most often for full class or symbol names, although if the search were faster I'd probably see the results before I finish typing them.

I open the same flutter directory (i.e. /Users/danny/Dev/Google/flutter on your machine) in IntelliJ. The search times for full symbols are fast enough that I rarely complete typing them. I can hardly notice the lag between keystrokes for the update in the search results.

Here's a comparison.

This is IntelliJ, full Flutter repo open, searching for "Directionality" using IntelliJ's "search all" feature (meaning it isn't just searching for classes, it's searching through file names, symbols and UI actions too).

IntelliJDirectionality.mp4

Here's VSCode doing the same search, although it's only searching for classes and symbols:

VSCodeDirectionality.mp4

One thing I noticed when recording this is that it doesn't seem to take the win. It found the symbol, but it paused while it exhausted its search before moving it to the top of the results, even though the results on the screen contained the full symbol already:

SlowFinish.mp4

Overall, I can't help but feel like it gets hung up after the first few characters return results. I seem to get the results for the first 2-3 characters fairly quickly, and then it waits the entire 30 seconds for the next chunk to return the full results. It seems random where it gets hung up: sometimes it only gets the results for the first character before hanging (sometimes hanging after printing the results starting with "#"), sometimes it gets to character 6 or 7 before hanging (like in the last video above).

Your change seems like a great improvement, and seems like a no-brainer if it's simple to implement. And while I still think an index may be the best way to eventually fix this, it does seem like there's still something that could be fixed in the existing algorithm, and maybe that would be sufficient if it could be found.

[gspencergoog]

For data collection, I should mention that the above videos were captured on a Macbook Pro M1 Max with 64GB of RAM, each video captured after waiting for the IDEs to finish indexing and analyzing.

[DanTup]

Thanks for the extra info!

One thing I noticed when recording this is that it doesn't seem to take the win. It found the symbol, but it paused while it exhausted its search before moving it to the top of the results, even though the results on the screen contained the full symbol already:

Yeah, this is a side-effect of us bailing out early when we hit a maximum number of results. When you're typing the first few characters, there are a lot of matches, so we just stop after finding the first 500 (since it's likely you're going to type more characters). When you're typed more characters and there aren't so many results, we end up searching more of the files (which takes much longer) without exiting early.

It's also possible VS Code is doing some debouncing which may add some delay. And ofc, us returning a large number of duplicates is probably not helping (it's more to be transferred from the server to the extension host, then the extension host to VS Code's UI, etc).

Once the change above is landed, I'll do some additional testing to see exactly how VS Code is behaving, and ensure cancellation is responsive enough (most of the search is synchronous so we have to periodically yield to ensure if there's a cancellation request in the buffer we pick it up quickly and abort, since there's probably another search also in the queue in that case).

[gspencergoog]

Thanks for taking a look at this.

It's too bad that most of the search is synchronous (and I assume also single-threaded), since it seems like with 79 "drivers" you could search each one on a separate thread (modulo the number of CPU cores) and integrate the results on the main thread. This should help even on projects with only three or four drivers, I would think.

[DanTup]

I did some more testing today, and noticed something I had missed previously. The first search is a lot slower (I don't know exactly why, there's probably some compilation going on, and perhaps some caching of files that are read from disk, by the OS and/or server). After the first search, things are much faster than I noted yesterday.

Here's some timings from opening the full Flutter repo but running the server from latest source (I don't think the change has rolled into Flutter master yet) on my machine. For each search, I pasted the class name in so that it is not affected by cancellation during typing (to just get raw search speed):

• ButtonStyleButton: 10,106ms
• VoidCallback: 552ms
• BoxHitTestResult: 512ms
• ButtonStyleButton: 499ms

I made sure the items were all in different files, and I did not open any files in the editor (which could have caused some additional caching). If you see the same, then hopefully the performance will be a lot less frustrating (if you ignore the very first one).

I also did some testing and found that VS Code is indeed debouncing as you type (edit: apparently it's 200ms). If I type ButtonStyleButton at a reasonable speed, it actually only sends a single request to the server:

Pausing during typing will perform searches:

And in the logs I can see that cancellations are sent and handled correctly:

[12:52:00 PM ==> {"jsonrpc":"2.0","id":15,"method":"workspace/symbol","params":{"query":""},"clientRequestTime":1662637920844}
[12:52:00 PM <== {"id":15,"jsonrpc":"2.0","result":[]}
[12:52:01 PM ==> {"jsonrpc":"2.0","id":16,"method":"workspace/symbol","params":{"query":"B"},"clientRequestTime":1662637921524}
[12:52:01 PM ==> {"jsonrpc":"2.0","method":"$/cancelRequest","params":{"id":16},"clientRequestTime":1662637921542}
[12:52:01 PM <== {"id":16,"jsonrpc":"2.0","error":{"code":-32800,"message":"Request was cancelled"}}
[12:52:03 PM ==> {"jsonrpc":"2.0","id":17,"method":"workspace/symbol","params":{"query":"ButtonStyleButton"},"clientRequestTime":1662637923493}
[12:52:04 PM <== {"id":17,"jsonrpc":"2.0","result":[{"kind":5,"location":{"range":{"end":{"character":1,"line":189},"start":{"character":0,"line":18}},"uri":"file:///Users/danny/Dev/Google/flutter/packages/flutter/lib/src/material/button_style_button.dart"},"name":"ButtonStyleButton"}]}

I'm interested to hear how things feel to you once this change lands in Flutter.

By the way, if you want a search that includes symbols and filenames, it seems VS Code has an option to include symbols in the Quick Open (Cmd+P):