## Stream: t-compiler/wg-parallel-rustc

### Topic: transitive relation

nikomatsakis (Sep 16 2019 at 20:31, on Zulip):

Ping @Santiago Pastorino we could discuss possibly refactoring the transitive relation code here

Santiago Pastorino (Sep 16 2019 at 20:32, on Zulip):

hey

Santiago Pastorino (Sep 16 2019 at 20:32, on Zulip):

sure

Santiago Pastorino (Sep 16 2019 at 20:32, on Zulip):

I was finishing watching the recording

Santiago Pastorino (Sep 16 2019 at 20:33, on Zulip):

but yeah, already saw the transitive relation part :)

nikomatsakis (Sep 16 2019 at 20:34, on Zulip):

I'm not sure what I would do here either except that it feels sort of complex the way it is :)

Santiago Pastorino (Sep 16 2019 at 20:35, on Zulip):

I'd need to read a bit the code to see what's about, right now I can't even ask questions :)

simulacrum (Sep 16 2019 at 20:36, on Zulip):

@nikomatsakis Do I understand correctly that the transitive relation is essentially just saying that for a, b, c, if a <: b and b <:c then a <: c?

simulacrum (Sep 16 2019 at 20:38, on Zulip):

It does look like it's essentially tracking that along with querying that information

simulacrum (Sep 16 2019 at 20:40, on Zulip):

I was thinking that we might be able to store/manipulate this fairly optimally via https://en.wikipedia.org/wiki/Disjoint-set_data_structure with the addition that we "sort" the elements in each set

nikomatsakis (Sep 23 2019 at 19:29, on Zulip):

@simulacrum yes that is all that it is tracking, and yes it's not a super smart data structure. I mean for that matter, we could just .. do a DFS. It's typically pretty small sets.

nikomatsakis (Sep 23 2019 at 19:29, on Zulip):

I don't quite know what use disjoint set would have

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

isn't that more for "equality classes"? in particular, it doesn't capture ordering within a set, I don't think?

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

I think what'd start with is just removing the transitive computation and doing a DFS

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

and see how that performs :)

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

well, wait, there's a bit more to it

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

I remember there is some stuff, the postdom methods

nikomatsakis (Sep 23 2019 at 19:30, on Zulip):

that said, this is something we can totally make thread-safe, since it's redundant computation

simulacrum (Sep 23 2019 at 19:31, on Zulip):

Hm, I was thinking that we would sort within each set to maintain transitivity, but maybe that doesn't really make sense

Zoxc (Sep 23 2019 at 20:21, on Zulip):

Isn't this only used in the AST borrowchecker?

nikomatsakis (Sep 23 2019 at 20:45, on Zulip):

no, it's still used in NLL

nikomatsakis (Sep 23 2019 at 20:45, on Zulip):

anyway @simulacrum the elements of this set are named lifetimes like `'a`, `'b` -- so there usually aren't that many members

nikomatsakis (Sep 23 2019 at 20:48, on Zulip):

no, it's still used in NLL

hmm but, in NLL it's probably thread-local

nikomatsakis (Sep 23 2019 at 20:49, on Zulip):

ah well it still appears in the `TypeckTables`

nikomatsakis (Sep 23 2019 at 20:51, on Zulip):

the truth is that the most obvious change to make here would just be to improve how the thing itself works; e.g., use an `Arc` to store the computed transitive value and avoid holding the lock quite so long, but otherwise leave it

simulacrum (Sep 23 2019 at 20:57, on Zulip):

Ah if it's only named lifetimes (not inferred relations or so between anonymous lifetimes) then seems fine to just redo the calculations each time I imagine? Like, I can't imagine more than like 5 elements in these lists

simulacrum (Sep 23 2019 at 20:57, on Zulip):

Unless I'm missing something

nikomatsakis (Sep 23 2019 at 20:58, on Zulip):

well I think it can be more because it includes anonymous lifetimes

nikomatsakis (Sep 23 2019 at 20:58, on Zulip):

but yeah the magnitude is small

nikomatsakis (Sep 23 2019 at 20:58, on Zulip):

we could try just disabling caching and doing a perf run =)

nikomatsakis (Sep 23 2019 at 20:58, on Zulip):

just to see

simulacrum (Sep 23 2019 at 20:59, on Zulip):

