Stream: t-compiler/wg-incr-comp

Topic: brainstorming: mission statement, goals, design constraints


view this post on Zulip pnkfelix (Jun 25 2020 at 15:26):

this is a brainstorming thread

view this post on Zulip pnkfelix (Jun 25 2020 at 15:27):

so I don't know if this is going to end up being an area subteam or a project subteam

view this post on Zulip pnkfelix (Jun 25 2020 at 15:27):

it sort of depends on whether we turn into a group of local experts on everything related to incr-comp

view this post on Zulip pnkfelix (Jun 25 2020 at 15:27):

or if we just decide on a specific set of tasks that we're going to do, and once they're done, we disband

view this post on Zulip pnkfelix (Jun 25 2020 at 15:29):

in any case, here are some thoughts that have been bouncing around my head for some number of days

view this post on Zulip pnkfelix (Jun 25 2020 at 15:29):

some of these are things I've already talked about with @nikomatsakis but want to record more publicly

view this post on Zulip davidtwco (Jun 25 2020 at 15:29):

(I don't have much of an opinion regarding these questions, I'm primarily interested in showing up at a meeting each week (or w/e), being given some tasks to do, and gaining expertise in incr-comp through that - whatever everyone else's goals are, that works for me)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:29):

others are more little musings that I'm still working through

view this post on Zulip pnkfelix (Jun 25 2020 at 15:30):

@davidtwco that's no problem. I just figure this can be a space for people to write down their thoughts. Or respond to mine. Or maybe it will just be a void that I send messages off into.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:30):

The first thing I want to bring up: I recently mentioned to niko how we might be better served in incremental compilation

view this post on Zulip pnkfelix (Jun 25 2020 at 15:30):

if we used some sort of "predictive model" to anticipate which modules/fn's are most likely to be editted in the future

view this post on Zulip pnkfelix (Jun 25 2020 at 15:31):

and keep those in a separate cgu

view this post on Zulip pnkfelix (Jun 25 2020 at 15:31):

from the unchanging code

view this post on Zulip pnkfelix (Jun 25 2020 at 15:31):

obviously we cannot predict the future, but I would guess that the modules in files that have been most recently edited are ones likely to change in the future

view this post on Zulip pnkfelix (Jun 25 2020 at 15:32):

when I mentioned this to @nikomatsakis , they responded that one of the oldest design crietria for incr-comp is that it is deterministic

view this post on Zulip pnkfelix (Jun 25 2020 at 15:32):

i.e. the edit history should not matter for the final object code files you get out

view this post on Zulip pnkfelix (Jun 25 2020 at 15:34):

nikomatsakis specifically pointed out that the incr-comp system, at least originally, had testing where they went through the commit history for a set of projects and checked that incr rebuilds after each commit had same object output as building from scratch at that commit

view this post on Zulip pnkfelix (Jun 25 2020 at 15:35):

So all of this is to say: Do we think this is a property we should ensure we preserve? Or should we consider, e.g., having a opt-in flag where a user can say "go ahead and make cgu partitioning decisions that depend on details such as file timestamps"?

view this post on Zulip pnkfelix (Jun 25 2020 at 15:35):

That's sort of a big picture question, and I imagine a change to that design criteria would have to be approved by rest of rustc team

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:35):

Was the goal for reproducible builds or something else?

view this post on Zulip Jonas Schievink [he/him] (Jun 25 2020 at 15:36):

It sounds a bit like that would make reproducing incr. comp. bugs even harder than it already is

view this post on Zulip pnkfelix (Jun 25 2020 at 15:36):

I think it was for reproducible builds, yes, exactly

view this post on Zulip pnkfelix (Jun 25 2020 at 15:36):

and I had a reaction of "I think that ship has sailed"

view this post on Zulip pnkfelix (Jun 25 2020 at 15:36):

(which is when nikomatsakis gave the example of the commit history test)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:37):

I don't remember offhand if there were other motivations besides reproducibility of builds, and also bugs (which may or may not be a corollary)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:37):

anyway any work we did here would definitely have to show huge benefits before it could get buy-in, I imagine

view this post on Zulip pnkfelix (Jun 25 2020 at 15:38):

but given how much time of compiling e.g. rustc_middle is spent in LLVM codegen

view this post on Zulip pnkfelix (Jun 25 2020 at 15:38):

its something that I keep thinking about

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:38):

It seems like most of the use cases that care about reproducible builds are batch compilation sessions anyway. But yeah, I agree that would probably make repro-ing incr. comp bugs more difficult.

view this post on Zulip davidtwco (Jun 25 2020 at 15:38):

While reproducible builds are great, and we should want them, I think it would be reasonable for debug builds where you're just working locally to forgo that.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:38):

having said that, there may be other ways to get similar benefits

view this post on Zulip pnkfelix (Jun 25 2020 at 15:38):

in particular, something else I was thinking about

view this post on Zulip pnkfelix (Jun 25 2020 at 15:39):

