Stream: t-compiler/wg-nll

Topic: issue-52028-memory-usage-in-html5ever


nikomatsakis (Jul 05 2018 at 18:06, on Zulip):

So I had this idea for optimizing html5ever

nikomatsakis (Jul 05 2018 at 18:06, on Zulip):

it basically just eliminates a big intermediate vector

nikomatsakis (Jul 05 2018 at 18:06, on Zulip):

it would have to I think build on my branch though.. probably ..

nikomatsakis (Jul 05 2018 at 18:06, on Zulip):

maybe not

davidtwco (Jul 05 2018 at 18:07, on Zulip):

I'll have a look at doing that then. Which branch would you recommend working from?

nikomatsakis (Jul 05 2018 at 18:08, on Zulip):

let me re-read my idae :)

nikomatsakis (Jul 05 2018 at 18:13, on Zulip):

ok so I would probably start from my PR

nikomatsakis (Jul 05 2018 at 18:13, on Zulip):

just because

nikomatsakis (Jul 05 2018 at 18:13, on Zulip):

I dont' think there's anything in there that you need

nikomatsakis (Jul 05 2018 at 18:13, on Zulip):

this PR I mean https://github.com/rust-lang/rust/pull/51987

nikomatsakis (Jul 05 2018 at 18:14, on Zulip):

but it seems like that will land

nikomatsakis (Jul 05 2018 at 18:14, on Zulip):

and you'd probably get merge conflicts otherwise

nikomatsakis (Jul 05 2018 at 18:34, on Zulip):

@David Wood let me know how it goes; in the meantime, I'm going to open up an issue about the region error stuff and try to leave some notes

davidtwco (Jul 05 2018 at 18:35, on Zulip):

Sounds good, just building your branch to get started.

Jake Goulding (Jul 06 2018 at 00:34, on Zulip):

That's a single 12 GiB allocation happening

LOL

davidtwco (Jul 06 2018 at 18:18, on Zulip):

@nikomatsakis So I'm looking at this issue - what do you envision we replace Vec<(ty::Region<'tcx>, Location)> with? I've been trying with SparseBitMatrix<RegionVid, LocationIndex> but there's some places where the Vec was iterated over and I'm not sure how to use the SparseBitMatrix in that context?

davidtwco (Jul 06 2018 at 18:18, on Zulip):

Tried a handful of things and never got much of anywhere.

nikomatsakis (Jul 06 2018 at 18:32, on Zulip):

I envisioned using RegionValues I think

nikomatsakis (Jul 06 2018 at 18:33, on Zulip):

right now though, constructing a RegionValues requires knowing the total number of region variables

nikomatsakis (Jul 06 2018 at 18:35, on Zulip):

I'm not sure exactly how I would alter the API; I debated around a few things

nikomatsakis (Jul 06 2018 at 18:36, on Zulip):

I think I'd probably make it so that it doesn't know the number of variables and just instantiates them on demand

davidtwco (Jul 06 2018 at 18:36, on Zulip):

This implies to me that -- to start -- we could refactor so that type check generates the initial liveness results (storing in a sparse bit set per variable) directly. This would effectively replace the liveness_set vector that we have today. We would then hand that off to the region inference context

I read this and went and looked for sparse bit sets.

davidtwco (Jul 06 2018 at 18:51, on Zulip):

I think I've got it to check now with a SparseBitMatrix but I've no idea if it is correct or better in any way.

davidtwco (Jul 06 2018 at 18:51, on Zulip):

(or what you wanted at all)

nikomatsakis (Jul 06 2018 at 19:13, on Zulip):

@David Wood you're on the right track

nikomatsakis (Jul 06 2018 at 19:13, on Zulip):

I forgot that it used a SparseBitMatrix though

nikomatsakis (Jul 06 2018 at 19:14, on Zulip):

we'd have to modify that type to grow dynamically too

nikomatsakis (Jul 06 2018 at 19:14, on Zulip):

if we want this behavior

nikomatsakis (Jul 06 2018 at 19:14, on Zulip):

which...seems ok?

nikomatsakis (Jul 06 2018 at 19:14, on Zulip):

is all of this making any sense? :)

davidtwco (Jul 06 2018 at 19:14, on Zulip):

It didn't use a SparseBitMatrix before, I introduced one here because that's what I figured you meant.

