Stream: t-compiler/wg-nll

Topic: issue-51821


Eh2406 (Jun 27 2018 at 16:22, on Zulip):

Reposting to start a new topic.
So while that runs I see 2 questions, that I may be able to answer for myself with a working editor, but you may just know:
1, how does the vec constraints end up calling add_region?
2, is ConstraintIndex use anywhere? The places IndexVec are added to from 51821 don't record it.

Eh2406 (Jun 27 2018 at 16:38, on Zulip):

The answer to both is compute_region_values and ConstraintIndex is also used in build_dependency_map

nikomatsakis (Jun 27 2018 at 16:54, on Zulip):

@Eh2406 I'm back now, what's current status?

Eh2406 (Jun 27 2018 at 16:55, on Zulip):

just drafting a question for you...

Eh2406 (Jun 27 2018 at 16:58, on Zulip):

I see two ways to read your instructions,
a: use a FxHashSet<(RegionVid, RegionVid)> to make add_region approximately NOP on repeated inputs.
b: use a FxHashSet<(RegionVid, RegionVid)>to not add duplicate items to constraints in the first place.
witch did you have in mind?

nikomatsakis (Jun 27 2018 at 17:03, on Zulip):

@Eh2406 I did not mean modifying anything at the level of add_region

nikomatsakis (Jun 27 2018 at 17:03, on Zulip):

I am not entirely sure where I do think we should modify

nikomatsakis (Jun 27 2018 at 17:03, on Zulip):

but i'd probably start by just not adding duplicate items to constraints

nikomatsakis (Jun 27 2018 at 17:04, on Zulip):

the only potential issue I can see is that we may want to have extra information for error reporting -- i.e., the duplciate constraints arise for different reasons, and maybe some make sense more than others -- but we can cross that bridge when we come to it

nikomatsakis (Jun 27 2018 at 17:04, on Zulip):

in particular we're nowhere near smart enough to make use of that anyway :)

Eh2406 (Jun 27 2018 at 17:07, on Zulip):

Ok, that prompts the question. Is vec the correct data structure for a set of things without duplicates.

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

yes, it does. There are some advantages. For example, we currently thread a linked list through the vector

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

using the indices

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

so that when one thing is dirty

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

we can quickly find the "dependent" constraints

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

that said, we used to build up a hashmap for that same purpose

nikomatsakis (Jun 27 2018 at 17:08, on Zulip):

I removed it as an optimization — but it turned out I was misinterpreting the profiles and it didn't really gain much

nikomatsakis (Jun 27 2018 at 17:09, on Zulip):

still, there is another argument in favor of a vector, which is that there is add'l data in each constraint that is not part of the "key" we use for uniqueness

nikomatsakis (Jun 27 2018 at 17:09, on Zulip):

though you could represent that with a FxHashMap<Key, ExtraData>

nikomatsakis (Jun 27 2018 at 17:09, on Zulip):

still, i'd probably try inserting the FxHashSet to start

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

actually what I would prefer to see I think is for us to isolate out the "set of constraints" into a data structure of its own (in its own submodule, ideally :)

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

and then we can tinker...

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

e.g., that same file could encapsulate the logic of threading dirty constraints around...

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

but regardless of whether we encapsulate or not

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

it seems good to start with the simple thing (a set + the vec we have) and then we can measure the delta

nikomatsakis (Jun 27 2018 at 17:10, on Zulip):

of alternative choices

Eh2406 (Jun 27 2018 at 17:12, on Zulip):

Ok, I will start with something small.

Eh2406 (Jun 27 2018 at 17:13, on Zulip):

still, there is another argument in favor of a vector, which is that there is add'l data in each constraint that is not part of the "key" we use for uniqueness

That data will also be lost if we remove duplicates from the vec.

nikomatsakis (Jun 27 2018 at 17:18, on Zulip):

sure, but not for the entry we keep

nikomatsakis (Jun 27 2018 at 17:19, on Zulip):

this is what I was saying before about "the only potential issue I can see is that we may want to have extra information for error reporting..."

Eh2406 (Jun 27 2018 at 18:21, on Zulip):

Ok so I have a draft with a new field of RegionInferenceContext seen_constraints: FxHashSet<(RegionVid, RegionVid)>,
but it allocates a new vector in new

Jake Goulding (Jun 27 2018 at 18:22, on Zulip):

