New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for "Red/Green" Dependency Tracking #42293

Closed
michaelwoerister opened this Issue May 29, 2017 · 2 comments

Comments

Projects
None yet
3 participants
@michaelwoerister
Contributor

michaelwoerister commented May 29, 2017

"Red/Green dependency tracking" is what we call the improved tracking algorithm for incremental compilation. The main difference to the algorithm used at the moment is improved accuracy because it can recover from "false positives", that is, it can stop cache invalidation short if a potentially changed value turns out to not have changed after all. A (work-in-progress) description of the system can be found at https://github.com/nikomatsakis/rustc-on-demand-incremental-design-doc/blob/master/0000-rustc-on-demand-and-incremental.md. Implementing this new tracking and caching system will happen in a few phases:

Phase 1 - Red/Green without additional caching

In the first phase the core infrastructure for red/green tracking will be implemented. We do not cache any additional intermediate results but at the end of this phase, we will already have reached peak tracking accuracy.

  • Implement direct metadata hashing as a proof of concept for general result hashing (#38114)
  • Remove DepTrackingMap::write() (#42192)
  • Refactor DepNode to use a stable hash that does not need "re-tracing" (#42294)
  • Clarify how checking for query cycles fits into the red/green algorithm (#42633)
  • Remove all occurrences of DepNode re-opening (#42298)
  • Fingerprint all query results (#44364)
  • Switch to new, append-only dependency graph implementation (#44772)
  • Make Metadata fingerprints available in DepGraph (#44772)
  • Implementing minimal CachingPolicy support for queries and use for CGUs
  • Implement red/green marking in ty::queries::{}::try_get()
  • Transition the testing framework to work properly again (#44716)

Phase 2 - Caching ty::TypeckTables

In the second phase, support for caching ty::TypeckTables will be added, which allows the compiler to skip type checking.

  • Add infrastructure for caching and loading query results (#46004)
  • Move all uses of NodeId referenced by ty::TypeckTables over to HirId (#40303)
  • Refactor error messages, warnings, and lints to be cacheable (#41184)
  • Store and load ty::TypeckTables (#46004)

Phase 3 - Caching MIR

The third phase will support for caching MIR, which should be straight forward at that point. It remains to be verified though if it actually is a performance gain to do so.

  • Use new infrastructure to load and store optimized MIR (#46556)
  • Verify that this even makes sense

cc @nikomatsakis, @eddyb, and @rust-lang/compiler in general

@aturon aturon referenced this issue Jun 2, 2017

Open

Incremental compilation #4

14 of 14 tasks complete

bors added a commit that referenced this issue Sep 29, 2017

Auto merge of #44901 - michaelwoerister:on-demand-eval, r=<try>
incr.comp.: Switch to red/green change tracking, remove legacy system.

This PR finally switches incremental compilation to [red/green tracking](#42293) and completely removes the legacy dependency graph implementation -- which includes a few quite costly passes that are simply not needed with the new system anymore.

There's still some documentation to be done and there's certainly still lots of optimizing and tuning ahead -- but the foundation for red/green is in place with this PR. This has been in the making for a long time `:)`

r? @nikomatsakis
cc @alexcrichton, @rust-lang/compiler

bors added a commit that referenced this issue Oct 4, 2017

Auto merge of #44901 - michaelwoerister:on-demand-eval, r=nikomatsakis
incr.comp.: Switch to red/green change tracking, remove legacy system.

This PR finally switches incremental compilation to [red/green tracking](#42293) and completely removes the legacy dependency graph implementation -- which includes a few quite costly passes that are simply not needed with the new system anymore.

There's still some documentation to be done and there's certainly still lots of optimizing and tuning ahead -- but the foundation for red/green is in place with this PR. This has been in the making for a long time `:)`

r? @nikomatsakis
cc @alexcrichton, @rust-lang/compiler
@michaelwoerister

This comment has been minimized.

Contributor

michaelwoerister commented Dec 14, 2017

🎉 🎉 🎉 🎉 🎉

@matklad

This comment has been minimized.

Member

matklad commented Sep 7, 2018

@michaelwoerister could you add a link to https://rust-lang-nursery.github.io/rustc-guide/query.html to the original description? This is what comes up in the search for rust red-green, so it's nice to have links to state-of-the-art docs.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment