Stream: wg-async-foundations

Topic: #65147 check_mod_item_types slowdown


tmandry (Oct 08 2019 at 17:35, on Zulip):

I just confirmed that the slowdown is indeed inside check_item_type for opaque types

simulacrum (Oct 08 2019 at 18:58, on Zulip):

@tmandry I guess digging in by just commenting and rebuilding would be the next step unfortunately -- maybe you could try eprintln!(...) at some random places since the number of queries executed is low

tmandry (Oct 08 2019 at 22:18, on Zulip):

ah, so the PR that @nagisa linked does indeed seem to fix this issue

tmandry (Oct 08 2019 at 22:21, on Zulip):

that's.. a crazy speedup

nagisa (Oct 08 2019 at 23:28, on Zulip):

glad my wikipedia could save you some effort!

tmandry (Oct 09 2019 at 01:24, on Zulip):

ah, nevermind.. I may have been confused

nagisa (Oct 09 2019 at 01:25, on Zulip):

Welp. I was worried that it would not help, as the stack trace you have is in an entirely different place.

nagisa (Oct 09 2019 at 01:25, on Zulip):

but perhaps something similar in the location you are seeing issues would be beneficial

tmandry (Oct 09 2019 at 01:28, on Zulip):

yeah, maybe

tmandry (Oct 09 2019 at 01:28, on Zulip):

it happens when checking for cycles inside opaque types

tmandry (Oct 09 2019 at 01:29, on Zulip):

which is one of the backtraces I posted yesterday, but I wasn't sure then

tmandry (Oct 09 2019 at 01:29, on Zulip):

https://github.com/rust-lang/rust/blob/f3c9cece7b6829e6fd7854a1aee6a1619a81a38c/src/librustc/ty/util.rs#L694

tmandry (Oct 09 2019 at 01:32, on Zulip):

which I think actually delegates to some of the code changed in that PR (the substs.fold_with(self))

simulacrum (Oct 09 2019 at 01:33, on Zulip):

It would be good to be sure that that expander is responsible (easiest way is probably to comment it out)

simulacrum (Oct 09 2019 at 01:34, on Zulip):

though I suspect you are right that it is

tmandry (Oct 09 2019 at 01:59, on Zulip):

working on double checking that..

tmandry (Oct 09 2019 at 01:59, on Zulip):

in the meantime, I tried building with the stage 1 compiler and it complains about not finding std

tmandry (Oct 09 2019 at 02:05, on Zulip):

cargo also doesn't get put in stage1/bin, so I symlinked it (we use cargo for third-party crates right now)

tmandry (Oct 09 2019 at 02:06, on Zulip):

but when it comes to rustbuild hackery I mostly have no idea what I'm doing :smiley:

tmandry (Oct 09 2019 at 02:23, on Zulip):

double checked and the slowdown is definitely happening inside check_opaque_for_cycles, btw

tmandry (Oct 09 2019 at 02:24, on Zulip):

I added a log to see all the types it folds.. this may have been a mistake :D

tmandry (Oct 09 2019 at 02:32, on Zulip):

https://gist.githubusercontent.com/tmandry/f172f0ac2f2bfc21d0e3fc1b89eeb9d6/raw/acdeeceda8145a650f081e30eba86fd4a8e5501d/rustc.log

tmandry (Oct 09 2019 at 02:32, on Zulip):

there's the type that kills rustc

tmandry (Oct 09 2019 at 05:01, on Zulip):

(actually nevermind what I said about the stage1 compiler.. I'm able to build the target I care about with it)

tmandry (Oct 09 2019 at 06:09, on Zulip):

So I'm thinking that when one OpaqueTypeExpander visits >3 billion types, something's gone wrong?

tmandry (Oct 09 2019 at 06:14, on Zulip):

here's a log of try_expand_impl_trait_type, search for seen=

tmandry (Oct 09 2019 at 06:14, on Zulip):

produced by this code

tmandry (Oct 09 2019 at 06:15, on Zulip):

some very gnarly types in there..

tmandry (Oct 09 2019 at 06:29, on Zulip):

cc @Matthew Jasper

tmandry (Oct 09 2019 at 06:33, on Zulip):

to summarize, try_expand_impl_trait_type takes a long time on some nasty types produced by deep async fn call stacks; see the two links I pasted above, as well as #65147

tmandry (Oct 09 2019 at 18:57, on Zulip):

that type has 386 regions...

Matthew Jasper (Oct 09 2019 at 19:22, on Zulip):

A couple of things to try:

  1. Change this to else if t.has_projections() { ... } else { t }https://github.com/rust-lang/rust/blob/9b91bef78b15dfecc5144b0575f40a2d84ea795a/src/librustc/ty/util.rs#L738
  2. Store a cache of opaque types and what they expand to in the visitor.
tmandry (Oct 09 2019 at 22:27, on Zulip):

@Matthew Jasper thank you. your first suggestion helped a lot!

tmandry (Oct 09 2019 at 22:28, on Zulip):

it brought the number of types visited down from 3 billion to a modest 21 million :smile:

tmandry (Oct 09 2019 at 22:28, on Zulip):

more importantly, the compile time is sane again

tmandry (Oct 09 2019 at 22:45, on Zulip):

it's still a significant regression from a month ago, so I'm working on tracking down what changed.

tmandry (Oct 10 2019 at 02:35, on Zulip):

oh wow, adding a cache brought it down to around a thousand, and the compile time is better than it ever was before :smiley:

tmandry (Oct 10 2019 at 03:16, on Zulip):

@Matthew Jasper can you explain why (1) is correct? like, what if I had Vec<Foo::Item>, or Vec<Bar> where Bar is an existential type?

tmandry (Oct 10 2019 at 03:20, on Zulip):

(I'm assuming having generic params is not considering having projections.. but maybe I'm wrong)

Matthew Jasper (Oct 10 2019 at 11:33, on Zulip):

has_projections will return true for both of those type: it recurses on the generic arguments of a type. So Vec<impl X> has_projections because impl X has_projections.

Matthew Jasper (Oct 10 2019 at 11:36, on Zulip):

Type flags are cached so calling has_projections doesn't have to do the recursion here.

tmandry (Oct 10 2019 at 22:10, on Zulip):

ohh, makes sense, thanks!

nagisa (Oct 10 2019 at 22:37, on Zulip):

Well done!

nagisa (Oct 10 2019 at 22:37, on Zulip):

Nothing beats the feeling making O(unreasonable) a N(effectively 1) :D

tmandry (Oct 15 2019 at 18:29, on Zulip):

@Matthew Jasper Can you take another look at #65293 today? I think it's ready to go

Matthew Jasper (Oct 15 2019 at 18:31, on Zulip):

Have you forgotten to push? I can't see any changes since I reviewed.

tmandry (Oct 15 2019 at 19:17, on Zulip):

@Matthew Jasper sigh.. yes, sorry about that. my tracking branch was misconfigured somehow.

tmandry (Oct 15 2019 at 19:19, on Zulip):

it's pushed now.

Last update: Nov 18 2019 at 00:40UTC