davidtwco (Jul 06 2018 at 19:14, on Zulip):

I had no idea it wouldn't grow dynamically - this'll probably fail in that case.

nikomatsakis (Jul 06 2018 at 19:15, on Zulip):

sorry, I meant that RegionValues uses one

nikomatsakis (Jul 06 2018 at 19:16, on Zulip):

are you familiar with the RegionValues type?

nikomatsakis (Jul 06 2018 at 19:16, on Zulip):

(is that even the right name...)

nikomatsakis (Jul 06 2018 at 19:16, on Zulip):

https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/borrow_check/nll/region_infer/values/struct.RegionValues.html

davidtwco (Jul 06 2018 at 19:16, on Zulip):

Don't recall using it, I'm not using that just now.

nikomatsakis (Jul 06 2018 at 19:16, on Zulip):

this is the type we ultimately use to store the liveness results in the region inference context

nikomatsakis (Jul 06 2018 at 19:17, on Zulip):

this might be a place where it's useful to step back and talk about the regon inferene cx is setup

nikomatsakis (Jul 06 2018 at 19:17, on Zulip):

if you wanted, we could do a quick "guided tour"

nikomatsakis (Jul 06 2018 at 19:17, on Zulip):

(and I could tape it)

nikomatsakis (Jul 06 2018 at 19:17, on Zulip):

but it'd have to be ... kind of now

nikomatsakis (Jul 06 2018 at 19:17, on Zulip):

anyway, this the field of the inference context where the liveness values are stored

nikomatsakis (Jul 06 2018 at 19:18, on Zulip):

what we do right now is to first build up the liveness values into this big array, and then transfer them into there

davidtwco (Jul 06 2018 at 19:18, on Zulip):

I can probably do that.

nikomatsakis (Jul 06 2018 at 19:18, on Zulip):

and what I am proposing is kind of building up that field during typeck

davidtwco (Jul 06 2018 at 19:20, on Zulip):

Here's what I changed: https://gist.github.com/davidtwco/f6fece99fb433a7506633dbdb321b4ab

davidtwco (Jul 06 2018 at 19:20, on Zulip):

Pretty certain it's the wrong direction.

nikomatsakis (Jul 06 2018 at 19:21, on Zulip):

yeah .. right direction maybe but I think we can do it .. I hope .. more easily?

davidtwco (Jul 06 2018 at 19:21, on Zulip):

That would be nice.

nikomatsakis (Jul 06 2018 at 19:21, on Zulip):

I am pondering a bit what I think the right steps are

davidtwco (Jul 06 2018 at 19:22, on Zulip):

Sure thing.

nikomatsakis (Jul 06 2018 at 19:22, on Zulip):

but yeah if you wanted I can kind of give you a quick overview of the total "information flow" here

davidtwco (Jul 06 2018 at 19:23, on Zulip):

That'd be helpful I reckon.

nikomatsakis (Jul 06 2018 at 19:23, on Zulip):

you want to do that now?

nikomatsakis (Jul 06 2018 at 19:23, on Zulip):

/me tries to decide if he has time

nikomatsakis (Jul 06 2018 at 19:23, on Zulip):

I'm leaving for a vacation tomorrow so got a few things to get done :)

davidtwco (Jul 06 2018 at 19:23, on Zulip):

If you've got time, I'm around now.

davidtwco (Jul 06 2018 at 19:24, on Zulip):

But it's not super important so don't bother if you've not.

nikomatsakis (Jul 06 2018 at 19:24, on Zulip):

let me ask you a different question

nikomatsakis (Jul 06 2018 at 19:25, on Zulip):

we could also discuss some the idea of how to improve the region errors

nikomatsakis (Jul 06 2018 at 19:25, on Zulip):

specifically this:

davidtwco (Jul 06 2018 at 19:25, on Zulip):

Whichever you'd prefer I work on, I've not got a particular preference.

nikomatsakis (Jul 06 2018 at 19:25, on Zulip):

I have been meaning to write things up about it but haven't gotten to it

nikomatsakis (Jul 06 2018 at 19:26, on Zulip):

hmm

nikomatsakis (Jul 06 2018 at 19:27, on Zulip):

ok let's do something quickly

nikomatsakis (Jul 06 2018 at 19:27, on Zulip):