(by the way, I may make statements here that are bogus. please do correct me if so)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:39):

the other thing I was thinking about: Right now, if i understand correctly, we have a cgu parititioning system where we have a hard limit on the number of cgu's

view this post on Zulip pnkfelix (Jun 25 2020 at 15:40):

we start with a large set of cgui's and merge them in order to stay under that bound, call it N

view this post on Zulip pnkfelix (Jun 25 2020 at 15:41):

and that is set by profiles in cargo

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

where the default is 256 for incremental builds and 16 for non-incremental (for parallel codegen purposes)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

so heres my point

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

what if, instead of having a fixed number

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

we instead had it scale up with crate size

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

or, if you prefer, we had a max codegen-unit size

view this post on Zulip pnkfelix (Jun 25 2020 at 15:42):

that is, a max size for each codegen unit

view this post on Zulip pnkfelix (Jun 25 2020 at 15:43):

and so the merging would be about putting the smaller stuff together

view this post on Zulip pnkfelix (Jun 25 2020 at 15:43):

this is all a very long way of saying

view this post on Zulip pnkfelix (Jun 25 2020 at 15:43):

right now, the time spent doing codegen

view this post on Zulip pnkfelix (Jun 25 2020 at 15:43):

is going to be O(C) where C is the size of your crate

view this post on Zulip pnkfelix (Jun 25 2020 at 15:43):

even when you turn on incremetnal, its still O(C)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:44):

(its "just" cut by that constant factor)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:44):

but if the policy were instead to have a max codegen-unit size

view this post on Zulip pnkfelix (Jun 25 2020 at 15:45):

then time spent doing codegen should be O(E*S), where E is number of edits and S is that max codegen-unit size

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:45):

I think in general that's a good idea but there's a few things I ran into when I played with that idea:

view this post on Zulip pnkfelix (Jun 25 2020 at 15:46):

I agree you don't want to split call graphs if you can. That could hopefully be addressed by making the merge algorithm smarter

view this post on Zulip pnkfelix (Jun 25 2020 at 15:46):

the "get lucky and have thing in tiny CGU" case ... does that actually happen today?

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:46):

Yeah

view this post on Zulip pnkfelix (Jun 25 2020 at 15:46):

I was under impression that, since the cgu merge system is geared towards load balancing

view this post on Zulip pnkfelix (Jun 25 2020 at 15:47):

that you would tend to have small stuff all collected together

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:47):

If your function is not polymorphic, it tends to end up in one of the smaller CGUs

view this post on Zulip pnkfelix (Jun 25 2020 at 15:47):

hmm

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:47):

Not always

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:47):

but often I'd say

view this post on Zulip pnkfelix (Jun 25 2020 at 15:47):

that's interesting

view this post on Zulip pnkfelix (Jun 25 2020 at 15:47):

if anything, its an argument for the predictive modelling I mentioned up above

view this post on Zulip pnkfelix (Jun 25 2020 at 15:48):

the other thing I was thinking, regarding max codegen size

view this post on Zulip davidtwco (Jun 25 2020 at 15:48):

Does that fall out from generic and non-generic items being in different codegen units in the initial set and then there just being more generic code in most projects?

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:48):

I think so yeah

view this post on Zulip pnkfelix (Jun 25 2020 at 15:49):

pnkfelix said:

the other thing I was thinking, regarding max codegen size

... instead of having it be a predetermined number, the number could be computed by the contents of the crate. E.g. take the largest fn in the crate, multiply its size by 10 (or some other factor K), and then use that as the target cgu size.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:50):

I'm honestly not sure whether that will hurt or help overall, but it at least seems like it has a chance to being adaptive to peoples coding styles

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:50):

Yeah, I think scaling the number of CGUs by the size of the crate (however that's determined) is a good idea

view this post on Zulip pnkfelix (Jun 25 2020 at 15:50):

if nothing else, it has a nice asymptotic growth argument behind it.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:51):

perfect for academic papers

view this post on Zulip davidtwco (Jun 25 2020 at 15:51):

There's already some code-size heuristic computed in partitioning to determine which codegen units are smallest and should be merged, right?

view this post on Zulip davidtwco (Jun 25 2020 at 15:51):

I assume that could be used to determine the size of an entire crate.

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:51):

One project I've been thinking about doing is refactoring partitioning.rs so that the actual algorithm is hidden behind a trait which would let us swap out different algorithms in a cleaner way. Potentially we could have unstable flags for choosing the algorithm for testing.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:51):

yes. it is only an estimate

view this post on Zulip Wesley Wiser (Jun 25 2020 at 15:52):

That would also give us a framework for having algorithms for different build configurations.

view this post on Zulip pnkfelix (Jun 25 2020 at 15:52):

(and I've seen some issues where people grumble about inaccuracies in the estimate)

view this post on Zulip pnkfelix (Jun 25 2020 at 15:53):

okay. I need to go afk for a bit. thanks for letting me bounce these ideas off of you all.

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:02):

