Performance of extracting LSIF-related semantic information

[Strum355]

Following on from #1914 on using Pyright as a backend for emitting LSIF data.

Currently I am collecting definition ranges, reference ranges, and hover text using the first APIs that seemed relevant to me and worked at the time.

For a relatively small sized Python codebase:

• time for a noop tree visitor is 449.73 millis.
• time for extracting definition ranges is 2.77 secs
• time for extracting definition ranges + hover text is 4.27 secs
• time for extracting definition ranges + hover text + reference ranges is 25.16 secs

Naturally, this does not scale well with codebase size (running on the mypy repository, it ran for 15min before I cancelled it prematurely). While extracting definition ranges and hover text can be somewhat merged together as they take very similar codepaths, references ranges dominates the execution time by a wide margin.
Leading from this, I have the following questions:

• Are there more suitable/performant APIs to achieve the same results?
• What scope is there for parallelization (using worker_threads etc)?
• Any other comments on the approach currently used or otherwise?

There are other routes we may explore (using a symbol based intermediary format cached between runs to minimize the number of files that need to be reindexed etc), but I would like to see how far we can go with Pyright itself before resorting to more elaborate solutions 🙂

[erictraut]

How long does it take to perform a complete type analysis of the same source base, and where is the time spent during that analysis? You can use the command-line version of pyright along with the --stats option to get a detailed breakdown.

It sounds like identifying reference ranges is the most expensive part. Are you using the existing reference API for this (the "reportReferencesForPosition" method)? This method was designed for finding all of the references for a single symbol. It was not designed to find all references to all symbols in a code base. Using it to find all references to all symbols will result in an n^2 behavior or worse. You would need to implement this a different way — one in which you find all references for all symbols in a single pass — to make it efficient.

[Strum355]

Completed in 2.02sec

Analysis stats
Total files analyzed: 475

Timing stats
Find Source Files:    0sec
Read Source Files:    0.03sec
Tokenize:             0.18sec
Parse:                0.33sec
Resolve Imports:      0.19sec
Bind:                 0.36sec
Check:                0.71sec
Detect Cycles:        0sec

Yes I am using reportReferencesForPosition. My first thought would be to cache results based on declarations (which can be extracted through TypeEvaluator.getDeclarationsForNameNode), but Im wondering if theres something more "unified" across references (as an example, javac has a Symbol type which is attached to all identifier/name nodes for that symbol). I see pyright also has a Symbol type but Im having a hard time seeing how to get a Symbol for a given NameNode while walking the trees, and whether or not it would be fit for purpose in your opinion.

[Strum355]

There are probably additional optimizations I can make along the lines of the current FindReferencesTreeWalker to avoid rewalking a tree many times, which will be another avenue I will explore.

[erictraut]

Yes, pyright has the notion of a symbol (see symbol.ts), and each symbol object has an associated set of one or more "declarations" (see declaration.ts). Most "name" nodes (identifiers) within a parse tree have an associated symbol. The symbol is allocated during the binding phase so it can be stored in the appropriate symbol table based on its scope.

Calling getDeclarationsForNameNode is fine, but calling reportReferencesForPosition for every position is not. That's where you're going to see n^2 behavior because you're going to walk all of the parse trees for all of the files every time you call reportReferencesForPosition. If you have 475 source files and 10,000 symbols, that means you'll be walking 4.8M parse trees!

You need to find a way where you walk the parse trees only once or twice per file. For example, you could walk all parse trees once to build up a map that maps identifiers to parse nodes. Then when you want to find all the references for "foo", you can quickly scan through only the nodes that contain "foo" to see which ones are not only a textual match but also a semantic match. Even if your map includes only files rather than individual parse nodes, it would allow you to skip the parse trees for the source files that don't contain "foo".

One challenge you may face is that you could run out of memory for very large code bases. Pyright monitors its memory usage and discards all of its internal caches (including parse trees, symbol tables, and type caches) if it gets close to a high-water mark of about 1.5GB. For a code base of 475 files, you won't come close to this. But as you start to go beyond 1000 files, you will probably start to hit this issue.