let's talk about this issue since I think it's a bit more obvious

nikomatsakis (Jul 06 2018 at 19:27, on Zulip):

and anyway my PR didn't land yet :)

nikomatsakis (Jul 06 2018 at 19:27, on Zulip):

I'll try to write something up about that over the weekend

nikomatsakis (Jul 06 2018 at 19:28, on Zulip):

https://appear.in/i-heart-rust

nikomatsakis (Jul 06 2018 at 20:01, on Zulip):

@David Wood will be live at https://youtu.be/DqojDh9kFdI once processing is complete; it's also in the playlist

davidtwco (Jul 07 2018 at 19:45, on Zulip):

@nikomatsakis I create let elements = &Rc::new(RegionValueElements::new(mir, universal_regions.len())); and pass it into type_check::type_check which passes it into type_check::type_check_internal which makes the RegionValues. What should I do with these lines where I don't have a universal_regions?

davidtwco (Jul 07 2018 at 19:45, on Zulip):

I can't find a nice way do it without everything ending up wrapped in Option.

nikomatsakis (Jul 07 2018 at 20:05, on Zulip):

@David Wood you may want to add it to the BorrowCheckContext

nikomatsakis (Jul 07 2018 at 20:05, on Zulip):

I added that at some point precisely because everything was getting wrapped up in options

nikomatsakis (Jul 07 2018 at 20:06, on Zulip):

see e.g. this section

davidtwco (Jul 07 2018 at 20:06, on Zulip):

Oh yeah, that would work, I'd considered that at some point but for some reason thought otherwise.

davidtwco (Jul 07 2018 at 20:10, on Zulip):

Ah, so I think why I got tripped up with that was that it made it difficult to instantiate the MirTypeckRegionConstraints in TypeChecker::new() since it now takes a RegionValues - which I'm instantiating there and that requires a elements.

davidtwco (Jul 07 2018 at 20:10, on Zulip):

And wrapping that in Option is a pain as that's the return value of type_check::type_check.

nikomatsakis (Jul 07 2018 at 20:14, on Zulip):

Ah, I see. Still, those are only used in the borrow check mode.

nikomatsakis (Jul 07 2018 at 20:14, on Zulip):

I wonder if we should jus move those into the BorrowCheckContext

nikomatsakis (Jul 07 2018 at 20:14, on Zulip):

e.g., with an &mut

nikomatsakis (Jul 07 2018 at 20:14, on Zulip):

I've contemplated doing so before

nikomatsakis (Jul 07 2018 at 20:15, on Zulip):

the whole setup feels a bit wonky, like it could be realigned, but I am not entirely sure how :)

davidtwco (Jul 07 2018 at 20:16, on Zulip):

What's the type check mir pass used for?

nikomatsakis (Jul 07 2018 at 20:16, on Zulip):

it's a sanity check

nikomatsakis (Jul 07 2018 at 20:16, on Zulip):

it checks that we generate well-formed MIR

nikomatsakis (Jul 07 2018 at 20:16, on Zulip):

but it doesn't consider regions etc

nikomatsakis (Jul 07 2018 at 20:17, on Zulip):

it's gonna go away once NLL lands

nikomatsakis (Jul 07 2018 at 20:17, on Zulip):

since NLL does the same thing

nikomatsakis (Jul 07 2018 at 20:17, on Zulip):

and then some

nikomatsakis (Jul 07 2018 at 20:17, on Zulip):

I suppose we could have it create the RegionValueElements etc but ...

nikomatsakis (Jul 07 2018 at 20:18, on Zulip):

or alternatively you could imagine removing it, and instead just having the MIR-based borrow check always run, but stop early if not enabled

nikomatsakis (Jul 07 2018 at 20:18, on Zulip):

that'd probably be the way to go

davidtwco (Jul 07 2018 at 20:18, on Zulip):

Even if I put the elements as close as possible to where it is used, at that point the universal regions is in an Option and I've got the same issue.

nikomatsakis (Jul 07 2018 at 20:18, on Zulip):

I'm reluctant to remove it altogher both because it's useful and because it would make NLL performance look worse :stuck_out_tongue:

nikomatsakis (Jul 07 2018 at 20:19, on Zulip):

I don't think I quite understand

nikomatsakis (Jul 07 2018 at 20:19, on Zulip):