Vec::new has no heap allocation, so that may be ok?

nikomatsakis (Jun 27 2018 at 18:23, on Zulip):

well presumably it populates it too

Eh2406 (Jun 27 2018 at 18:24, on Zulip):

ah that does not save us this time, we are copying a bunch into it.

nikomatsakis (Jun 27 2018 at 18:24, on Zulip):

@Eh2406 right, so this is why I was talking about extracting out to a new data structure for a "Set of constraints"

nikomatsakis (Jun 27 2018 at 18:24, on Zulip):

so that we can create it before type check begins

nikomatsakis (Jun 27 2018 at 18:24, on Zulip):

and then move it into the region inference context

nikomatsakis (Jun 27 2018 at 18:24, on Zulip):

along with the hashset

Eh2406 (Jun 27 2018 at 18:24, on Zulip):

that all makes sense. as a gole.

nikomatsakis (Jun 27 2018 at 18:24, on Zulip):

yep, doesn't have to be step 1

Eh2406 (Jun 27 2018 at 18:25, on Zulip):

so I'd say I am at step 0.7. witch is preity good for the time i've put in.

nikomatsakis (Jun 27 2018 at 18:26, on Zulip):

it may already show some measurable effect...

nikomatsakis (Jun 27 2018 at 18:27, on Zulip):

but it seems like if we're micro-optimziing, it'd be better to avoid adding the duplicates from the beginning

nikomatsakis (Jun 27 2018 at 18:27, on Zulip):

versus adding them and then filtering them ou

Eh2406 (Jun 27 2018 at 18:29, on Zulip):

I think the next step is to remove the allocation by using retain

nikomatsakis (Jun 27 2018 at 18:29, on Zulip):

ah, that's a decent compromise

nikomatsakis (Jun 27 2018 at 18:29, on Zulip):

forgot about retain

Eh2406 (Jun 27 2018 at 18:52, on Zulip):

used retain and it is pretty clean.

Eh2406 (Jun 27 2018 at 18:53, on Zulip):

next to look into were new is called as you suggested in the issue.

nikomatsakis (Jun 27 2018 at 18:57, on Zulip):

nice

Eh2406 (Jun 27 2018 at 19:10, on Zulip):

looks like there is a long chain but it comes from MirTypeckRegionConstraints

nikomatsakis (Jun 27 2018 at 19:12, on Zulip):

yes that sounds right

Eh2406 (Jun 27 2018 at 19:31, on Zulip):

Where do you want the new type? What do you want it to be called?

nikomatsakis (Jun 27 2018 at 19:35, on Zulip):

I think it belongs in a new module; I'd probably call it rustc_mir::borrow_check::nll::region_infer::constraint_set::ConstraintSet (with that module being crate visible)

nikomatsakis (Jun 27 2018 at 19:35, on Zulip):

but it could also be nll::constraint_set::ConstraintSet

nikomatsakis (Jun 27 2018 at 19:35, on Zulip):

I've been debating about what should belong "under" region_infer...

nikomatsakis (Jun 27 2018 at 19:35, on Zulip):

either way, the Constraint struct should probably live with it

nikomatsakis (Jun 27 2018 at 19:36, on Zulip):

along with (I think) the logic for threading constraints into a linked list (eventually, anyway)

Eh2406 (Jun 27 2018 at 19:38, on Zulip):

So I was thinking change MirTypeckRegionConstraintsto hold the new type. and it is in type_checke

Eh2406 (Jun 27 2018 at 19:38, on Zulip):

so that suggests in nll.

Jake Goulding (Jun 27 2018 at 19:47, on Zulip):

...so many nested modules...

Eh2406 (Jun 27 2018 at 20:50, on Zulip):

pr incoming

Eh2406 (Jun 27 2018 at 20:53, on Zulip):

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

nikomatsakis (Jun 27 2018 at 21:14, on Zulip):

@Eh2406 I left some notes on the PR

Eh2406 (Jun 27 2018 at 21:21, on Zulip):

@nikomatsakis I assume by Constraint you mean OutlivesConstraintor are you asking me to rename it?

Eh2406 (Jun 27 2018 at 21:24, on Zulip):

I think you want me to bring build_dependency_map into the new type as link so as to get rid of inner_mut?

Eh2406 (Jun 27 2018 at 21:25, on Zulip):

