Stream: t-compiler

Topic: dep-graph design meeting prep


mw (Oct 29 2019 at 09:50, on Zulip):

Hello @Zoxc, @nikomatsakis, and anyone else from @T-compiler/meeting who is interested! I'd like to prepare for the design meeting this Friday so we can make progress there and hopefully unblock https://github.com/rust-lang/rust/pull/60035.

Here are questions I have:

Maybe it would also help to walk through the steps that happen when trying to execute a query that turns out to be red.

Zoxc (Oct 29 2019 at 10:46, on Zulip):

I'd like a little bit more detail. Is no part of the existing file overwritten? If so, what does this mean for reading such a file?

Normally no part of the existing file overwritten, except when garbage collection occurs, then the entire file is rewritten to remove redundant changes.

You'd read such a file from start to finish.

Zoxc (Oct 29 2019 at 10:50, on Zulip):

When and how are changes written to new dep-graph?

Changes to the dep graph is buffered and when the buffer is full it is sent to a background worker. That worker then encodes the changes and appends them to the file. When debugging / testing the dep graph, the background worker also builds an in memory copy. When the compiler is done it flushes the buffer and asks for the background worker to finish, and that will also return the in memory copy for use in testing back to the main thread.

Zoxc (Oct 29 2019 at 10:51, on Zulip):

Does this approach involve copying the dep-graph file before modifying it?

Yes, but we already copy the entire incremental state, so that's not a regression.

Zoxc (Oct 29 2019 at 10:56, on Zulip):

Some PR comments mention garbage collection. What exactly is collected?

The dep graph file with the list of changes is garbage collected. We can't keep appending to the dep graph file forever, so we need to remove stuff from it at some point. It's probably the simplest implementation of a key value store, we could change it later to something more advanced that doesn't require garbage collection.

Is the plan to have "garbage collection" compilation sessions that take longer?

The garbage collection happens in the background thread which loads the dep graph. If there's free CPU cores, it shouldn't affect overall compilation time.

mw (Oct 29 2019 at 11:30, on Zulip):

how is the file encoded? Is it a list of (DepNode, [DepNode]) pairs?

mw (Oct 29 2019 at 11:34, on Zulip):

what's the algorithm for garbage collection? is garbage collection done during each session?

Zoxc (Oct 29 2019 at 11:44, on Zulip):

The file is basically Vec<Action>, https://github.com/rust-lang/rust/blob/9f268ad2f5009213d5f33fea02d359536cc89cec/src/librustc/dep_graph/serialized.rs#L341

When the dep graph is loaded, how much wasted space is calculated, and if it's above a ratio, garbage collection is triggered. Garbage collection reads the dep graph file again and records the byte location of the changes we'd want to keep, combining them if possible. Then it writes the changes out again.

Zoxc (Oct 29 2019 at 11:46, on Zulip):

GC algorithm: https://github.com/rust-lang/rust/blob/9f268ad2f5009213d5f33fea02d359536cc89cec/src/librustc/dep_graph/serialized.rs#L85
Method which computes what to keep: https://github.com/rust-lang/rust/blob/9f268ad2f5009213d5f33fea02d359536cc89cec/src/librustc/dep_graph/serialized.rs#L30

Zoxc (Oct 29 2019 at 12:16, on Zulip):

The dep node result hashes are stored in a separate file as an array indexed by DepNodeIndexand is written each session as it changes more often.

mw (Oct 29 2019 at 13:22, on Zulip):

The dep node result hashes are stored in a separate file as an array indexed by DepNodeIndexand is written each session as it changes more often.

So the entire array is loaded into memory (together with the previous dep-graph) and then the entire array is written to disk at the end of the session again, correct?

Zoxc (Oct 29 2019 at 13:28, on Zulip):

There's 2 arrays, but yes.

mw (Oct 29 2019 at 13:28, on Zulip):

2 arrays in what sense?

mw (Oct 29 2019 at 13:29, on Zulip):

that the "old" array is kept around immutably?

mw (Oct 29 2019 at 13:30, on Zulip):

And the serialized version of the dep-graph is a stream of Action where an Action is a list of additions and updates, with each entry in the list being conceptually { idx: DepNodeIndex, stable_id: DepNode, deps: [DepNodeIndex] }?

mw (Oct 29 2019 at 13:32, on Zulip):

Is there a reason that Action is an enum of New, Update, Invalidate? Could it also be just one Set variant, so to speak?

Zoxc (Oct 29 2019 at 13:40, on Zulip):

that the "old" array is kept around immutably?

Yeah.

And the serialized version of the dep-graph is a stream of Action where an Action is a list of additions and updates, with each entry in the list being conceptually { idx: DepNodeIndex, stable_id: DepNode, deps: [DepNodeIndex] }?

Pretty much.

Is there a reason that Action is an enum of New, Update, Invalidate? Could it also be just one Set variant, so to speak?

The Update variant is encoded on disk without the DepNode part, so it's more space efficient.

nikomatsakis (Oct 29 2019 at 14:13, on Zulip):

do we have a hackmd document anywhere?

nikomatsakis (Oct 29 2019 at 14:13, on Zulip):

if not, can we create one and start to sketch out the plan based on these notes?

mw (Oct 29 2019 at 14:51, on Zulip):

The Update variant is encoded on disk without the DepNode part, so it's more space efficient.

OK, makes sense.

mw (Oct 29 2019 at 15:48, on Zulip):

How does this look to you? https://hackmd.io/@michaelwoerister/HkbS9CHqS/edit

mw (Oct 29 2019 at 15:50, on Zulip):

Ideally much of the answers to the questions in there would go into the rustc-guide and/or source-level documentation.

nikomatsakis (Oct 31 2019 at 12:56, on Zulip):

It looks good, @mw , except that we have no idea what the answers are :)

nikomatsakis (Oct 31 2019 at 12:56, on Zulip):

Well, presumably @Zoxc has some thoughts

nikomatsakis (Oct 31 2019 at 12:56, on Zulip):

I guess I meant I don't know

nikomatsakis (Oct 31 2019 at 12:59, on Zulip):

I added one question, which has to do with a rust-analyzer-like model and live-updates

nikomatsakis (Oct 31 2019 at 13:00, on Zulip):

@mw -- remind me, with today's incremental, do we completely regenerate the dep-graph every time?

i.e., we load the old dep-graph and then selectively copy over into the new one what we need, then write out the end reuslt?

nikomatsakis (Oct 31 2019 at 13:00, on Zulip):

And when/where/how do we use garbage collection today?

nikomatsakis (Oct 31 2019 at 13:00, on Zulip):

(Is that in the rustc-guide docs...? I should maybe go check first :)

mw (Oct 31 2019 at 13:01, on Zulip):

mw -- remind me, with today's incremental, do we completely regenerate the dep-graph every time?

i.e., we load the old dep-graph and then selectively copy over into the new one what we need, then write out the end reuslt?

that is true.

mw (Oct 31 2019 at 13:01, on Zulip):

the garbage collection happens naturally as part of "selectively copy[ing] over into the new one"

nikomatsakis (Oct 31 2019 at 13:02, on Zulip):

ok. If my understanding of what @Zoxc is proposing is correct, I think that this would still be true

nikomatsakis (Oct 31 2019 at 13:02, on Zulip):

I'm going to maybe add some notes at the top -- "summary of the proposal"

nikomatsakis (Oct 31 2019 at 13:02, on Zulip):

I think that is currently .. well, there is none?

nikomatsakis (Oct 31 2019 at 13:03, on Zulip):

maybe there are some comments?

mw (Oct 31 2019 at 13:03, on Zulip):

yes, please edit the doc, it should be world-writable

nikomatsakis (Oct 31 2019 at 13:05, on Zulip):

I'm editing -- another question that occurs to me, regarding motivation -- what are the goals

nikomatsakis (Oct 31 2019 at 13:06, on Zulip):

do we have measurements?

mw (Oct 31 2019 at 13:07, on Zulip):

@nnethercote has done some analysis regarding memory usage

mw (Oct 31 2019 at 13:07, on Zulip):

that is in the PR

mw (Oct 31 2019 at 13:07, on Zulip):

we also want to avoid the cost of having to re-write the whole dep-graph.

mw (Oct 31 2019 at 13:08, on Zulip):

I don't have numbers on that at hand

nikomatsakis (Oct 31 2019 at 13:08, on Zulip):

we also want to avoid the cost of having to re-write the whole dep-graph.

to be clear, it's not so much that we're avoiding that cost

nikomatsakis (Oct 31 2019 at 13:08, on Zulip):

we're just kind of spreading it out over time, right?

nikomatsakis (Oct 31 2019 at 13:08, on Zulip):

(and maybe in a background thread)

mw (Oct 31 2019 at 13:09, on Zulip):

