This repository has been archived by the owner. It is now read-only.

Incremental compilation #4

Open
aturon opened this Issue Nov 7, 2016 · 7 comments

Comments

Projects
None yet
6 participants
@aturon
Copy link
Member

aturon commented Nov 7, 2016

Point of contact

@nikomatsakis @michaelwoerister

Overview

The goal of the project is to allow the compiler to reuse results from previous compilations. The overall approach is that we dynamically track what data it has accessed to form a dependency graph. You can find more details on the current approach in RFC 1298 -- however, we are also contemplating an architecture shift that has yet to be written up in RFC form. The best notes, perhaps, can be found in the etherpad from the Paris 2017 design sprint.

The newer approach

The critical change in the new design is to be more reluctant to invalidate. Instead of eagerly invalidating everything that might have changed, we invalidate things when we see that a direct input as changed, and this invalidation propagates through the graph. This can result in more re-use, because we may have a node whose inputs have changed but which, when executed, still recomputes the same value (this could happen if, for example, it does not depend on the particular part of the input which changed, but only on other parts).

This algorithm integrates with the "on-demand" processing mechanism that we are phasing in. To describe the algorithm, we will use a series of three colors on the dependency graph: grey, red, and green. Grey is the initial color, and indicates that the node was loaded from a previous session and may or may have a valid value associated with it. Execution happens by a series of queries, which request values (e.g., "compute the TypeckTables for def-id D"). If we have a saved value for a query, but the node for that value is still colored grey, then we must first validate the value. This is done by checking the color of our predecessors in the dependency graph (i.e., the values which were read when computing the saved value). If they are grey, then we first demand the value. This will process the value recursively and ultimately leave it one of two colors:

  • Red, meaning that the value has changed in this compilation session.
  • Green, meaning that the previous value is still valid.

In both cases, we can now obtain the correct value for this particular session (which may or may not have been recomputed). If all inputs to our task come back as Green, then our saved value is still valid and we can re-use it (and color ourselves Green). If at any point we find that any of our inputs come back as red, then we can know that we have to recompute the value we are looking for (e.g., "compute the TypeckTables for def-id D"). We do this by running its "on-demand" task. Once the task completes, we take the new value and compare it against our saved value: it is possible, after all, that the inputs have changed but in a way that doesn't affect this particular result. If the result is the same as the saved value, we can color ourselves Green (even though we had red inputs), but otherwise we have to color ourselves as red -- which will cause those that used us as an input to be recomputed.

Scenarios

The following issues represent "scenarios that we want to work". In some cases, these issues will contain notes on the things that block them from "working" to our satisfaction yet.

Status

We are currently in the "beta period" for the current code. In particular, we are now able -- within a single crate -- to skip the translation into LLVM IR and the optimization phases by re-using object code. There are currently several major goals for moving past this point. Each is listed below, along with issues that track major milestones in that direction:

@vitiral

This comment has been minimized.

Copy link

vitiral commented Aug 1, 2017

You should probably strikethrough rust-lang/rust#40304 as you've closed it in favor of rust-lang/rust#40746

edit: rust-lang/rust#42535 is also done, so ✔️

@e-oz

This comment has been minimized.

Copy link

e-oz commented Aug 28, 2017

We are currently in the "beta period"

Please restore ability to use incremental compilation in beta branch of Rust.

@steveklabnik

This comment has been minimized.

Copy link
Member

steveklabnik commented Aug 28, 2017

@e-oz beta is like a release candidate for the final release; as such, beta follows the same rules as stable.

@ErichDonGubler

This comment has been minimized.

Copy link

ErichDonGubler commented Feb 9, 2018

Looks like all unchecked items should be checked now?

@michaelwoerister

This comment has been minimized.

Copy link

michaelwoerister commented Feb 12, 2018

Thanks, @ErichDonGubler. I checked all the boxes.

@ErichDonGubler

This comment has been minimized.

Copy link

ErichDonGubler commented Feb 12, 2018

@michaelwoerister: Is there anything left that's actionable in this issue, if everything is checked now? What's left to do?

@michaelwoerister

This comment has been minimized.

Copy link

michaelwoerister commented Feb 12, 2018

I'll leave it to @aturon to decide what to do with this issue now that 2017 is over.

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