## 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):

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):

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 `MirTypeckRegionConstraints`to 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 `OutlivesConstraint`or 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 `OutlivesConstraint`or 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`

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):
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):

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`

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):

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

for got I will do it

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

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: Jul 02 2020 at 19:05UTC