well, only changes are written so the cost of writing the unchanged parts is avoided

mw (Oct 31 2019 at 13:09, on Zulip):

not sure how exactly garbage collection plays into that

nikomatsakis (Oct 31 2019 at 13:11, on Zulip):

well, only changes are written so the cost of writing the unchanged parts is avoided

ok I missed that part

nikomatsakis (Oct 31 2019 at 13:11, on Zulip):

yes it seems like we would want to begin by explaining exactly how that works

nikomatsakis (Oct 31 2019 at 13:12, on Zulip):

it seems like gc is the key question -- i.e., how do we avoid the time to load the old depgraph growing ever longer?

mw (Oct 31 2019 at 13:13, on Zulip):

yes

eddyb (Oct 31 2019 at 13:14, on Zulip):

I'd argue thresholds/quotas is the way to go

mw (Oct 31 2019 at 13:14, on Zulip):

loading the dep-graph happens in a background, so that becoming more costly won't show as long as it is "fast enough"

mw (Oct 31 2019 at 13:15, on Zulip):

but writing and loading the dep-graph is not super expensive even now

mw (Oct 31 2019 at 13:15, on Zulip):

e.g. here we have only a few percent for each: https://perf.rust-lang.org/detailed-query.html?commit=c553e8e8812c19809e70523064989e66c5cfd3f1&benchmark=inflate-debug&run_name=clean%20incremental

mw (Oct 31 2019 at 13:15, on Zulip):

memory is the bigger issue, I think

nikomatsakis (Oct 31 2019 at 13:21, on Zulip):

comparing the perf results from May 7 I see largely regressions (though a max of like 8%), but I'm not sure if I'm being misled because of instruction count and parallelism

nikomatsakis (Oct 31 2019 at 13:22, on Zulip):

walltime seems to show small gains, so perhaps so?

nikomatsakis (Oct 31 2019 at 13:22, on Zulip):

I can't tell if that's a parallel compiler run

nikomatsakis (Oct 31 2019 at 13:28, on Zulip):

ok, well, I updated the hackmd to the best of my ability, but there are definitely some areas where @Zoxc would have to weigh in. @Zoxc, if you are able, it'd be great if you could update the hackmd with answers to:

nikomatsakis (Oct 31 2019 at 13:30, on Zulip):

@mw by "partial updates", I think you mean things like a rust-analyzer scenario, where we don't do a single "main compilation"?

nikomatsakis (Oct 31 2019 at 13:34, on Zulip):

ok, I made a few more updates, coallescing some questions and leaving some notes that I think are accurate

nikomatsakis (Oct 31 2019 at 13:34, on Zulip):

I'm done for now :)

mw (Oct 31 2019 at 13:35, on Zulip):

with partial updates I mean mainly updating the incremental cache for compilation sessions that error

mw (Oct 31 2019 at 13:36, on Zulip):

this question is not a high priority for me though.

nikomatsakis (Oct 31 2019 at 13:36, on Zulip):

ah yes very good

nikomatsakis (Oct 31 2019 at 13:36, on Zulip):

I hadn't thought about it but that is indeed kind of a "special case" of the rust-analyzer scenario, isn't it?

mw (Oct 31 2019 at 13:37, on Zulip):

I guess so, yes.

mw (Oct 31 2019 at 13:37, on Zulip):

there are probably some additional questions about correctness in any "partial update" scenario

mw (Oct 31 2019 at 13:38, on Zulip):

(did we get rid of query cycles yet? I hope so :))

eddyb (Oct 31 2019 at 13:39, on Zulip):

hey @mw did I show you cyclotron? it's a memoizer, that computes fixpoints when it hits cycles :)

eddyb (Oct 31 2019 at 13:39, on Zulip):

probably too inefficient/silly to use in the compiler, and potentially unsound in certain situations

eddyb (Oct 31 2019 at 13:40, on Zulip):

works for fixing left-recursion in parsing though,,,

nikomatsakis (Oct 31 2019 at 14:14, on Zulip):

did I show you cyclotron? it's a memoizer, that computes fixpoints when it hits cycles :)

I've debated about this for salsa -- this is of course kind of what trait solving winds up doing -- but I don't think it's correct in all cases

eddyb (Oct 31 2019 at 14:18, on Zulip):

trait solving is also probably more efficient at computing those fixpoints, whereas all I do is repeat the "head" of the cycle until it stops changing

