Stream: wg-traits

Topic: performance regression from universes


nikomatsakis (Nov 26 2018 at 18:19, on Zulip):

So @scalexm have you thought at all about the performance regression you pointed me at?

nikomatsakis (Nov 26 2018 at 18:19, on Zulip):

I was going to take a look

scalexm (Nov 26 2018 at 18:19, on Zulip):

@nikomatsakis I opened a PR with a perf run

scalexm (Nov 26 2018 at 18:19, on Zulip):

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

scalexm (Nov 26 2018 at 18:20, on Zulip):

not sure if this will do

nikomatsakis (Nov 26 2018 at 18:20, on Zulip):

hard to imagine that this is the bottleneck

scalexm (Nov 26 2018 at 18:20, on Zulip):

well

scalexm (Nov 26 2018 at 18:20, on Zulip):

according to the original comment

nikomatsakis (Nov 26 2018 at 18:20, on Zulip):

I am wondering if the lack of "universe canonicalization" is causing problems

nikomatsakis (Nov 26 2018 at 18:20, on Zulip):

i.e., we're getting poorer cache behavior or something

scalexm (Nov 26 2018 at 18:20, on Zulip):

it seems like a lot of time is spent entering and exiting create_next_universe

nikomatsakis (Nov 26 2018 at 18:20, on Zulip):

yeah; my guess is more that the caller is executing too often

nikomatsakis (Nov 26 2018 at 18:21, on Zulip):

vs create_next_universe itself being too expensive

nikomatsakis (Nov 26 2018 at 18:21, on Zulip):

still, worth checking ;)

scalexm (Nov 26 2018 at 18:21, on Zulip):

mmh in that case that perf regression may have appeared earlier no?

scalexm (Nov 26 2018 at 18:22, on Zulip):

I mean earlier create_next_universe was not even called because the map was only [ty::UniverseIndex::from(0)]

nikomatsakis (Nov 26 2018 at 18:24, on Zulip):

hmm

nikomatsakis (Nov 26 2018 at 18:25, on Zulip):

maybe so

nikomatsakis (Nov 26 2018 at 18:25, on Zulip):

it's clearly that PR at fault:

nikomatsakis (Nov 26 2018 at 18:25, on Zulip):

Screen-Shot-2018-11-26-at-1.25.05-PM.png

scalexm (Nov 26 2018 at 18:27, on Zulip):

so to be clear

scalexm (Nov 26 2018 at 18:27, on Zulip):

there's something I cannot remember

scalexm (Nov 26 2018 at 18:27, on Zulip):

there was this comment above the creation of the universes map

scalexm (Nov 26 2018 at 18:27, on Zulip):
         // For each universe that is referred to in the incoming
        // query, create a universe in our local inference context. In
        // practice, as of this writing, all queries have no universes
        // in them, so this code has no effect, but it is looking
        // forward to the day when we *do* want to carry universes
        // through into queries.
scalexm (Nov 26 2018 at 18:27, on Zulip):

I think this was still true before my placeholders PR

scalexm (Nov 26 2018 at 18:28, on Zulip):

or maybe it was stale already because of https://github.com/rust-lang/rust/pull/55305 (universes refactor 3)

nikomatsakis (Nov 26 2018 at 18:29, on Zulip):

I believe we are currently putting all region variables into the root universe

nikomatsakis (Nov 26 2018 at 18:30, on Zulip):

when canonicalizing the query

scalexm (Nov 26 2018 at 18:30, on Zulip):

yes, and that will change only with your universes PR, right?

nikomatsakis (Nov 26 2018 at 18:30, on Zulip):
struct CanonicalizeAllFreeRegions;

impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions {
    fn canonicalize_free_region(
        &self,
        canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
        r: ty::Region<'tcx>,
    ) -> ty::Region<'tcx> {
        canonicalizer.canonical_var_for_region_in_root_universe(r)
    }

    fn any(&self) -> bool {
        true
    }
}
nikomatsakis (Nov 26 2018 at 18:30, on Zulip):

so it was probably true

nikomatsakis (Nov 26 2018 at 18:30, on Zulip):

my universes PR actually doesn't change this, but I am now wondering if it should, at least in combination with your PR

scalexm (Nov 26 2018 at 18:31, on Zulip):

Ok so the real change before the placeholders PR and after the placeholders PR is that the map is no more always equal to [UniverseIndex::ROOT]

nikomatsakis (Nov 26 2018 at 18:32, on Zulip):

we may want to back out the PR

nikomatsakis (Nov 26 2018 at 18:32, on Zulip):

so we can optimize "in peace"

nikomatsakis (Nov 26 2018 at 18:32, on Zulip):

still, I'm surprised that keccak is so heavily affected

nikomatsakis (Nov 26 2018 at 18:32, on Zulip):

I'm going to do a bit more digging I guess

scalexm (Nov 26 2018 at 18:32, on Zulip):

so the only ways I can think this would have regressed perf is:

nikomatsakis (Nov 26 2018 at 18:34, on Zulip):

I'm trying to remember, when are we even creating bound type variables?

nikomatsakis (Nov 26 2018 at 18:34, on Zulip):

I didn't expect this to happen much outside of chalk

scalexm (Nov 26 2018 at 18:34, on Zulip):

we are not, however InferCtxt tracks the universe where each type inference variable was created

nikomatsakis (Nov 26 2018 at 18:36, on Zulip):

ok I see

nikomatsakis (Nov 26 2018 at 18:36, on Zulip):

and those are now preserved