Something I'd like to see as well (I think @Wesley Wiser was experimenting with this concept) is experimentation with large numbers of CGUs for incremental compilation

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:02):

Like, the numbers that we have today are sort of magic numbers

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:02):

(To pick the numbers and size of CGUs)

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:03):

I would like to see how small can we make the CGUs before we lose incremental compilation performance

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:04):

Because the smaller they are, the more the incremental compilation times should mimic the size of the edit, is that correct?

view this post on Zulip Félix Fischer (Jun 25 2020 at 18:05):

And hopefully, I think, we would like incr. comp time to be related to the size of the edits, i.e. small edits should make recompilation almost trivial

view this post on Zulip Jonas Schievink [he/him] (Jun 26 2020 at 12:50):

Just thought of another drawback of making incr. comp. nondeterministic: It would become impossible to use it to build code for benchmarking.

view this post on Zulip Jonas Schievink [he/him] (Jun 26 2020 at 12:50):

This is something I do all day at the moment, and having to wait even longer to run benchmarks would be very unfortunate

view this post on Zulip Félix Fischer (Jun 26 2020 at 15:59):

Jonas Schievink said:

Just thought of another drawback of making incr. comp. nondeterministic: It would become impossible to use it to build code for benchmarking.

I don't think it would become _impossible_. It would become quite a lot harder though. We'd need a long time to run benchmarks multiple times, and do statistical analysis over the sample.

And there's an argument to be said that we need to do that already (measuring performance of a deterministic program is already quite hard).

view this post on Zulip Jonas Schievink [he/him] (Jun 26 2020 at 16:08):

But if you change the program and want to estimate the performance impact of that change, non-deterministic incr. comp. wouldn't just mean you have to run it more often, it means you have to turn incr. comp. off completely, since it depends on the changes to the source code. Not even recompiling multiple times would help (since nothing has changed since the last rebuild).

view this post on Zulip Jonas Schievink [he/him] (Jun 26 2020 at 16:11):

(you raise a good point though – this is another reason why reproducible builds are important)

view this post on Zulip Félix Fischer (Jun 26 2020 at 16:27):

If you change the program and want to estimate the performance impact of that change

Ahh, I get what you mean now. I was thinking of measurements to incr. compilation times (in the context of developing the compiler), but you mean measuring performance of another Rust project that's being compiled. Yas, that's totally right. The performance impact would have to be measured against the from-scratch compiled binary, because the incr. comp. binary would depend on the compilation history, yes yes yes yes.

view this post on Zulip gizmondo (Jun 29 2020 at 10:45):

Should "querify earlier stages of compilation" be one of the goals?

view this post on Zulip pnkfelix (Jun 29 2020 at 18:01):

Jonas Schievink said:

Just thought of another drawback of making incr. comp. nondeterministic: It would become impossible to use it to build code for benchmarking.

my latest thinking here is that we could get around this by providing an easy way to recreate a given incremental compilation context. E.g. a -Z flag where you explicitly say "treat this listed set of files as recently changed, and all others as not recently changed." That, combined with some automated messaging from the compiler saying what those sets are on a given compiler run, would let us recreate incremental build contexts that incorporate history without losing determinism.

view this post on Zulip Félix Fischer (Jun 29 2020 at 18:08):

But that's a bit coarse-grained, isn't it? After all, incr-comp changes depending on how much and where each file was changed.

view this post on Zulip Félix Fischer (Jun 29 2020 at 18:09):

Like afaik just introducing a println! call can currently affect the next incr comp step substantially

view this post on Zulip Félix Fischer (Jun 29 2020 at 18:09):

But other changes to the same file are trivial to recompile

view this post on Zulip pnkfelix (Jun 29 2020 at 18:12):

well, if we can come up with some reasonable way for a human to encode the context, then one can imagine using something more fine-grained than just file timestamps

view this post on Zulip pnkfelix (Jun 29 2020 at 18:12):

my main point was that we need not give up on reproducibility

view this post on Zulip pnkfelix (Jun 29 2020 at 18:13):

(however, if it requires a very long string of text to encode the context informing the incremental compile, then this is perhaps not realistic.)

view this post on Zulip davidtwco (Jun 29 2020 at 18:15):

(one thought I've just had - might be worth scheduling a meeting/session describing what the incr-comp infrastructure looks like within the compiler today; gets everyone up to speed as the working group starts to do things + you can refer back to it with new folks, or for a refresher)

view this post on Zulip Félix Fischer (Jun 29 2020 at 18:15):

Yeah, I'm thinking that perhaps the minimum equivalent representation of the problem for the goal of reproducibility is a diff history, a bit like a git commit chain (caveat: I know that git doesn't actually work as patch-based diff chains, but for this purpose it can be thought of in that way)

view this post on Zulip pnkfelix (Jun 29 2020 at 18:16):

gizmondo said:

Should "querify earlier stages of compilation" be one of the goals?

This probably should indeed be one of the goals

view this post on Zulip Jonas Schievink [he/him] (Jun 29 2020 at 18:19):