can you send me your diff? :)

nikomatsakis (Jul 07 2018 at 20:19, on Zulip):

(or, better, the commit)

nikomatsakis (Jul 07 2018 at 20:19, on Zulip):

and maybe the compiler error

davidtwco (Jul 07 2018 at 20:21, on Zulip):
error[E0425]: cannot find value `elements` in this scope
   --> librustc_mir/borrow_check/nll/type_check/mod.rs:737:57
    |
737 |                 liveness_constraints: RegionValues::new(elements),
    |                                                         ^^^^^^^^ not found in this scope

error[E0308]: mismatched types
  --> librustc_mir/borrow_check/nll/constraint_generation.rs:43:56
   |
43 |     cg.add_region_liveness_constraints_from_type_check(liveness_set_from_typeck);
   |                                                        ^^^^^^^^^^^^^^^^^^^^^^^^ expected slice, found struct `borrow_check::nll::region_infer::values::RegionValues`
   |
   = note: expected type `&[(&rustc::ty::RegionKind, rustc::mir::Location)]`
              found type `&borrow_check::nll::region_infer::values::RegionValues<rustc::ty::RegionVid>`

error: aborting due to 2 previous errors

Here's a branch with a WIP commit: https://github.com/davidtwco/rust/tree/issue-52028

davidtwco (Jul 07 2018 at 20:22, on Zulip):

What I was suggesting though was that if I move where I create elements such that it's created inside the type_check module and returned alongside the RegionValues (which could work..) then at the point where I'd create elements, the number of universal regions is within the Option<BorrowCheckContext> and therefore the issue just manifests itself slightly differently.

davidtwco (Jul 07 2018 at 20:23, on Zulip):

The second error there can be ignored, I've just not around to dealing with that part of the code.

nikomatsakis (Jul 07 2018 at 20:23, on Zulip):

I think you should move the creation into the BorrowCheckContext struct

nikomatsakis (Jul 07 2018 at 20:23, on Zulip):

and not have a return value

nikomatsakis (Jul 07 2018 at 20:23, on Zulip):

so e.g. BorrowCheckContext could have a &mut MirTypeckRegionConstraints<'tcx>

davidtwco (Jul 07 2018 at 20:23, on Zulip):

I see.

nikomatsakis (Jul 07 2018 at 20:24, on Zulip):

there are two places that we write to constraints

davidtwco (Jul 07 2018 at 20:24, on Zulip):

Yeah, alright, I'll give that a go.

nikomatsakis (Jul 07 2018 at 20:24, on Zulip):

one of them already checked that BorrowCheckConstraints is Some

nikomatsakis (Jul 07 2018 at 20:24, on Zulip):

the other one could have done :)

nikomatsakis (Jul 07 2018 at 20:24, on Zulip):

basically the same as the &mut AllFacts that's already in there

davidtwco (Jul 07 2018 at 20:36, on Zulip):

That worked, thanks.

davidtwco (Jul 09 2018 at 21:08, on Zulip):

@nikomatsakis Submitted https://github.com/rust-lang/rust/pull/52190 for this. Not passing the tests yet, but the bulk of it is there.

lqd (Jul 09 2018 at 21:11, on Zulip):

@David Wood awesome :D

nikomatsakis (Jul 12 2018 at 05:05, on Zulip):

@David Wood nice! (I'm still on vacation, trying to catch up a bit though -- beginning with rebasing https://github.com/rust-lang/rust/pull/51987)

davidtwco (Jul 12 2018 at 18:43, on Zulip):

@nikomatsakis rebased

lqd (Jul 12 2018 at 19:34, on Zulip):

(tiny typo during the rebase if you haven't seen it yet)

davidtwco (Jul 12 2018 at 19:46, on Zulip):

@lqd oops, thanks, completely forgot to do a check on it before pushing.

lqd (Jul 12 2018 at 19:48, on Zulip):

:)

davidtwco (Jul 12 2018 at 19:52, on Zulip):

Alright, fixed.

davidtwco (Jul 13 2018 at 09:24, on Zulip):

It occurs to me looking at this that I misread your initial message and it wasn't instruction to rebase over that PR again (though it was required so it didn't hurt to do).

nikomatsakis (Jul 13 2018 at 16:17, on Zulip):