and I don't know what you want me to bring in for each_affected_by_dirty

nikomatsakis (Jun 27 2018 at 21:26, on Zulip):

@nikomatsakis I assume by Constraint you mean OutlivesConstraintor are you asking me to rename it?

yes I mean that, I am not saying we should rename it

nikomatsakis (Jun 27 2018 at 21:26, on Zulip):

I think you want me to bring build_dependency_map into the new type as link so as to get rid of inner_mut?

yes

nikomatsakis (Jun 27 2018 at 21:26, on Zulip):

and I don't know what you want me to bring in for each_affected_by_dirty

I basically don't want to have direct access to the vector

nikomatsakis (Jun 27 2018 at 21:26, on Zulip):

so I was proposing that we extract the loop that uses it into a method

nikomatsakis (Jun 27 2018 at 21:26, on Zulip):

one second...

nikomatsakis (Jun 27 2018 at 21:27, on Zulip):

@Eh2406 this is the loop I would exract into that method

nikomatsakis (Jun 27 2018 at 21:28, on Zulip):

it would be replaced with something like:

constraint_set.each_affected_by_dirty(constraint.sup, |dep_idx| {
  dirty_list.push(dep_idx);
});
nikomatsakis (Jun 27 2018 at 21:28, on Zulip):

I guess we would still want to permit indexing by ConstraintIndex

Eh2406 (Jun 27 2018 at 21:34, on Zulip):

I don't groc that code at this time. Nor will I be able to do it in the time I have left today.
So let me see if I can get link done tonight. build_dependency_map starts with let mut map = IndexVec::from_elem(None, &self.definitions);
So should the link take a starting map as an argument?

nikomatsakis (Jun 27 2018 at 21:36, on Zulip):

link would be a good start :)

nikomatsakis (Jun 27 2018 at 21:36, on Zulip):

it should probably return the map

nikomatsakis (Jun 27 2018 at 21:36, on Zulip):

oh, it needs to know the number of items I guess?

nikomatsakis (Jun 27 2018 at 21:37, on Zulip):

just pass in self.definitions.len() and invoke IndexVec::from_elem_n(None, len)

Eh2406 (Jun 27 2018 at 21:38, on Zulip):

lol is that all its doing.

nikomatsakis (Jun 27 2018 at 21:40, on Zulip):

yeah

Eh2406 (Jun 27 2018 at 21:54, on Zulip):

links is up

nikomatsakis (Jun 27 2018 at 22:02, on Zulip):

@Eh2406 I'll take a look -- do you think you'll have more time for the rest later? (I wasn't clear on whether you happened to have time today, or you would have time e.g. tomorrow etc)

nikomatsakis (Jun 27 2018 at 22:03, on Zulip):

I could plausibly pull out some of that code the way I had in mind, seems like it wouldn't take that long, but if you think you'll have time, better for you to do it so you can get more familiar with things :)

Eh2406 (Jun 27 2018 at 22:03, on Zulip):

I'm not sure either, but I am going to give it a little longer tonight.

Eh2406 (Jun 27 2018 at 22:04, on Zulip):

ok looking at each_affected_by_dirty the code you linked refers to 2 other variables.
- clean_bit_vec which is not straightforward to bring in do to https://github.com/rust-lang/rust/blob/4aff10bb1b9b202bb6464f99d198d3e6f49e6991/src/librustc_mir/borrow_check/nll/region_infer/mod.rs#L495
- dependency_map witch is https://github.com/rust-lang/rust/blob/4aff10bb1b9b202bb6464f99d198d3e6f49e6991/src/librustc_mir/borrow_check/nll/region_infer/mod.rs#L485

dependency_map can be removed by taking Option<ConstraintIndex> as an arg instead of RegionVid
don't know about the other.

Eh2406 (Jun 27 2018 at 22:07, on Zulip):

clean_bit_vec can be added as part of the call back.

nikomatsakis (Jun 27 2018 at 22:09, on Zulip):

the dependency_map would I guess have to be given back, after having been returned by link

nikomatsakis (Jun 27 2018 at 22:09, on Zulip):

it could also be stored in the ConstraintSet structure itself I suppose

Eh2406 (Jun 27 2018 at 22:11, on Zulip):

I have something for you do look at

Eh2406 (Jun 27 2018 at 22:11, on Zulip):

one sec for the push to go thure