I'm mainly concerned about users who want to cargo bench their code, and turn on incr. comp. at the same time (which would become the default once #57968 is resolved). For those users, the executable they get would depend on recent changes, which sounds undesirable. If a -Z flag is provided to override this behavior, I'm not sure how people would find out about it.

view this post on Zulip Félix Fischer (Jun 29 2020 at 18:20):

Yeah, -Z flags should not be where the best option for normal users lie

view this post on Zulip Jonas Schievink [he/him] (Jun 29 2020 at 18:21):

(some projects enable this kind of setup today because they are trying to find a balance between compile times and runtime performance, rust-analyzer is one example, but this is common for game dev too, I believe)

view this post on Zulip Santiago Pastorino (Jul 03 2020 at 22:01):

davidtwco said:

(one thought I've just had - might be worth scheduling a meeting/session describing what the incr-comp infrastructure looks like within the compiler today; gets everyone up to speed as the working group starts to do things + you can refer back to it with new folks, or for a refresher)

I've never replied to this message but I thought I have done so :P, I was talking with @pnkfelix some days ago exactly about this, so huge :+1:

view this post on Zulip njn (Jul 12 2020 at 22:47):

Making incr. comp. non-deterministic sounds awful to me. It would make all sorts of things harder, such as profiling.

view this post on Zulip eddyb (Jul 13 2020 at 00:35):

uhh, what's this about? I wasn't here when the conversation took place

view this post on Zulip eddyb (Jul 13 2020 at 00:36):

is this specifically just about CGU partitioning?

view this post on Zulip eddyb (Jul 13 2020 at 00:36):

at least that part I'm less worried about, compared to the query system

view this post on Zulip njn (Jul 13 2020 at 01:22):

Oh, it says above that "deterministic" means "the edit history should not matter for the final object code files you get out". That's much stronger than what I was thinking of

view this post on Zulip eddyb (Jul 13 2020 at 02:57):

hmm, this shouldn't matter for most of the compiler, right? just codegen and beyond?

view this post on Zulip eddyb (Jul 13 2020 at 02:59):

okay found the start of the non-determinism discussion: https://rust-lang.zulipchat.com/#narrow/stream/241847-t-compiler.2Fwg-incr-comp/topic/brainstorming.3A.20mission.20statement.2C.20goals.2C.20design.20constraints/near/201984881

view this post on Zulip eddyb (Jul 13 2020 at 03:00):

okay yeah seems to be able CGUs, since if they're based on the state of the code when you first compiled the crate, and don't change when you recompile, would not be identical for different edit histories

view this post on Zulip eddyb (Jul 13 2020 at 03:02):

at least it can't (or shouldn't be able to) affect query system behavior in ways in which I care about - even if there are other problems with "edit history sensitive" CGUs

view this post on Zulip pnkfelix (Jul 13 2020 at 16:23):

Yeah my main focus (when I was talking about using the edit history) was CGUs.

view this post on Zulip pnkfelix (Jul 13 2020 at 16:25):

now, that may still affect things we care about. When @njn said "profiling" above, I don't know if that was in reference to profile-guided optimization (PGO), or if it was "just" about manual inspection of performance profiles

view this post on Zulip pnkfelix (Jul 13 2020 at 16:25):

I suspect messing with the CGUs would probably totally screw up PGO

view this post on Zulip njn (Jul 13 2020 at 22:45):

I mean, if we have two identical scenarios (in terms of what gets compiled, changed, recompiled, etc., after starting from a fresh codebase), I want to have identical (or very nearly identical) behaviour. Which is what we currently have. E.g. look at the incr-patched benchmarks.

view this post on Zulip pnkfelix (Jul 13 2020 at 23:25):

@njn if a "scenario" includes the edit history, then my intent was that determinism would be retained. (I was further musing to go a step further, and have some succinct encoding of the historical context that the compiler could emit and read back in, to ease reconstruction of scenarios)

view this post on Zulip pnkfelix (Jul 13 2020 at 23:26):

that is, the "non-determinism" I was referring to was that the edit history could affect the output, and for some people, that implies unpredictability

view this post on Zulip Félix Fischer (Jul 14 2020 at 06:15):

So you're saying that this non determinism would behave like a seeded RNG:

view this post on Zulip Félix Fischer (Jul 14 2020 at 06:17):

The third point implies that if you have two identical histories, the IR generated for both of them would be the same.

view this post on Zulip eddyb (Jul 14 2020 at 07:03):

@Félix Fischer I thought the "change history" is only relevant because of statefulness, not because it exists as an input

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:03):

Yeah yeah yeah

view this post on Zulip eddyb (Jul 14 2020 at 07:03):

simplest way I can imagine this is some information computed when first compiling incrementally, that is preserved instead of updated

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:03):

I'm modeling it as an equivalent problem

view this post on Zulip eddyb (Jul 14 2020 at 07:03):

so instead of being deterministic on the current source code, it's deterministic on the source code at some point in the past