@David Wood so it seems like https://github.com/rust-lang/rust/pull/51987 has landed; you may want to rebase atop master now

davidtwco (Jul 13 2018 at 17:12, on Zulip):

Rebased ontop of master now.

nikomatsakis (Jul 14 2018 at 04:51, on Zulip):

@David Wood left a first round of review, just looking at the changes to make SparseBitMatrix lazy

nikomatsakis (Jul 14 2018 at 05:01, on Zulip):

ok, left a second round of feedback on the rest

davidtwco (Jul 16 2018 at 11:35, on Zulip):

Put a PR in that should have resolved those issues. I've not had much time to look into the failure that's happening just now. Will try to get to that tonight.

nikomatsakis (Jul 16 2018 at 11:41, on Zulip):

@David Wood to clarify, you mean the same PR, right?

davidtwco (Jul 16 2018 at 11:58, on Zulip):

Ah, yeah, I meant to say commit.

davidtwco (Jul 16 2018 at 11:58, on Zulip):

Too late to edit now.

nikomatsakis (Jul 16 2018 at 12:05, on Zulip):

@David Wood did you ever figure out what those travis errors are about? Do you want me to take a look? It might just be "things happening in a slightly different order"

davidtwco (Jul 16 2018 at 12:28, on Zulip):

I haven't had a chance to properly dig in.

davidtwco (Jul 16 2018 at 12:29, on Zulip):

Its the visited vec in some of the SCC functions.

davidtwco (Jul 16 2018 at 12:29, on Zulip):

If you have time and want to take a look I don't mind.

nikomatsakis (Jul 16 2018 at 12:37, on Zulip):

I'll clone it

nikomatsakis (Jul 16 2018 at 15:08, on Zulip):

@David Wood so far most of the errors I see are ICEs relating to the lazy bit set code. I'm fixing those bit by bit. This mess of bitsets is SUCH a candidate for being pulled out to an external crate where it can be properly vetted and tested...

davidtwco (Jul 16 2018 at 15:12, on Zulip):

By lazy bit set do you mean the type underpinning the SparseBitMatrix or the changes to the SparseBitMatrix?

nikomatsakis (Jul 16 2018 at 15:19, on Zulip):

the changes that make it grow automatically, I mean

nikomatsakis (Jul 16 2018 at 15:20, on Zulip):

I'm now past the obvious ICEs

nikomatsakis (Jul 16 2018 at 15:20, on Zulip):

will push those

nikomatsakis (Jul 16 2018 at 15:20, on Zulip):

now getting new errors ;)

davidtwco (Jul 16 2018 at 15:22, on Zulip):

The only ICE I was seeing (at least with the test I was looking at) was the visited vector being empty when it wasn't supposed to be in the SCC code. Given that I didn't get a chance to work that out, I wasn't aware that the bit matrix changes had any issues. Though, perhaps I just had to find time to dig deeper.

nikomatsakis (Jul 16 2018 at 15:24, on Zulip):

pushed a commit or two

nikomatsakis (Jul 16 2018 at 15:30, on Zulip):

@David Wood I'm investigating the remaining ICEs

nikomatsakis (Jul 16 2018 at 15:31, on Zulip):

PS we should talk about further region error reporting work too ... :)

nikomatsakis (Jul 16 2018 at 15:41, on Zulip):

ah, I see the problem

nikomatsakis (Jul 16 2018 at 15:41, on Zulip):

I didn't read the resize_with rustdocs closely enough :)

nikomatsakis (Jul 16 2018 at 15:41, on Zulip):

it will sometimes truncate!

davidtwco (Jul 16 2018 at 15:50, on Zulip):

Ah. I'm not sure if I checked the ICE last night after it finished building successfully because it was late.

davidtwco (Jul 16 2018 at 15:50, on Zulip):

So the ICE may have changed.

nikomatsakis (Jul 16 2018 at 15:53, on Zulip):

I think it all works now

davidtwco (Jul 16 2018 at 16:01, on Zulip):

Great!

nikomatsakis (Jul 16 2018 at 16:02, on Zulip):

at least src/test/ui passes :)

davidtwco (Jul 17 2018 at 07:41, on Zulip):

Apologies for not being able to wrap up those last few issues. Did we see much of an impact from the change with the memory usage?

lqd (Jul 17 2018 at 08:30, on Zulip):

for sure

