Chunk, scope, or shard LSIF for better processing throughput

I work on a tool that parses and interprets LSIF content. Recently we've been looking for ways to improve throughput when parsing large quantities of LSIF and have encountered a couple of bottlenecks that seem like they could be most effectively resolved with spec changes.

Lots of Stuff in Memory

By nature of being a graph we pretty much have to process the entire LSIF output, often holding much of it in memory. This strategy for memory management can severely limit the scalability of tools that consume LSIF output from large workspaces.

I have evaluated using begin and end $events as signals to unload items that are completed from memory. Using this mechanism, we can seemingly drop any of the following from memory after the owning document ends:

• range vertices
• contains edges
• next edges

Other items, like resultSets, monikers, and item edges can only be dropped if local to a particular document. For example: "unique": "document" property indicates that that item belongs to the document and can be unloaded when the document ends. Some generators, like Roslyn, however, do not use such narrow scoping, and so every resultSet must be treated as potentially global (cc: @jasonmalinowski).

Together, ranges, contains, and next edges make up 60% of the lines in a typical LSIF file. Dropping these at an end event is a solid reduction in memory, but it does mean that memory required to process an LSIF seems to grow linearly with the size of the workspace, albeit, at a slower rate.

For example: it's not unusual to see workspaces that generate 7-12GB of LSIF. Processing these, we end up with very long running parses and CPU time to spare, but absolutely no memory to process another LSIF in parallel.

No Parallel Traversal

In its current form, LSIF is very hard to traverse and process in parallel. This is related to its graph-like nature, in that you have to have most of the nodes and edges available to be sure your parse is semantically correct.

Attempts to ingest in parallel are typically defeated by an inability to guarantee that a thread doing a parse for a particular group of nodes, edges, or a particular document isn't missing a relevant bit of context by processing only a subsequence of vertices and edges. There are ways to solve this, but most I've tried run into lock contention or other tradeoffs that negate the benefits.

The Goal

The goal of this discussion is to make incremental changes to the LSIF spec and the surrounding guidance to better optimize it for ingestion throughput **cc: ** @dbaeumer,

The ideal approach for performance

The ideal from a performance standpoint is for language service information to be represented in uniformly sized chunks (perhaps one per document or per project), perhaps in separate LSIF graphs altogether. Each chunk should be independent of each other and able to be processed in any order. Linkages between the documents could be expressed via the usage of monikers, hashes, IDs, or other foreign key relationship, which can be realized when querying the backing file/datastore/etc.

JSON is also quite expensive to parse, largely due to memory allocation (in C# it's approximately 20% of the LSIF parser Thread Time) and the majority of the GC-triggering allocations, making alternate encodings enticing from an optimization perspective.

The biggest appeal of this approach is that it mirrors that of traditional build systems with separate compile and link stages: files/projects are compiled, and the results are linked by mangled name or ID, enabling effective utilization of the machine resources at pretty much any scale of project.

I base this ideal on the observation that while the data are conceptually a graph, it frequently ends up a database, store, or alternate encoding as flat records with foreign key relationships.

The incremental step

The ideal performance approach is a radical departure from the existing model that may be difficult for existing partners to adapt to and would break compatibility.

An incremental alternative is to maintain the existing graph format for LSIF, but 1) make targeted changes to enable generators to chunk their output and 2) update the language in the spec to contain a best practices section that describes language optimizations with a bit greater detail.

Begin and end $events are almost exactly what is needed to solve this problem. Their one drawback is that they can be interleaved/overlapping. If they instead were nested, like brackets in code, a trivial, scope aware LSIF parser could use a stack to maintain awareness of when things go in/out of scope. A savvy implementation could even execute peer scopes in parallel.

Specifics

$events are updated to either disallow overlapping/interleaving (a breaking change), or updated to make non-overlapping an optional capability in the capabilities vertex ( #1753, non-breaking change), or by adding new event names like "beginScope" and "endScope" with different semantics.

To ensure proper behavior after a scope terminates, some rules apply:

• ResultSets spanning multiple documents in a single project via reference edges must not be contained a document partition. They must be contained in the enclosing project partition, if any.
• ResultSets spanning multiple projects via reference edges must not be contained in a project partition. They go in the global scope.
• Where possible, LSIF generators that work on large projects should decouple reference graphs at some level... perhaps the project level and link them instead via usage of a common moniker.

Start with the LSIF specification's $events, scope behavior, and capabilities vertex, then review the related discussion in issue #1753. Compare nested scopes, an optional non-overlapping capability, and new beginScope/endScope events. Done would require an agreed specification change and updated best-practices guidance, including rules for cross-document and cross-project ResultSets.