view this post on Zulip eddyb (Jul 14 2020 at 07:04):

I don't think you need to get into randomness, it's deterministic just not on the current state

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:04):

Yes

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:04):

It is deterministic

view this post on Zulip eddyb (Jul 14 2020 at 07:04):

I'd call it "stateful" not even nondeterministic tbh

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:04):

But it might appear random

view this post on Zulip eddyb (Jul 14 2020 at 07:05):

no, I don't think that's fair to say

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:05):

I think I need a voice message to explain what I mean XD

view this post on Zulip eddyb (Jul 14 2020 at 07:06):

because of how different the past codebase could look compared to the current one, I don't think you can even model it probabilistically

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:06):

I mean that it is like a noise function. You give it a seed and a point in space, and it always computes to the same value

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:06):

(Procedural noise)

view this post on Zulip eddyb (Jul 14 2020 at 07:06):

that's just a deterministic function

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:06):

And it is continuous in the point

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:06):

Yup

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:06):

Deterministic indeed. Well, that's what I'm asking

view this post on Zulip eddyb (Jul 14 2020 at 07:07):

I don't see how the "PRNG" aspect applies to the rustc situation

view this post on Zulip eddyb (Jul 14 2020 at 07:08):

it's either deterministic in one or more of the states the source code was when running rustc, or it's not

view this post on Zulip eddyb (Jul 14 2020 at 07:08):

if it depends on anything but the current state, it's stateful

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:08):

Why not? (Btw we might be digressing too much here, and I think we are actually saying the same thing but I might not be good enough at writing my idea down to show it, I think?

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:09):

Nono, you got me wrong. Procedural noise is always deterministic. It only appears random.

view this post on Zulip eddyb (Jul 14 2020 at 07:09):

what rustc does doesn't even appear random, it's just boring algorithms

view this post on Zulip eddyb (Jul 14 2020 at 07:09):

you can add PRNGs to some of the algorithms but that's specifically an extra step

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:09):

But prngs are something else eddy!

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:10):

Anywho

view this post on Zulip eddyb (Jul 14 2020 at 07:10):

the closest thing is probably LLVM optimizations, in terms of unpredictable behavior

view this post on Zulip eddyb (Jul 14 2020 at 07:10):

what rustc does is very boring compared to anything random-looking, noise etc.

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:10):

Yes

view this post on Zulip eddyb (Jul 14 2020 at 07:11):

and we could (deterministically) randomize some things, and that's a specific choice, which is why I disagree on using that terminology when we don't do that

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:11):

But my question was about this discussion we were having on making the incr. compilation artifacts be "non-deterministic"

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:11):

So, things that haven't been implemented yet

view this post on Zulip eddyb (Jul 14 2020 at 07:11):

I think even "non-deterministic" might've been a misuse of the term

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:12):

And I wanted to ask Felix (the other Felix XD) if what he meant was actually "deterministic, but basically dependent on the entire incr. compilation history of the code"

view this post on Zulip eddyb (Jul 14 2020 at 07:12):

statefully deterministic and only apparently non-deterministic (when taking into account only the current state)

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:13):

Yup

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:13):

Exactly

view this post on Zulip eddyb (Jul 14 2020 at 07:13):

okay sure but bringing anything like "randomness" into it muddles the waters, because @pnkfelix may have been talking about actually randomizing (deterministically, or not) some initial state of the incremental caches

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:13):

I think that "non-deterministic" here means that the artifacts produced might depend on history and not just code alone

view this post on Zulip eddyb (Jul 14 2020 at 07:14):

sorry, I should go to sleep instead of stumbling over things to be pedantic about

view this post on Zulip eddyb (Jul 14 2020 at 07:14):

yeah I think that's a slightly misuse like I mentioned above

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:14):

Yeah yeah

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:14):

Don't worry eddy

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:14):

Be pedantic alright

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:15):

Please do ask me for clarification if something seems off in my writing

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:17):

I sometimes use terms that might be ambiguous because I usually bring different areas of CS to the table, to understand the compiler better myself

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:18):

But those terms in this context might not carry the same meaning

view this post on Zulip Félix Fischer (Jul 14 2020 at 07:18):

:heart:

view this post on Zulip pnkfelix (Jul 14 2020 at 15:36):

im happy to switch terminology

view this post on Zulip pnkfelix (Jul 14 2020 at 15:38):

all I've been trying to say is that we might want to allow the results to be a function of the history rather than the end state. I said "non-deterministic" because, unfortunately, that's how such results can look to some people who assume that history is not an input to the function.

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:44):

Oh, okay, I think we got what you meant then :3

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:45):

I was worried I had misunderstood

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:46):

So then: is this a problem? That the results are history-dependent for the incr-comp case?

view this post on Zulip pnkfelix (Jul 14 2020 at 15:47):

well, as I noted above, its contrary to one of the original design goals for incr-comp

view this post on Zulip pnkfelix (Jul 14 2020 at 15:48):

