Stream: t-compiler

Topic: [CGU Partitioning] merge strategy


pnkfelix (May 22 2020 at 15:35, on Zulip):

@Wesley Wiser here is a variation of the current strategy I was just musing about

pnkfelix (May 22 2020 at 15:35, on Zulip):

I'll start with an assumption that we have, or can build, a graph between cgu's representing reference relationships

pnkfelix (May 22 2020 at 15:36, on Zulip):

e.g. if cgu A calls a method defined by cgu B, then there's an edge there

pnkfelix (May 22 2020 at 15:36, on Zulip):

so now here's the idea: label each edge with the sum of the estimated code size for each side of the edge

pnkfelix (May 22 2020 at 15:37, on Zulip):

and then, instead of merging the absolute lowest sized pairs of cgu's

pnkfelix (May 22 2020 at 15:37, on Zulip):

instead, take the edge with the lowest value and merge its ends together. Then update the sums on the other edges accordingly

pnkfelix (May 22 2020 at 15:38, on Zulip):

the intention here is that we would be trying to merge together things that would actually benefit from being in the same cgu

Wesley Wiser (May 22 2020 at 15:39, on Zulip):

In that they use many of the same functions so they can share definitions?

pnkfelix (May 22 2020 at 15:39, on Zulip):

Now, to be fair, this may not yield a compile-time win. In fact, the only way I could imagine it yielding a compile-time win would be if it shifts effort being done by LTO

pnkfelix (May 22 2020 at 15:39, on Zulip):

Wesley Wiser said:

In that they use many of the same functions so they can share definitions?

no, as in A uses a function from B

Nathan Corbyn (May 22 2020 at 15:39, on Zulip):

Isn’t this the same algorithm just only considering pairs with edges between them?

pnkfelix (May 22 2020 at 15:39, on Zulip):

Nathan Corbyn said:

Isn’t this the same algorithm just only considering pairs with edges between them?

yes it is

pnkfelix (May 22 2020 at 15:40, on Zulip):

pnkfelix said:

Wesley Wiser said:

In that they use many of the same functions so they can share definitions?

no, as in A uses a function from B

I mean, yes, A will be able to use the definition from B

pnkfelix (May 22 2020 at 15:40, on Zulip):

the main reason why I am thinking along these lines

davidtwco (May 22 2020 at 15:40, on Zulip):

Intuitively, this makes sense to me.

Nathan Corbyn (May 22 2020 at 15:40, on Zulip):

So this shouldn’t be too much work on top of the current impl as long as we can build the graph?

Nathan Corbyn (May 22 2020 at 15:41, on Zulip):

That’s cool

pnkfelix (May 22 2020 at 15:41, on Zulip):

is that longer term, I think we will want to experiment with finer-grained cgu's (like letting someone try per-fn cgu)

pnkfelix (May 22 2020 at 15:41, on Zulip):

but per-fn cgu will be terrible in the current merging scheme

pnkfelix (May 22 2020 at 15:41, on Zulip):

(I think)

Wesley Wiser (May 22 2020 at 15:41, on Zulip):

Yeah, I had to disable the merging in my hacky branch.

Nathan Corbyn (May 22 2020 at 15:42, on Zulip):

Does rustc build a call graph for MIR already?

Nathan Corbyn (May 22 2020 at 15:42, on Zulip):

I’m not sure I understand why we don’t do this already

Wesley Wiser (May 22 2020 at 15:47, on Zulip):

pnkfelix said:

Now, to be fair, this may not yield a compile-time win. In fact, the only way I could imagine it yielding a compile-time win would be if it shifts effort being done by LTO

Oh, I see what you're saying. Yeah, that would make a lot of sense.

Wesley Wiser (May 22 2020 at 15:48, on Zulip):

I've been focusing on trying to make cargo build faster so I didn't even consider it from the code-quality perspective.

pnkfelix (May 22 2020 at 16:53, on Zulip):

by the way, @Wesley Wiser , do you know why the cargo-debug incr-patched println benchmark regressed by 50% with your branch (#71349) to make one-cgu-per-item (that is what it did, right? I'm trying to infer based on a skim of the diff...)

Wesley Wiser (May 22 2020 at 16:57, on Zulip):

That's what I was trying to do but from looking at the trace data, I can see that I didn't quite hit the mark.

Wesley Wiser (May 22 2020 at 16:58, on Zulip):

I think this was the main issue https://github.com/rust-lang/rust/pull/71349/files#diff-d8017c239ab8ef69c6c46e6035930e01R612

Wesley Wiser (May 22 2020 at 16:58, on Zulip):

I wasn't able to figure out exactly what I needed to do to get non-local items to link against a different CGU

Wesley Wiser (May 22 2020 at 17:00, on Zulip):

I have another branch where I think I resolved that by making everything Linkage::LinkOnce and Visibility::Default but IIRC that had bad performance because we spent a lot longer linking.

Last update: May 29 2020 at 17:00UTC