lqd (Jul 17 2018 at 08:32, on Zulip):

(and not only memory apparently)

davidtwco (Jul 17 2018 at 08:52, on Zulip):

@lqd does it say the memory diff on perf.rust-lang?

lqd (Jul 17 2018 at 08:53, on Zulip):

yes let me get you a link

lqd (Jul 17 2018 at 08:53, on Zulip):

https://perf.rust-lang.org/compare.html?start=3d5753fda1ee8f729da1061e931e13b043f479a5&end=c1ea2d1eb1304c9d8de16b74ae863a8e1e58cd2f&stat=max-rss

lqd (Jul 17 2018 at 08:54, on Zulip):

at the bottom left there is a selector for which perf stat you want to show

davidtwco (Jul 17 2018 at 09:08, on Zulip):

Ah, thanks. Wasn't sure which one was memory usage.

davidtwco (Jul 17 2018 at 09:08, on Zulip):

Hopefully someone can have bors try again with that PR soon.

lqd (Jul 17 2018 at 09:14, on Zulip):

yeah it's a known travis issue at 6-7AM :) I've had it before; we can ping someone on the infra team if they're available (they might be sleeping :)

lqd (Jul 17 2018 at 09:35, on Zulip):

(alrighty, it's been retried)

nikomatsakis (Jul 17 2018 at 11:03, on Zulip):

still, the perf is atrocious :( I had hoped reducing the peak memory usage would do it, but apparently not. I expect though that the #52034 change that @DPC is working on may have a big effect

nikomatsakis (Jul 17 2018 at 11:03, on Zulip):

also, 2GB is still ungreat.

nikomatsakis (Jul 17 2018 at 11:03, on Zulip):

I wonder if there is much we can do to improve further

nikomatsakis (Jul 17 2018 at 11:04, on Zulip):

seems almost certainly yes, would have to do a more compressed representation though

nikomatsakis (Jul 17 2018 at 11:14, on Zulip):

perhaps something that takes advantage of repeated substructure, like a BDD

lqd (Jul 17 2018 at 11:21, on Zulip):

did we ever profile html5ever ?

nikomatsakis (Jul 17 2018 at 11:22, on Zulip):

I was just getting started on that

nikomatsakis (Jul 17 2018 at 11:22, on Zulip):

I'm going to build w/ @David Wood's branch

lqd (Jul 17 2018 at 11:22, on Zulip):

I don't remember us doing so

lqd (Jul 17 2018 at 11:22, on Zulip):

yeah

lqd (Jul 17 2018 at 11:22, on Zulip):

esp because of the OOMs I mean

lqd (Jul 17 2018 at 11:22, on Zulip):

hopefully it's liveness so that 52034 fixes it

nikomatsakis (Jul 17 2018 at 11:26, on Zulip):

started builds

nikomatsakis (Jul 17 2018 at 11:26, on Zulip):

well I expect liveness is a big part of it and that #52034 will help

nikomatsakis (Jul 17 2018 at 11:26, on Zulip):

let me review what njn wrote...

nikomatsakis (Jul 17 2018 at 11:27, on Zulip):

ah, yes, precompute_borrows_out_of_scope, our old friend

nikomatsakis (Jul 17 2018 at 14:42, on Zulip):

@lqd html5ever perf profile is kind of interesting:

athena. perf focus '{do_mir_borrowck}' --tree-callees --tree-max-depth 3 --tree-min-percent 5 --relative
Matcher    : {do_mir_borrowck}
Matches    : 5379
Not Matches: 739
Percentage : 100%

Tree
| matched `{do_mir_borrowck}` (100% total, 0% self)
: | rustc_mir::borrow_check::nll::compute_regions (51% total, 0% self)
: : | rustc_mir::borrow_check::nll::type_check::type_check (47% total, 0% self)
: : : | rustc_mir::borrow_check::nll::type_check::liveness::generate (47% total, 0% self) [...]
: | rustc_mir::dataflow::impls::borrows::Borrows::new (31% total, 3% self)
: : | <std::collections::hash::map::HashMap<K, V, S>>::insert (14% total, 7% self)
: : : | <std::collections::hash::map::HashMap<K, V, S>>::try_resize (6% total, 4% self) [...]
: : | <rustc_mir::borrow_check::nll::region_infer::values::RegionValues<N>>::contains (12% total, 12% self)
: | <rustc_mir::borrow_check::MirBorrowckCtxt<'cx, 'gcx, 'tcx> as rustc_mir::dataflow::DataflowResultsConsumer<'cx, 'tcx>>::visit_statement_entry (15% total, 0% self)
: : | rustc_mir::borrow_check::MirBorrowckCtxt::consume_operand (5% total, 0% self)
: : : | rustc_mir::borrow_check::MirBorrowckCtxt::access_place (5% total, 0% self) [...]
: : | rustc_mir::borrow_check::MirBorrowckCtxt::mutate_place (5% total, 0% self)
: : : | rustc_mir::borrow_check::MirBorrowckCtxt::access_place (5% total, 0% self) [...]
lqd (Jul 17 2018 at 14:43, on Zulip):

RegionValues::contains :thinking_face:

nikomatsakis (Jul 17 2018 at 14:43, on Zulip):

this may mean that @DPC's work on #52034 will be huge -- depends on how much of the liveness::generate is from variables that contain regions

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

well, that is I think from the code that figures out the "lifetime" of each borrow

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

it does a DFS from the start of the borrow

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

and watches out for exits from the region

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

there is definitely something kind of "ugh" there

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

because we then later do a dataflow

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

which essentially duplicates that work

nikomatsakis (Jul 17 2018 at 14:44, on Zulip):

but I'm not sure how to do better than the DFS per borrow yet

nikomatsakis (Jul 17 2018 at 14:45, on Zulip):

we could remove the dataflow later on, though it doesn't seem to be particularly high on any profile

nikomatsakis (Jul 17 2018 at 14:45, on Zulip):

just silly

lqd (Jul 17 2018 at 14:45, on Zulip):

do we have a way of guesstimating how many of these liveness requests are actually from variables with regions ?

nikomatsakis (Jul 17 2018 at 14:45, on Zulip):

the DFS itself could be coded more efficiently I imagine

nikomatsakis (Jul 17 2018 at 14:45, on Zulip):

hard to tell; I can check the mir-dump debug info I suppose

lqd (Jul 17 2018 at 14:46, on Zulip):

it's gonna be huge

nikomatsakis (Jul 17 2018 at 14:46, on Zulip):

indeed

nikomatsakis (Jul 17 2018 at 14:46, on Zulip):

running that now

nikomatsakis (Jul 17 2018 at 14:46, on Zulip):

there must be some huge fn

nikomatsakis (Jul 17 2018 at 14:46, on Zulip):

I suspect that a lot of those variables contain regions

nikomatsakis (Jul 17 2018 at 14:46, on Zulip):

because we seem to have a lot of loans to trace out :)

lqd (Jul 17 2018 at 14:47, on Zulip):

now I'm intrigued what the offending code looks like in html5ever :D

nikomatsakis (Jul 17 2018 at 14:48, on Zulip):

heh indeed

nikomatsakis (Jul 17 2018 at 14:50, on Zulip):

well, I see 38% of total execution time spent traversing types, looking for regions that are live

nikomatsakis (Jul 17 2018 at 14:51, on Zulip):

you already added the "quick check" that skips that if there are no live regions

nikomatsakis (Jul 17 2018 at 14:51, on Zulip):

hmm

nikomatsakis (Jul 17 2018 at 14:52, on Zulip):

I wonder if it would be faster to "invert" the liveness code

nikomatsakis (Jul 17 2018 at 14:52, on Zulip):

I am trying to remember :) I seem to recall this being true in a previous compiler I worked on