that is, at one point one of the tests in use was to rebuild a repo at each point in its history, and check that the results are the same as a clean build (i.e. one with no incr-comp results stored)

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:48):

Ahhh, I see

view this post on Zulip pnkfelix (Jul 14 2020 at 15:48):

(because I interpret the latter as being the same as "having no history at all")

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:49):

Right, right

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:49):

Can we get rid of that restriction?

view this post on Zulip pnkfelix (Jul 14 2020 at 15:49):

that is indeed the question. :)

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:49):

Hahaha

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:49):

:)

view this post on Zulip pnkfelix (Jul 14 2020 at 15:49):

its probably something we'd have to raise with the whole compiler team, at least

view this post on Zulip pnkfelix (Jul 14 2020 at 15:49):

if not core as well

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:49):

Agreed

view this post on Zulip pnkfelix (Jul 14 2020 at 15:50):

And I don't want to do that until we've got evidence that doing this is a significant win

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:50):

Ahh, okay

view this post on Zulip pnkfelix (Jul 14 2020 at 15:50):

Niko pointedly said that they thought there are other tasks we could tackle, like querifying more stuff

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:51):

Querifying more stuff?

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:51):

Like, in chalk?

view this post on Zulip pnkfelix (Jul 14 2020 at 15:51):

pnkfelix said:

And I don't want to do that until we've got evidence that doing this is a significant win

at the same time, I don't want to invest the effort of prototyping history-sensitive compilation unless we have some idea that it might be okayed.

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:51):

Right, right. I was wondering about that^

view this post on Zulip pnkfelix (Jul 14 2020 at 15:52):

Félix Fischer said:

Like, in chalk?

um more like in the query system that the compiler actually uses today?

view this post on Zulip davidtwco (Jul 14 2020 at 15:52):

Félix Fischer said:

Querifying more stuff?

https://rustc-dev-guide.rust-lang.org/query.html

view this post on Zulip pnkfelix (Jul 14 2020 at 15:52):

let me see if I can find an issue explaining this

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:52):

Ahhhhhhhhhhhhhhhh

view this post on Zulip Wesley Wiser (Jul 14 2020 at 15:52):

AIUI only the middle and backend parts of the compiler use the query system which is what powers incremental compilation. The parser, name resolution, and other frontend stuff is still pass based and doesn't participate in incremental compilation.

view this post on Zulip pnkfelix (Jul 14 2020 at 15:52):

see for example: https://rust-lang.github.io/compiler-team/minutes/design-meeting/2019-12-06-end-to-end-query-PRs/

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:53):

Demand driven compilation. I had completely forgotten that that was one of the current overall goals

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:54):

I was only thinking in queries as "rust-analyzer kind of things"

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:55):

So how do we get from a world where we do incremental pass-based compilation to a world where, at least for debug builds, we do it... query-based?

view this post on Zulip Wesley Wiser (Jul 14 2020 at 15:55):

We're already query based, just not the first part of the compilation process

view this post on Zulip pnkfelix (Jul 14 2020 at 15:55):

no no, read @Wesley Wiser 's message again

view this post on Zulip Wesley Wiser (Jul 14 2020 at 15:55):

So the goal is to make that part query based as well

view this post on Zulip pnkfelix (Jul 14 2020 at 15:55):

the pass-based stuff is inherently non-increental

view this post on Zulip pnkfelix (Jul 14 2020 at 15:56):

but yes, we probably do want to move from pass-based to query-based for more stuff

view this post on Zulip pnkfelix (Jul 14 2020 at 15:56):

that is what the end-to-end query stuff is about. (Making the earlier phases use queries)

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:56):

Ah, okay. So we are already in a query-based world. This is cool :D

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:58):

Ah, okay, I see. So niko was saying that we could still get some low-hanging fruit by querifying more parts of the compiling process.

view this post on Zulip pnkfelix (Jul 14 2020 at 15:58):

exactly

view this post on Zulip pnkfelix (Jul 14 2020 at 15:58):

I don't know how low-hanging it is

view this post on Zulip pnkfelix (Jul 14 2020 at 15:58):

but it would have a less drastic effect, perhaps, on our customers

view this post on Zulip davidtwco (Jul 14 2020 at 15:58):

pnkfelix said:

I don't know how low-hanging it is

I was typing exactly this :laughter_tears:

view this post on Zulip Wesley Wiser (Jul 14 2020 at 15:59):

There's other possible improvements here as well. Some of our queries are very "coarse-grained" so we do more work than strictly necessary or because they cover so much code, they invalidate more of the data then needs to be when something changes. Breaking those kinds of queries up to be smaller would result in less work.

There's also the reverse where if we have queries that are too small, the overhead of recording their results into the query system dwarfs the improvements we get from running them incrementally.

view this post on Zulip Wesley Wiser (Jul 14 2020 at 15:59):

Basically just fine-tuning what we already have.

view this post on Zulip Félix Fischer (Jul 14 2020 at 15:59):