Eh2406 (Jun 27 2018 at 22:12, on Zulip):

also can I remove new, it is giving ded code workings?

nikomatsakis (Jun 27 2018 at 22:12, on Zulip):

yep

Eh2406 (Jun 27 2018 at 22:16, on Zulip):

pushed, getting an odd error

error[E0596]: cannot borrow immutable argument `op` as mutable
  --> librustc_mir\borrow_check\nll\constraint_set.rs:63:13
   |
60 |         op: impl FnMut(ConstraintIndex),
   |         -- consider changing this to `mut op`
...
63 |             op(dep_idx);
   |             ^^ cannot borrow mutably

error: aborting due to previous error
Eh2406 (Jun 27 2018 at 22:22, on Zulip):

What borrow!

Eh2406 (Jun 27 2018 at 22:25, on Zulip):

mut op made the errore go away.

Eh2406 (Jun 27 2018 at 22:25, on Zulip):

I think this is close to what you wanted.

nikomatsakis (Jun 27 2018 at 22:28, on Zulip):

What borrow!

the call is a borrow

Eh2406 (Jun 27 2018 at 22:29, on Zulip):

that hiccup aside, I think that is a each_affected_by_dirty for you.

nikomatsakis (Jun 27 2018 at 22:37, on Zulip):

@Eh2406 looks great! I left some nits, mostly requests for comment and one minor cleanup.

nikomatsakis (Jun 27 2018 at 22:37, on Zulip):

but yes I'd say that's more or less done

Eh2406 (Jun 27 2018 at 22:41, on Zulip):

ok I am working on all the iters then I will do the Index

nikomatsakis (Jun 27 2018 at 22:44, on Zulip):

(I also pointed out we could use a Deref impl instead)

Eh2406 (Jun 27 2018 at 22:45, on Zulip):

Deref but not DerefMut that sounds good.

nikomatsakis (Jun 27 2018 at 22:46, on Zulip):

right

Eh2406 (Jun 27 2018 at 22:51, on Zulip):

done and pushed

nikomatsakis (Jun 27 2018 at 22:52, on Zulip):

looks great

nikomatsakis (Jun 27 2018 at 22:52, on Zulip):

are you able to add the comments?

Eh2406 (Jun 27 2018 at 22:53, on Zulip):

for got I will do it

Eh2406 (Jun 27 2018 at 22:58, on Zulip):

added

nikomatsakis (Jun 27 2018 at 22:59, on Zulip):

very nice =)

Eh2406 (Jun 27 2018 at 22:59, on Zulip):

This has been a lot of work of ~ 30% of ~8% = ~2% improvement.

nikomatsakis (Jun 27 2018 at 23:00, on Zulip):

code is nicer anyhow :)

Eh2406 (Jun 27 2018 at 23:01, on Zulip):

and in the long run 2 man-days is not a lot.

Eh2406 (Jun 28 2018 at 16:03, on Zulip):

rebase is done ~1h ago, waiting on travis and and r+

nikomatsakis (Jun 28 2018 at 16:07, on Zulip):

@Eh2406 remind me the URL?

Eh2406 (Jun 28 2018 at 16:07, on Zulip):

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

Eh2406 (Jun 28 2018 at 16:48, on Zulip):

I was thinking, always dangerous, from the way you described things the field pub point: Location, is not important any more. Would it be a good cleanup to just remove it as a separate PR?

nikomatsakis (Jun 28 2018 at 16:53, on Zulip):

I believe we use it during error reporting

nikomatsakis (Jun 28 2018 at 16:55, on Zulip):

so I'd say leave it

Eh2406 (Jun 28 2018 at 17:03, on Zulip):

I would have thought we used pub span: Span, for error reporting?

nikomatsakis (Jun 28 2018 at 17:03, on Zulip):

we use both

nikomatsakis (Jun 28 2018 at 17:03, on Zulip):

I'm actually not sure if we us the span :)

nikomatsakis (Jun 28 2018 at 17:04, on Zulip):

knowing the point lets us describe why

nikomatsakis (Jun 28 2018 at 17:04, on Zulip):

more intelligently than just where

nikomatsakis (Jun 28 2018 at 17:04, on Zulip):

i.e., we can inspect the MIR

Eh2406 (Jun 28 2018 at 17:04, on Zulip):

ok

Last update: Nov 21 2019 at 13:10UTC