nikomatsakis (Nov 26 2018 at 18:36, on Zulip):

makes sense

scalexm (Nov 26 2018 at 18:36, on Zulip):

yes, unlike regions which are always put in the ROOT universe

scalexm (Nov 26 2018 at 18:36, on Zulip):

(when canonicalizing)

nikomatsakis (Nov 26 2018 at 18:37, on Zulip):

seems likely that universe canon would also help here

nikomatsakis (Nov 26 2018 at 18:37, on Zulip):

this does suggest that we could, in an emergency, land a PR that puts type variables into ROOT univese

nikomatsakis (Nov 26 2018 at 18:37, on Zulip):

to be fixed in a follow-up

scalexm (Nov 26 2018 at 18:37, on Zulip):

yes

nikomatsakis (Nov 26 2018 at 18:37, on Zulip):

that'd be nicer than having to back that big PR out

scalexm (Nov 26 2018 at 18:37, on Zulip):

I'm just waiting for the perf run to finish and if that does not solve the problem, let's do that

nikomatsakis (Nov 26 2018 at 18:38, on Zulip):

sounds good

scalexm (Nov 26 2018 at 19:16, on Zulip):

@nikomatsakis https://perf.rust-lang.org/compare.html?start=b51632e3f0856ea444f5e59819538e85947673fc&end=bb9bcfd67d1be59a17b58b07b9fa152266ef763f I never understand how to read this table

scalexm (Nov 26 2018 at 19:17, on Zulip):

does this mean that my PR actually decreased perfs by 50% more?

nikomatsakis (Nov 26 2018 at 19:17, on Zulip):

yes

nikomatsakis (Nov 26 2018 at 19:17, on Zulip):

which is a bit confusing :)

lqd (Nov 26 2018 at 19:17, on Zulip):

perf is ready looks red oh alexandre writing at the same time damn phone typing :3

scalexm (Nov 26 2018 at 19:17, on Zulip):

lol

scalexm (Nov 26 2018 at 19:17, on Zulip):

that was unexpected

nikomatsakis (Nov 26 2018 at 19:18, on Zulip):

indeed

nikomatsakis (Nov 26 2018 at 19:18, on Zulip):

I made a local build btw

nikomatsakis (Nov 26 2018 at 19:18, on Zulip):

to do some experimenting

nikomatsakis (Nov 26 2018 at 19:18, on Zulip):

though I realize now it's not optimized, so i can't compare perf measurements directly

nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

ok @scalexm I added some quick checks:

DEBUG 2018-11-26T19:26:47Z: rustc_traits::evaluate_obligation: evaluate_obligation(canonical_goal=Canonical {
    max_universe: U10992,
    variables: [
        CanonicalVarInfo {
            kind: Ty(
                General(
                    U10992
                )
            )
        }
    ],
    value: ParamEnvAnd {
        param_env: ParamEnv {
            caller_bounds: [],
            reveal: UserFacing
        },
        value: Binder(TraitPredicate(<[u64] as core::ops::Index<^1_0>>))
    }
})
nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

I'd say we need to do univ canonicalization :P

scalexm (Nov 26 2018 at 19:27, on Zulip):

lol ok

nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

I'd be up for trying to do that

nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

but i'm also up for someone else to do it

nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

trying to guesstimate my avail time this week:)

nikomatsakis (Nov 26 2018 at 19:27, on Zulip):

in theory I have more

scalexm (Nov 26 2018 at 19:28, on Zulip):

so I guess the perf problem just comes from the construction + allocation of the map

scalexm (Nov 26 2018 at 19:29, on Zulip):

I'll open a PR for putting back all type existentials in ROOT if -Z chalk is not there as you suggested

nikomatsakis (Nov 26 2018 at 19:30, on Zulip):

we can land it with p=1, please send me a link on zulip

nikomatsakis (Nov 26 2018 at 19:30, on Zulip):

OK, well, I think i'm going to go try and do reviews now.

nikomatsakis (Nov 26 2018 at 19:30, on Zulip):

still in "catch up" mode from vacation last week

nikomatsakis (Nov 26 2018 at 19:30, on Zulip):

I'll fix the universe PR though

scalexm (Nov 26 2018 at 19:39, on Zulip):

@nikomatsakis https://github.com/rust-lang/rust/pull/56251 I think that should do it

nikomatsakis (Nov 26 2018 at 19:40, on Zulip):

should we do a perf run?

nikomatsakis (Nov 26 2018 at 19:40, on Zulip):

/me sends bors try

scalexm (Nov 27 2018 at 00:16, on Zulip):

@nikomatsakis perf is green again

memoryruins (Nov 27 2018 at 05:33, on Zulip):

#56270 seems related

nikomatsakis (Nov 27 2018 at 15:23, on Zulip):

@scalexm if you have a build of the PR, maybe you can test #56270?

scalexm (Nov 27 2018 at 15:24, on Zulip):

@nikomatsakis mmh I haven't one :p

scalexm (Nov 27 2018 at 15:25, on Zulip):

but 99% sure this is the same issue

scalexm (Nov 27 2018 at 15:25, on Zulip):

there was #56274 too

scalexm (Nov 27 2018 at 15:27, on Zulip):

@nikomatsakis oh maybe you meant a build of the placeholders PR, not a build of the fix

nikomatsakis (Nov 27 2018 at 15:40, on Zulip):

I meant the fix

memoryruins (Nov 27 2018 at 23:12, on Zulip):

:) keccak-perf.png

Last update: Nov 12 2019 at 15:30UTC