Shopify / Shopify/rubydex

Redesign incremental computation algorithm

Open
#960 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

hard
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:

  1. We don't skip unnecessary work effectively. For example, if a local variable is introduced, there's no reason to run resolution
  2. 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:

  1. Consuming a document change updates the indexing-level information (definitions, references...) and remembers in the Graph the 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
  2. After all document changes were consumed, when resolve is 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
  3. 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 Ancestor unit if no direct ancestors were modified
  4. 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), a DeclarationId that then invalidates all of its members (if the fully qualified name got invalidated because of constant resolution) or a DeclarationId for 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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.