Zoxc (Oct 31 2019 at 14:26, on Zulip):

move to a rust-analyzer like model, with live updates

I'm not sure what this entails

nikomatsakis (Nov 01 2019 at 13:27, on Zulip):

trait solving is also probably more efficient at computing those fixpoints, whereas all I do is repeat the "head" of the cycle until it stops changing

yes, although there are prolog impl's that take that approach

pnkfelix (Nov 01 2019 at 13:32, on Zulip):

there's something in this conversation that may be obvious but I don't think anyone's pointed it out explicitly:

pnkfelix (Nov 01 2019 at 13:33, on Zulip):

some have noted the primary driver for the work is to reduce memory usage (or at least peak memory usage?)

pnkfelix (Nov 01 2019 at 13:34, on Zulip):

the reason this is a memory usage issue, if I understand correctly, is that we have two graphs (that are likely to be approximately the same size and shape) in memory at once

pnkfelix (Nov 01 2019 at 13:34, on Zulip):

and therefore the "best" improvement in memory usage one could hope to achieve is to halve the impact in mem usage from incremental compilation

pnkfelix (Nov 01 2019 at 13:35, on Zulip):

do I have that right? (I'm not saying that a 50% reduction is not worthwhile! but I just want to make sure I understand.)

nikomatsakis (Nov 01 2019 at 13:37, on Zulip):

I believe that is correct, @pnkfelix

nikomatsakis (Nov 01 2019 at 13:38, on Zulip):

@mw with respect to how garbage collection works... @Zoxc wrote this:

The garbage collection algorithm reads the dep graph and records the location of information we want to keep. It then clears the file and writes only the useful information back. It is precise and happens in the background thread. The cost of garbage collection is similar to loading the dep graph, so it’s unlikely we’ll block on it.

I think what this means (@Zoxc can confirm) is that we:

nikomatsakis (Nov 01 2019 at 13:39, on Zulip):

one thing I did not yet fully understand -- is the dep-graph stored in one big file that we (ordinarily) append to?

nikomatsakis (Nov 01 2019 at 13:39, on Zulip):

and -- if we do a GC -- we fully rewrite it?

nikomatsakis (Nov 01 2019 at 13:39, on Zulip):

Basically, one thing I would like to spend time on in the meeting is the on-disk format, which is still not really covered at all

mw (Nov 01 2019 at 13:41, on Zulip):

@nikomatsakis Yes, I was mainly wondering about "case two" in the document: unused nodes. How are those identified?

nikomatsakis (Nov 01 2019 at 13:42, on Zulip):

@mw presumably they are just not marked?

nikomatsakis (Nov 01 2019 at 13:42, on Zulip):

that's basically how it works today, no?

mw (Nov 01 2019 at 13:42, on Zulip):

Are they reliably "invalidated" somewhere else?

nikomatsakis (Nov 01 2019 at 13:42, on Zulip):

except that the "marking" is done "on the fly"

mw (Nov 01 2019 at 13:42, on Zulip):

I tried to find something in the PR that looks like such a marking phase, but I cannot find it

pnkfelix (Nov 01 2019 at 13:43, on Zulip):

well, is the GC scheme implemented?

mw (Nov 01 2019 at 13:43, on Zulip):

yes, here: https://github.com/rust-lang/rust/pull/60035/files#diff-ad7502063d3dee7dc215765da3e83c58R85

mw (Nov 01 2019 at 13:44, on Zulip):

I can see how this takes care of overwritten nodes, but I'm not sure how unreferenced nodes are handled

pnkfelix (Nov 01 2019 at 13:46, on Zulip):

I do see bits of code in the PR that seem like its looping over all the nodes and setting their state to DepNodeState::Invalid; I would think this is like setting all the mark-bits to "unmarked" in a normal GC?

pnkfelix (Nov 01 2019 at 13:47, on Zulip):

Am I wrong about the purpose of those loops? Or are you just saying you cannot see where they are called (because I will admit that I haven't looked into that yet)

mw (Nov 01 2019 at 13:50, on Zulip):

@pnkfelix that could be -- I don't have a clear picture of how things play together exactly

pnkfelix (Nov 01 2019 at 13:51, on Zulip):

yeah, I'm clearly in a similar boat. The invalidation loops I was looking at are themselves fired off by Action::InvalidateNodes commands that I infer must be in the file itself ... so I feel like I must have misunderstood their purpose.

Last update: Nov 20 2019 at 01:50UTC