nikomatsakis (Jul 17 2018 at 14:52, on Zulip):

that is, traditional liveness figures out the liveness of all variables at each point

nikomatsakis (Jul 17 2018 at 14:52, on Zulip):

but another way to do it is to look for any given variable and find the points where it is live

nikomatsakis (Jul 17 2018 at 14:52, on Zulip):

we are more interested in that in the end

nikomatsakis (Jul 17 2018 at 14:53, on Zulip):

i.e., you could imagine creating a SparseBitSet for each variable that has regions in its type

lqd (Jul 17 2018 at 14:53, on Zulip):

oh interesting

nikomatsakis (Jul 17 2018 at 14:53, on Zulip):

iterating over all uses of the variable and walking backwards from each one

nikomatsakis (Jul 17 2018 at 14:53, on Zulip):

annoyingly, we don't have a ready index for that

nikomatsakis (Jul 17 2018 at 14:53, on Zulip):

but I suppose we could build one in a single O(n) walk

nikomatsakis (Jul 17 2018 at 14:53, on Zulip):

the advantage would be:

nikomatsakis (Jul 17 2018 at 14:54, on Zulip):

we get a bitset for each variable

nikomatsakis (Jul 17 2018 at 14:54, on Zulip):

then we iterate the regions within the variable ONCE

