Redesign incremental computation algorithm
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 355
- Forks
- 24
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 17
Description
Currently, our invalidation/incremental computation algorithm has a few flaws. It has many special cases, which hints that we have not arrived at the correct generalization of the problem, which can be described as "determining the smallest sub-graph that needs to be recomputed when changes occur".
There are also two main performance issues:
- We don't skip unnecessary work effectively. For example, if a local variable is introduced, there's no reason to run resolution
- We traverse and invalidate the graph on every document changed. This is highly wasteful because traversing the graph is expensive and because a modification to another document may influence the amount of work we have to do. For example, if we process one document change, we may conclude that a declaration has to be removed. If a second change is immediately consumed that would keep the declaration alive, we now need to re-create it
There are already well established algorithms for incremental computation in graphs, but in essence we need something that looks like this:
- Consuming a document change updates the indexing-level information (definitions, references...) and remembers in the
Graphthe document diff. That means, which meaningful changes happened between the old and new versions of document. If two definitions are identical, they should not appear in the document diff and should not be accumulated as pending work - After all document changes were consumed, when
resolveis triggered, the first step is to use the pending work to invalidate the smallest sub-graph possible. This guarantees that we're taking all document changes into account to avoid getting into a situation like the one described in 2, where changes influence each other and impact the final result - We need to skip work as much as possible. When invalidation is triggered inside of resolution, it will basically enqueue units into the queue. We should not enqueue unnecessary work, such as adding an
Ancestorunit if no direct ancestors were modified - Our solution needs to be a straight forward algorithm, similar to the resolution approach. We need to determine, what are the primitives that determine invalidation? Sometimes, it's a
StringId(if a new constant is defined that may impact the resolution of previously computed references), aDeclarationIdthat then invalidates all of its members (if the fully qualified name got invalidated because of constant resolution) or aDeclarationIdfor ancestor linearization (which may trigger even more invalidation)
Note: one interesting intersection is that the document diff may also be reused by #957 to determine the smallest amount of database updates we have to perform.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reading the Graph representation and the resolve entry point, then trace how document changes are consumed and how invalidation work is enqueued. Done means the algorithm accounts for all pending document changes before invalidation, avoids unnecessary graph traversal and queue work, and determines the smallest sub-graph requiring recomputation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100