Right, right, right

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:01):

I wonder how we can set up a benchmark for this. Something that feeds compilation histories to the compiler so that we can see how the tuning efforts affect performance

view this post on Zulip pnkfelix (Jul 14 2020 at 16:02):

even a short history might be useful

view this post on Zulip davidtwco (Jul 14 2020 at 16:03):

Félix Fischer said:

I wonder how we can set up a benchmark for this. Something that feeds compilation histories to the compiler so that we can see how the tuning efforts affect performance

perf.rust-lang.org does that some of that already, which you might not be aware of - there is a baseline run, a full incremental run and a patched incremental run - we may of course want something more or less depending on what the working group ends up focusing on

view this post on Zulip pnkfelix (Jul 14 2020 at 16:03):

like, our current perf.rlo benchmarks only use single patches at most for evaluating incrental, if I remember correctly

view this post on Zulip pnkfelix (Jul 14 2020 at 16:03):

while I would expect we would probably want histories with a stack of at least two patches

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:03):

Yup, as I understand it, that is the case

view this post on Zulip pnkfelix (Jul 14 2020 at 16:03):

(since the content of the first patch will likely inform the compilation of the second patch)

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:04):

Yas. Two patches would let us explore how two changes interact

view this post on Zulip pnkfelix (Jul 14 2020 at 16:05):

adding a two-patch stack to perf.rlo probably would not be that hard. But I wouldn't want to start adding that overhead to perf until we have something in place that tries to use it

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:05):

(Thank u @davidtwco, I already sorta know that bench, although I feel like I could know a lot more still ^^)

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:06):

We get a lot of PRs that need to run perf before merging so adding tests to that unnecessarily hurts PR throughput. If we need the tests to catch perf regressions or make sure things stay fast, that's fine but we shouldn't add overhead there unnecessarily.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:06):

Agreed

view this post on Zulip pnkfelix (Jul 14 2020 at 16:06):

having said that, we might consider making a branch of perf

view this post on Zulip pnkfelix (Jul 14 2020 at 16:06):

that we use locally to evaluate a prototype

view this post on Zulip pnkfelix (Jul 14 2020 at 16:07):

so that we have a shared understanding of what we are benchmarking.

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:07):

You can run perf locally, it's not necessarily the most streamlined experience but it does work fairly well once you have it set up.

view this post on Zulip davidtwco (Jul 14 2020 at 16:08):

I take from the current discussion that we're primarily interested in the performance implications of incr-comp; things such as making incr-comp bugs easier to reproduce and debug are somewhat secondary to the extent that addressing them isn't necessary for the primary goal of perf?

view this post on Zulip pnkfelix (Jul 14 2020 at 16:08):

@davidtwco that's an excellent point

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:09):

Re: PR throughput
I want to work on that infrastructure. I feel like there are some low hanging fruits (wrt throughput and other metrics) in perf.rlo, but I won't have time for that at least until November so don't mind me >.<

view this post on Zulip pnkfelix (Jul 14 2020 at 16:09):

I think making incr-comp bugs easier to reproduce and debug is something we should talk about

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:09):

That's the boring stuff so that's probably why it hasn't been talked about :slight_smile:

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:09):

But yeah, that stuff is really important

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:09):

We have a pretty large backlog of incr bugs

view this post on Zulip davidtwco (Jul 14 2020 at 16:09):

Having not thought too deeply about potential solutions, it seems hard.

view this post on Zulip pnkfelix (Jul 14 2020 at 16:09):

but I suspect any such work (on making incr-comp easier to repro+debug) is only going to be justified if its in service of making incr comp faster.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:09):

Hmm

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:10):

I would pose it a bit differently

view this post on Zulip pnkfelix (Jul 14 2020 at 16:10):

is the incr cache something that can be moved between host systems? I would expect it isn't, but if it is, or if it can be made portable, then maybe that's a way we could help make the bugs easier to repro

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:11):

Something that hadn't clicked for me until just now but most of the bugs I've seen are only reported because they ICE the compiler. People generally aren't complaining because incr-comp doesn't work as well as it should, they're complaining because it completely breaks rustc.

view this post on Zulip pnkfelix (Jul 14 2020 at 16:11):

at least in terms of having the compiler provide an easy way to archive (e.g. in a tar ball) the current incr cache, perhaps in response to an ICE

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:11):

Yas!

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:11):

That would be really nice

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:11):

So fixing the root cause that causes us to use bad incr-comp data would likely resolve a lot of the current complaints and issues and then we can focus on making it faster/better/smarter.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:12):

Yup

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:12):

I would pose it that way

view this post on Zulip davidtwco (Jul 14 2020 at 16:12):

Presumably we'd need some tooling to understand the contents of the incr-comp cache - I can't imagine how I'd determine right now whether the bug in a incr-comp ICE is what the compiler spat out last time, or what it is doing this time with that data.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:13):

Incr-comp needs to be valid always. Then, it can be as fast as possible. Like, speed is the target; not ICE-ing is a restriction of the problem :3