Ah, so "anonymous lifetimes" sounds like not "named lifetimes" :)

simulacrum (Sep 23 2019 at 20:59, on Zulip):

But then yeah, I could see there being more - I can probably get a branch for a perf run w/o the cache put together

nikomatsakis (Sep 23 2019 at 21:00, on Zulip):

Ah, so "anonymous lifetimes" sounds like not "named lifetimes" :)

yeah so I really just mean "lifetime parameters"

Santiago Pastorino (Sep 26 2019 at 21:54, on Zulip):

was coming back to this but saw @simulacrum took care of it

Santiago Pastorino (Sep 26 2019 at 21:55, on Zulip):

great :)

simulacrum (Sep 26 2019 at 21:55, on Zulip):

It might not be done perse

simulacrum (Sep 26 2019 at 21:55, on Zulip):

I don't think Niko has reviewed PR?

Santiago Pastorino (Sep 26 2019 at 21:56, on Zulip):

probably not?

Santiago Pastorino (Sep 26 2019 at 21:56, on Zulip):

why did grammar regressed 25%?

simulacrum (Sep 26 2019 at 21:57, on Zulip):

https://github.com/rust-lang/rust/pull/64719

simulacrum (Sep 26 2019 at 21:57, on Zulip):

well, we _did_ remove caching

simulacrum (Sep 26 2019 at 21:57, on Zulip):

I haven't profiled though

Santiago Pastorino (Sep 26 2019 at 21:58, on Zulip):

ahh yeah but wall time is more or less the same

Santiago Pastorino (Sep 26 2019 at 21:58, on Zulip):

so you meant that there are more instructions being executed for that particular profile but it more or less takes the same time?

Santiago Pastorino (Sep 26 2019 at 21:59, on Zulip):

unsure I'm understanding what you meant

simulacrum (Sep 26 2019 at 22:05, on Zulip):

I'm saying that I don't know why there's such a big instruction regression for grammar beyond "less caching"

Santiago Pastorino (Sep 26 2019 at 23:24, on Zulip):
Santiago Pastorino (Sep 26 2019 at 23:25, on Zulip):

unsure if you can get and compare profile results for both commits on https://perf.rust-lang.org/

simulacrum (Sep 26 2019 at 23:27, on Zulip):

@Santiago Pastorino Not sure I follow you, which two commits do you want diff'd?

simulacrum (Sep 26 2019 at 23:28, on Zulip):

we can recollect and then there'll be self profile diff between master/new

Santiago Pastorino (Sep 26 2019 at 23:47, on Zulip):

@simulacrum wanted to compare between your branch and master

simulacrum (Sep 26 2019 at 23:47, on Zulip):

ah, yeah, we'll need another run for that -- I'll go start one

Santiago Pastorino (Sep 26 2019 at 23:47, on Zulip):

how you do that?

simulacrum (Sep 26 2019 at 23:48, on Zulip):

Just rerun perf :)

simulacrum (Sep 26 2019 at 23:48, on Zulip):

`@bors try @rust-timer queue`

Santiago Pastorino (Sep 26 2019 at 23:48, on Zulip):

I mean, but isn't that what you already did?

Santiago Pastorino (Sep 26 2019 at 23:48, on Zulip):

I think I'm not following you :)

Santiago Pastorino (Sep 26 2019 at 23:49, on Zulip):

of course one can do that easily locally just using perf

Santiago Pastorino (Sep 26 2019 at 23:49, on Zulip):

my question is ... `@bors try @rust-timer queue` seems to be showing that detailed view only of the PR

Santiago Pastorino (Sep 26 2019 at 23:49, on Zulip):

but I want to see the PR and master (the thing we are comparing against)

Santiago Pastorino (Sep 26 2019 at 23:50, on Zulip):

to see where is wasting more time the pr in comparison against master

simulacrum (Sep 26 2019 at 23:50, on Zulip):

Well so there's two things at play here

simulacrum (Sep 26 2019 at 23:50, on Zulip):

the perf run that I did on that PR was before we landed self-profile work

simulacrum (Sep 26 2019 at 23:50, on Zulip):

so that's why I'm recollecting

simulacrum (Sep 26 2019 at 23:51, on Zulip):

but to get the diff detailed query view you generally click on %change column on the compare page

Last update: Jan 21 2020 at 14:55UTC