nikomatsakis (Jul 17 2018 at 14:54, on Zulip):

and or the entire bitset into them

nikomatsakis (Jul 17 2018 at 14:54, on Zulip):

instead of what we do now, which is to iterate the regions in the variable at each point and add a single bit

nikomatsakis (Jul 17 2018 at 14:55, on Zulip):

in other words, there is a sort of impedance mismatch right now with the current setup

nikomatsakis (Jul 17 2018 at 14:55, on Zulip):

this may also simplify the "Drop live" vs "Use live" distinction

nikomatsakis (Jul 17 2018 at 14:55, on Zulip):

that is, we would basically walk backwards from drops -- if we encounter a USE, that converts into a USE LIVE, but it's all still part of a single visit

nikomatsakis (Jul 17 2018 at 14:55, on Zulip):

right now we actually compute liveness TWICE I think

nikomatsakis (Jul 17 2018 at 14:56, on Zulip):

yeah, this seems like a win

nikomatsakis (Jul 17 2018 at 14:56, on Zulip):

or at least worth a try

lqd (Jul 17 2018 at 14:57, on Zulip):

sounds worth a try indeed!

nikomatsakis (Jul 17 2018 at 14:58, on Zulip):

sort of sad to have two bits of liveness code but ... c'est la vie

lqd (Jul 17 2018 at 15:02, on Zulip):

I do wonder if the behavior with html5ever is a rare incident or if it's a pattern we already encounter at a smaller scale, maybe hidden in the perf overhead we're seeing elsewhere

nikomatsakis (Jul 17 2018 at 15:05, on Zulip):

yeah

nikomatsakis (Jul 17 2018 at 15:05, on Zulip):

hard to know

nikomatsakis (Jul 17 2018 at 15:05, on Zulip):

it is certainly also true for tuple-stress

nikomatsakis (Jul 17 2018 at 15:06, on Zulip):

but that case has an easy fix (ignore non-region variables)

lqd (Jul 17 2018 at 15:08, on Zulip):

yeah. maybe I'll look at this crate a bit later as well (I remember it needs bigger stack sizes to build because of heavy macro/syn/quote usage :)

lqd (Jul 17 2018 at 15:47, on Zulip):

(hehe the current version of html5ever cargo checks just fine in 2s, 30x faster than this 2y old version)

simulacrum (Jul 17 2018 at 15:52, on Zulip):

the non-NLL version cargo checks in 1.8 seconds :)

nikomatsakis (Jul 17 2018 at 15:53, on Zulip):

opened up https://github.com/rust-lang/rust/issues/52460

nikomatsakis (Jul 17 2018 at 15:53, on Zulip):

still, @lqd, that is very interesting

nikomatsakis (Jul 17 2018 at 15:53, on Zulip):

in particular, when we talk about our NLL performance targets

nikomatsakis (Jul 17 2018 at 15:53, on Zulip):

we really want to check current crates :)

simulacrum (Jul 17 2018 at 15:55, on Zulip):

Generally speaking though optimizing NLL for the pain points (e.g. this html5ever) may bring wins to the other crates which is why I think it's worth it

lqd (Jul 17 2018 at 15:56, on Zulip):

yeah, on the one hand we're lucky that the old version showcases a pathological case in rustc, and on the other, lucky that people will, hopefully, have a better experience than one might think just looking at the nll perf dashboard :)

lqd (Jul 17 2018 at 15:57, on Zulip):

oh for sure @simulacrum

simulacrum (Jul 17 2018 at 15:58, on Zulip):

I'm sure there are new crates that have the same pathological behavior too

lqd (Jul 17 2018 at 16:04, on Zulip):

maybe some of the ones which OOMed during the crater run

Last update: Nov 21 2019 at 23:25UTC