view this post on Zulip pnkfelix (Jul 14 2020 at 16:13):

its true: trying to make the incr-cache portable could be a real rabbit hole

view this post on Zulip pnkfelix (Jul 14 2020 at 16:14):

another potential option would be to actually record the history, as interpreted by the incr-cache, in the incr-cache

view this post on Zulip pnkfelix (Jul 14 2020 at 16:14):

and then when you have a bug, you could serialize just the edit history

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:14):

Yas

view this post on Zulip pnkfelix (Jul 14 2020 at 16:14):

and add that to the bug report

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:14):

Storing just the edit history should be fairly cheap in space

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:15):

(Unless you do a sweeping change I guess)

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:15):

I wonder if there's some kind of diagnostic routine we could write that would validate the incr-comp cache and report issues with it. We could invoke that as part of the ICE routine if the backtrace has some of the telltale incr-comp frames in it.

view this post on Zulip davidtwco (Jul 14 2020 at 16:15):

I think that would be best - then you can run the compiler with logging in the intermediate compiler invocations too. But not everyone will be able to share their source - though that's not specific to incr-comp bugs.

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:15):

Or the classic "tried to get index 12371239589231032 when slice len was 4"

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:16):

Which is 99% of the time an incr-comp issue

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:16):

Woah, that bad?

view this post on Zulip pnkfelix (Jul 14 2020 at 16:16):

I mean we don't see that kind of bug very often at all, apart from incr comp issues

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:16):

Well, it's just not a bug we normally generate anywhere else in the compiler.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:17):

I see. Wow.

view this post on Zulip pnkfelix (Jul 14 2020 at 16:17):

I wonder if we could change the message associated with that panic

view this post on Zulip pnkfelix (Jul 14 2020 at 16:17):

when it happens in rustc

view this post on Zulip pnkfelix (Jul 14 2020 at 16:17):

to say "this might be an incr-comp issue"

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:17):

That seems plausibly possible to me

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:17):

"Go <here> to report the problem"

view this post on Zulip pnkfelix (Jul 14 2020 at 16:17):

because part of the problem there is that the end-user doesn't even necessarily know that's a likely culprit

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:17):

Yas

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:18):

That should help a lot

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:18):

Yeah and by the time someone on the triage team realizes what's going on, they've blown away their cache

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:18):

Oh noes

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:18):

That's totally true

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:18):

:joy:

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:19):

Personally I would like to know if the issue is that the cache is wrong/corrupted or if we're triggering some kind of rare bug within the query system with valid data.

view this post on Zulip pnkfelix (Jul 14 2020 at 16:19):

really maybe every ICE should archive the incr cache

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:19):

In fact I think I even had such an issue while doing incremental work on mir-opt. It was so obscure that I ended up blowing up the entire cache and that fixed it

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:19):

Like maybe the data on disk is fine but we forget to update some index or something when we load it into the current compilation session and then later it goes off the rails

view this post on Zulip pnkfelix (Jul 14 2020 at 16:19):

(though that may lead to serious space blowup, given how much space the current incr cache uses already ...)

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:20):

Maybe it can be compressed!

view this post on Zulip davidtwco (Jul 14 2020 at 16:20):

Could earlier parts of the compiler not being querified result in different internal state (e.g. one more variant in an AdtDef) so that at the point where we start checking incr-comp data it causes the out-of-range indexing? I don't know enough about how we implement things to whether that could be the case.

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:20):

We probably don't need the MIR or llvm bitcode for the results.

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:21):

Which, I think are a fairly significant part of the disk cost.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:21):

If it is a cache, it must be in a fairly easy-to-digest form. I bet you can get a 50% reduction in size if not more with a common compression tool

view this post on Zulip pnkfelix (Jul 14 2020 at 16:23):

davidtwco said:

Could earlier parts of the compiler not being querified result in different internal state (e.g. one more variant in an AdtDef) so that at the point where we start checking incr-comp data it causes the out-of-range indexing? I don't know enough about how we implement things to whether that could be the case.

One would hope that the relevant portions of the incr-cache are invalidated in such scenarios, but that may indeed be part of the bugs in these cases (i..e situations where we are failing to invalidate sufficiently)

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:24):

I recall that there is some care taken to when choosing DepNodeIds (I think that's the right type) so that it doesn't change unnecessarily between compilations because those are the underlying keys into the incr cache (IIRC).

Edit: This is what I was thinking of https://github.com/rust-lang/rust/blob/master/src/librustc_middle/dep_graph/dep_node.rs

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:24):

"Naming and Cache invalidation are the two hardest problems in CS" xD

view this post on Zulip Wesley Wiser (Jul 14 2020 at 16:24):

Leaving that mostly just to try to point people toward the right thing.

view this post on Zulip Félix Fischer (Jul 14 2020 at 16:35):

(Fuck, Zulip mobile client is hard to use XD)


Last updated: Oct 21 2021 at 20:47 UTC