Stream: t-compiler/wg-mir-opt

Topic: Place's projection interning design meeting ?


Santiago Pastorino (Sep 24 2019 at 14:11, on Zulip):

@nikomatsakis @oli we've talked about doing a design meeting to discuss about what needs to be done to improve on Place's projection allocation strategy

Santiago Pastorino (Sep 24 2019 at 14:12, on Zulip):

opening this thread to start discussing a bit about when a meeting like this could happen

Santiago Pastorino (Sep 24 2019 at 14:12, on Zulip):

this would be my big next step to make progress with Place 2.0

Santiago Pastorino (Sep 24 2019 at 14:13, on Zulip):

the rest of the things around are really minor things, like the build place iteratively task

nikomatsakis (Sep 24 2019 at 14:25, on Zulip):

yep -- should we try to schedule a time? I could carve out some time tomorrow morning, or maybe tomorrow afternoon, say around 2pm Eastern

nikomatsakis (Sep 24 2019 at 14:26, on Zulip):

not sure how long we'll need for such discussion -- I would guess ~30 min ?

Santiago Pastorino (Sep 24 2019 at 14:31, on Zulip):

/cc @oli

oli (Sep 24 2019 at 14:48, on Zulip):

works for me

oli (Sep 25 2019 at 18:00, on Zulip):

hi @nikomatsakis @Santiago Pastorino

oli (Sep 25 2019 at 18:03, on Zulip):

So as far as I can tell we have three things to continue working on right now:

  1. place building shouldn't Vec -> Box -> Vec cycle all the time
  2. intern places to deduplicate them between all MIR bodies
  3. make Deref not be a place projection
oli (Sep 25 2019 at 18:03, on Zulip):

I'd wager that the numbers also correspond to the difficulty of the task

Santiago Pastorino (Sep 25 2019 at 18:16, on Zulip):

@nikomatsakis @oli I think we never set on a date/time for this meeting, should we look for some specific time?

Wesley Wiser (Sep 25 2019 at 18:19, on Zulip):

I thought it was supposed be today at 2 (Eastern) :shrug:

oli (Sep 25 2019 at 19:00, on Zulip):

ok, this time at the correct time: Hi @nikomatsakis @Santiago Pastorino

Santiago Pastorino (Sep 25 2019 at 19:02, on Zulip):

hehe, Oli, the "right" time was an hour ago :), but still I've talked to Niko and he told me that he booked this time twice

Santiago Pastorino (Sep 25 2019 at 19:02, on Zulip):

so he won't be able to attend

Santiago Pastorino (Sep 25 2019 at 19:02, on Zulip):

going to start a doodle

Santiago Pastorino (Sep 25 2019 at 19:02, on Zulip):

is it possible for you tomorrow or friday?

Santiago Pastorino (Sep 25 2019 at 19:02, on Zulip):

@nikomatsakis tomorrow or friday is ok?

oli (Sep 25 2019 at 19:03, on Zulip):

XD

Santiago Pastorino (Sep 25 2019 at 19:03, on Zulip):

want to reduce the amount of days used in a doodle :)

oli (Sep 25 2019 at 19:03, on Zulip):

I'm very confused

Santiago Pastorino (Sep 25 2019 at 19:03, on Zulip):

hehe don't worry because Niko wasn't around anyway

Santiago Pastorino (Sep 25 2019 at 19:03, on Zulip):

to me ... the more I read the conversation the more convinced I am that we didn't set a date, Niko asked for two possibilities and we said yes

Santiago Pastorino (Sep 25 2019 at 19:03, on Zulip):

:P

oli (Sep 25 2019 at 19:03, on Zulip):

neither tomorrow nor friday work for me after 11am eastern time

Santiago Pastorino (Sep 25 2019 at 19:04, on Zulip):

but before yes?

oli (Sep 25 2019 at 19:04, on Zulip):

jup

Santiago Pastorino (Sep 25 2019 at 19:05, on Zulip):

@nikomatsakis does it work for you tomorrow or friday before 11am eastern time?

oli (Sep 25 2019 at 19:06, on Zulip):

before the compiler triage or steering meetings

oli (Sep 25 2019 at 19:06, on Zulip):

anything works for me

oli (Sep 25 2019 at 19:07, on Zulip):

I'm gonna go to bed, pick any time before the compiler meetings and I can attend

Santiago Pastorino (Sep 25 2019 at 19:08, on Zulip):

to me seems like it would be better on friday

Santiago Pastorino (Sep 25 2019 at 19:08, on Zulip):

let's see what @nikomatsakis says

Santiago Pastorino (Sep 26 2019 at 11:02, on Zulip):

I've added the event to the rustc calendar

Santiago Pastorino (Sep 27 2019 at 12:35, on Zulip):

@WG-mir-opt friendly reminder, this meeting is happening in 25 mins

Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):

@WG-mir-opt hi everyone! :wave:

Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):

so, to remind mainly the people that's reading and wasn't following close, we changed Place representation from a tree like structure to the following structure ...

Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):
pub struct Place<'tcx> {
    pub base: PlaceBase<'tcx>,

    /// projection out of a place (access a field, deref a pointer, etc)
    pub projection: Box<[PlaceElem<'tcx>]>,
}
Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):

this meeting was mainly to discuss how to go from ...

Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):
    pub projection: Box<[PlaceElem<'tcx>]>,
Santiago Pastorino (Sep 27 2019 at 13:00, on Zulip):

to

Santiago Pastorino (Sep 27 2019 at 13:01, on Zulip):
    pub projection: &[PlaceElem<'tcx>],
Santiago Pastorino (Sep 27 2019 at 13:01, on Zulip):

or well, really the interned version of that

Santiago Pastorino (Sep 27 2019 at 13:02, on Zulip):

@oli, @nikomatsakis do you have some first thoughts about this ... :)

nikomatsakis (Sep 27 2019 at 13:02, on Zulip):

hi

eddyb (Sep 27 2019 at 13:02, on Zulip):

should we remove field types from projections?

nikomatsakis (Sep 27 2019 at 13:02, on Zulip):

sorry, reading now!

oli (Sep 27 2019 at 13:02, on Zulip):

Well, one other option was to intern Places directly so we'd have &'tcx Place<'tcx> everywhere

eddyb (Sep 27 2019 at 13:02, on Zulip):

I feel like that could make interning far more effective

Santiago Pastorino (Sep 27 2019 at 13:02, on Zulip):

I feel like that could make interning far more effective

you meant, interning the whole Place structure?

nikomatsakis (Sep 27 2019 at 13:03, on Zulip):

I think that's orthogonal, @eddyb

oli (Sep 27 2019 at 13:03, on Zulip):

yes

eddyb (Sep 27 2019 at 13:03, on Zulip):

@oli yeah but that only makes sense for non-finite structure

Santiago Pastorino (Sep 27 2019 at 13:03, on Zulip):

should we remove field types from projections?

isn't it a separate issue? say more about it :)

nikomatsakis (Sep 27 2019 at 13:03, on Zulip):

I thnk it's a decent idea, but the challenge is around normalization

eddyb (Sep 27 2019 at 13:03, on Zulip):

anything finite is usually much cheaper to just drag around

nikomatsakis (Sep 27 2019 at 13:03, on Zulip):

I'd rather leave the field types to be discussed separately

nikomatsakis (Sep 27 2019 at 13:03, on Zulip):

Can you explain what you mean by finite?

eddyb (Sep 27 2019 at 13:04, on Zulip):

PlaceBase is a "leaf" (I guess in Rust the word "finite" is kind of hard to use correctly)

Santiago Pastorino (Sep 27 2019 at 13:04, on Zulip):

I'd rather leave the field types to be discussed separately

I can dive in and do all the stuff needed, but yeah, something in my mind prefers to divide problems in the maximum possible way :), so :+1: to what @nikomatsakis is saying, unless there are reasons to do everything in one step

nikomatsakis (Sep 27 2019 at 13:05, on Zulip):

It seems to me that interning has two challenges:

- construction (I prefer the "builder" approach we discussed earlier, not sure if you've all thought about that more)
- the mut visitor, which cannot descend to non-owned content (I think some of the NLL visitors rely on being able to e.g. mutate the types)

eddyb (Sep 27 2019 at 13:05, on Zulip):

interning PlaceBase on top of projections means you'll have less reuse while there is only an ergonomic (if at all) benefit to having the whole Place being interned, since its size is really small

Santiago Pastorino (Sep 27 2019 at 13:05, on Zulip):

It seems to me that interning has two challenges:

for more info on the construction thing Niko is mentioning https://rust-lang.zulipchat.com/#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/non.20recursive.20Place.20construction

nikomatsakis (Sep 27 2019 at 13:05, on Zulip):

you're saying then that it's better to just intern the projection slice, @eddyb ?

nikomatsakis (Sep 27 2019 at 13:05, on Zulip):

vs the entire place?

nikomatsakis (Sep 27 2019 at 13:06, on Zulip):

I don't have a strong opinion about that

eddyb (Sep 27 2019 at 13:06, on Zulip):

yes, and this should be true for anything that's (leaf, [leaf]) or (leaf, recursive<leaf>)

nikomatsakis (Sep 27 2019 at 13:06, on Zulip):

but I think I agree

eddyb (Sep 27 2019 at 13:06, on Zulip):

(this is why I used the word finite at first)

nikomatsakis (Sep 27 2019 at 13:06, on Zulip):

if nothing else, I'd rather not intern a data structure with a vec inside

eddyb (Sep 27 2019 at 13:07, on Zulip):

there's also I guess the question of [Projection] vs ty::List<Projection>, the latter disallowing slicing but having reference equality instead of value equality

nikomatsakis (Sep 27 2019 at 13:07, on Zulip):

It seems to me that interning has two challenges:

does this seem about right to folks? are there other complications to consider?

nikomatsakis (Sep 27 2019 at 13:08, on Zulip):

there's also I guess the question of [Projection] vs ty::List<Projection>, the latter disallowing slicing but having reference equality instead of value equality

yeah, that's a good one -- I like allowing slices, but it's also achievable with PlaceRef, which I think @Santiago Pastorino added already?

Santiago Pastorino (Sep 27 2019 at 13:08, on Zulip):

yes

eddyb (Sep 27 2019 at 13:08, on Zulip):

or rather, you can create a &[T] from a &List<T> (and we do this with Substs in a few places, for example), but not a &List<T> from a &List<T>

Santiago Pastorino (Sep 27 2019 at 13:08, on Zulip):

we can go with List and be able to do that with PlaceRef

eddyb (Sep 27 2019 at 13:08, on Zulip):

yeah PlaceRef is a really nice solution for this

eddyb (Sep 27 2019 at 13:09, on Zulip):

(arguably Place itself could be generic enough to support this by itself but that's a bit silly at this point :P)

Santiago Pastorino (Sep 27 2019 at 13:09, on Zulip):

or rather, you can create a &[T] from a &List<T> (and we do this with Substs in a few places, for example), but not a &List<T> from a &List<T>

definitely, that can be done in Place::as_place_ref, as part of the whole conversion

nikomatsakis (Sep 27 2019 at 13:09, on Zulip):

yeah I mean placeref is fine too

oli (Sep 27 2019 at 13:09, on Zulip):

(arguably Place itself could be generic enough to support this by itself but that's a bit silly at this point :P)

we explicitly opted against that

nikomatsakis (Sep 27 2019 at 13:09, on Zulip):

is List 1-word?

eddyb (Sep 27 2019 at 13:09, on Zulip):

yupp

eddyb (Sep 27 2019 at 13:09, on Zulip):

oh right that's the other win here

nikomatsakis (Sep 27 2019 at 13:09, on Zulip):

ok that seems worthwhile

Santiago Pastorino (Sep 27 2019 at 13:10, on Zulip):

ohh wasn't aware of that

eddyb (Sep 27 2019 at 13:10, on Zulip):

yeah it's a whole hack involving extern { type ...; } and stuff

nikomatsakis (Sep 27 2019 at 13:10, on Zulip):

what is the size of the entire Place going to be, then?

nikomatsakis (Sep 27 2019 at 13:10, on Zulip):

I guess sizeof(Base) + 1

Santiago Pastorino (Sep 27 2019 at 13:10, on Zulip):

let me check that out quickly

nikomatsakis (Sep 27 2019 at 13:10, on Zulip):

well, + sizeof(usize) :)

eddyb (Sep 27 2019 at 13:10, on Zulip):

either 2 or 3 usize's but probably 3 given that idk how you'd fit the static case otherwise :(

nikomatsakis (Sep 27 2019 at 13:10, on Zulip):

plausibly we could intern base separately :)

eddyb (Sep 27 2019 at 13:11, on Zulip):

we can make this really nice if we get rid of static places though

eddyb (Sep 27 2019 at 13:11, on Zulip):

you can't move out of a static so they feel extremely pointless

nikomatsakis (Sep 27 2019 at 13:11, on Zulip):

hmm yes, seems like a "separate" thing to consider, but true

Wesley Wiser (Sep 27 2019 at 13:11, on Zulip):

So @oli and I had that thought that if we interned Place, then anywhere that currently has a Place field would shrink to sizeof(usize).

eddyb (Sep 27 2019 at 13:11, on Zulip):

(STATIC would then be *&STATIC for anyone not following)

Santiago Pastorino (Sep 27 2019 at 13:11, on Zulip):

what is the size of the entire Place going to be, then?

I remember doing this silly thing to emulate quickly the sizes of these things https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8ea6a738e3065c34837d9fde64f9091d

eddyb (Sep 27 2019 at 13:12, on Zulip):

@Wesley Wiser yes but you'd also have way more separate things in the interner that share projections but not base

Santiago Pastorino (Sep 27 2019 at 13:12, on Zulip):

size of Place as is today is 32 bytes

nikomatsakis (Sep 27 2019 at 13:12, on Zulip):

(STATIC would then be *&STATIC for anyone not following)

(I'd want to look into what this means for borrow checker, but I think it could be fine)

nikomatsakis (Sep 27 2019 at 13:12, on Zulip):

(but yeah separate)

Wesley Wiser (Sep 27 2019 at 13:13, on Zulip):

I think the idea was to do an intern cache at the mir::Body level

nikomatsakis (Sep 27 2019 at 13:13, on Zulip):

so there are three options, which are kind of non-exclusive:

Santiago Pastorino (Sep 27 2019 at 13:13, on Zulip):

what is the size of the entire Place going to be, then?

I remember doing this silly thing to emulate quickly the sizes of these things https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8ea6a738e3065c34837d9fde64f9091d

was looking mainly for the size of Statements at that time

Wesley Wiser (Sep 27 2019 at 13:13, on Zulip):

And we could also do a scheme to not store common Places

nikomatsakis (Sep 27 2019 at 13:13, on Zulip):

my opinion: interning base and interning place is something to consider later

nikomatsakis (Sep 27 2019 at 13:13, on Zulip):

the hard part is interning projections

nikomatsakis (Sep 27 2019 at 13:13, on Zulip):

and I think that's worth doing separately

Santiago Pastorino (Sep 27 2019 at 13:13, on Zulip):

what is the size of the entire Place going to be, then?

I remember doing this silly thing to emulate quickly the sizes of these things https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8ea6a738e3065c34837d9fde64f9091d

was looking mainly for the size of Statements at that time

still Place due to padding is not going to change because of the use of Box instead of List

oli (Sep 27 2019 at 13:14, on Zulip):

I think the idea was to do an intern cache at the mir::Body level

Ah yes, that was the idea with using 32 bit indices

Wesley Wiser (Sep 27 2019 at 13:14, on Zulip):

Ah right

nikomatsakis (Sep 27 2019 at 13:14, on Zulip):

hm although I do find the idea of indices and per-mir interning interesting

nikomatsakis (Sep 27 2019 at 13:14, on Zulip):

(somewhat orthogonal, but relevant)

eddyb (Sep 27 2019 at 13:14, on Zulip):

a Local is 32-bit :P

oli (Sep 27 2019 at 13:14, on Zulip):

like the first 128 indices could literally just be transmuted to Local

oli (Sep 27 2019 at 13:14, on Zulip):

and the others need lookup

eddyb (Sep 27 2019 at 13:15, on Zulip):

you won't ever merge that because it will regress old inflate,,,

nikomatsakis (Sep 27 2019 at 13:15, on Zulip):

I guess we could try to gather some estimates, no?

nikomatsakis (Sep 27 2019 at 13:15, on Zulip):

i.e., we could look at MIR and see how much re-use we'd get

eddyb (Sep 27 2019 at 13:15, on Zulip):

(unless we finally removed it from perf, lol)

nikomatsakis (Sep 27 2019 at 13:15, on Zulip):

(if we interned projections separately in a regular ol' arena)

nikomatsakis (Sep 27 2019 at 13:15, on Zulip):

you won't ever merge that because it will regress old inflate,,,

huh?

oli (Sep 27 2019 at 13:16, on Zulip):

so... collect all Places during mir optimizations and count their occurrences?

oli (Sep 27 2019 at 13:16, on Zulip):

then optimize for the most occurring ones?

eddyb (Sep 27 2019 at 13:16, on Zulip):

older inflate versions have a macro-generated huge function because it actually used to be better than the dynamic version but isn't even nowadays, and perf used to test the older version for a long while

nikomatsakis (Sep 27 2019 at 13:16, on Zulip):

I'm creating a hackmd to store our notes here

eddyb (Sep 27 2019 at 13:16, on Zulip):

@nikomatsakis basically it's our most powerful stress test :P

nikomatsakis (Sep 27 2019 at 13:16, on Zulip):

fyi :)

nikomatsakis (Sep 27 2019 at 13:16, on Zulip):

I'm going to try and jot down a few things

Wesley Wiser (Sep 27 2019 at 13:17, on Zulip):

perf used to test the older version for a long while

So perf.rlo won't actually show the issue?

nikomatsakis (Sep 27 2019 at 13:17, on Zulip):

nikomatsakis basically it's our most powerful stress test :P

sure but why would it specifically be bad for one of the proposals at hand?

eddyb (Sep 27 2019 at 13:18, on Zulip):

because one of the ways it's horrible in is it has maybe thousands of MIR locals

eddyb (Sep 27 2019 at 13:19, on Zulip):

its MIR locals multiplied by the number of statements resulted in a really terrible worst-case for my WIP NRVO PR last year

oli (Sep 27 2019 at 13:19, on Zulip):

if we regress memory on horrible crates and improve it on a lot of others, that's fine with me

eddyb (Sep 27 2019 at 13:19, on Zulip):

so it stuck with me

Santiago Pastorino (Sep 27 2019 at 13:19, on Zulip):

hehe :)

eddyb (Sep 27 2019 at 13:19, on Zulip):

anyway point was 128 might be a bit low, 2^16 is closer to what I've seen used in practice for SSA values

Wesley Wiser (Sep 27 2019 at 13:20, on Zulip):

I'm going to make some coffee because I'm not seeing why it would regress memory :)

oli (Sep 27 2019 at 13:20, on Zulip):

anyway point was 128 might be a bit low, 2^16 is closer to what I've seen used in practice for SSA values

that was just a random number I picked. Collecting data would be the best thing to find that number

eddyb (Sep 27 2019 at 13:21, on Zulip):

there's also that whole "alias" idea I had, but that's only semi-related. it is very close to interning places per-body, depending on the semantics you pick

Wesley Wiser (Sep 27 2019 at 13:21, on Zulip):

I feel like we could also extend that scheme so that n + 0 => Place(Local(n), []), n + 1 => Place(Local(n) [Field(0)]) up to some other number.

oli (Sep 27 2019 at 13:21, on Zulip):

I'm going to make some coffee because I'm not seeing why it would regress memory :slight_smile:

if every index is only used once, then we use more memory for the index + vector scheme than for the direct scheme I think

Wesley Wiser (Sep 27 2019 at 13:21, on Zulip):

But aren't we storing place's by value now?

Wesley Wiser (Sep 27 2019 at 13:21, on Zulip):

So de duplicating the values should save some memory right?

eddyb (Sep 27 2019 at 13:21, on Zulip):

oh god please don't do arithmetic coding in a compiler

eddyb (Sep 27 2019 at 13:22, on Zulip):

that stuff is fun but not cheap on compute

nikomatsakis (Sep 27 2019 at 13:22, on Zulip):

I don't know what "arithmetic coding" is but

nikomatsakis (Sep 27 2019 at 13:22, on Zulip):

I am still trying to sort out the variations

oli (Sep 27 2019 at 13:22, on Zulip):

well, if deduplication doesn't actually deduplicate because every value is only used once, then we don't gain anything but may lose something

nikomatsakis (Sep 27 2019 at 13:22, on Zulip):

it seems to me that

pnkfelix (Sep 27 2019 at 13:22, on Zulip):

what is the size of the entire Place going to be, then?

I remember doing this silly thing to emulate quickly the sizes of these things https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8ea6a738e3065c34837d9fde64f9091d

Isn't this what -Z print-type-sizes is for?

nikomatsakis (Sep 27 2019 at 13:22, on Zulip):

if you (a) intern the projections to a list

eddyb (Sep 27 2019 at 13:23, on Zulip):

(arithmetic coding is a trick used in compression, more often audio than general data compression, and it's also related to those tricks for fitting (Nat, Nat) into Nat, aka diagonalization or w/e)

Wesley Wiser (Sep 27 2019 at 13:23, on Zulip):

I guess I assumed most locals were used at least twice (a read and write)

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

ah, almost but not quite, dang it. I was going to say that Place coudl be copy, but the problem is I think we still have a Box for statics maybe?

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

anyway my point was this

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

if you reserve the first N places for locals

eddyb (Sep 27 2019 at 13:23, on Zulip):

you can solve statics anyway so don't worry about them too much

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

you don't need to put them in the vector at all

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

you can synthesize on demand

nikomatsakis (Sep 27 2019 at 13:23, on Zulip):

fn place(index: u32) -> Place

nikomatsakis (Sep 27 2019 at 13:24, on Zulip):

so in that case it really isn't any less efficient, no?

eddyb (Sep 27 2019 at 13:24, on Zulip):

(so the Nat thing is that you can fit tuples or lists of numbers into numbers, but it can get really expensive to decode, depending on how you're doing it)

nikomatsakis (Sep 27 2019 at 13:24, on Zulip):

(also it means we can set the threshold pretty high)

nikomatsakis (Sep 27 2019 at 13:24, on Zulip):

(the problem is statics, which would either have to be interned or solved in some other way)

nikomatsakis (Sep 27 2019 at 13:25, on Zulip):

but I think what all of this points to (in my mind) is that ultimately we probably want to intern the projections and the places

eddyb (Sep 27 2019 at 13:25, on Zulip):

oh so basically some of the place indices are locals and others are projections thereof

nikomatsakis (Sep 27 2019 at 13:25, on Zulip):

right, so if you have a threshold H, then fn place is kind of:

eddyb (Sep 27 2019 at 13:25, on Zulip):

and you can even define locals that way although it seems worrying. oh nvm what you're saying is what I thought everyone else was saying

nikomatsakis (Sep 27 2019 at 13:25, on Zulip):
fn place(index: u32) -> Place {
  if index < T { return Place { local: index }; }
  return self.place_vector[index - T];
}
Santiago Pastorino (Sep 27 2019 at 13:25, on Zulip):

what is the size of the entire Place going to be, then?

I remember doing this silly thing to emulate quickly the sizes of these things https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=8ea6a738e3065c34837d9fde64f9091d

Isn't this what -Z print-type-sizes is for?

I did this because I needed to see how much was the size of doing Box[T] instead of the previous thing we had to see if was worth the change, changing the thing gave my a lot of compile errors, didn't want to make the refactor before being sure :)

nikomatsakis (Sep 27 2019 at 13:26, on Zulip):

in that case, if all you have is a ton of locals, we haven't done any extra work, no?

nikomatsakis (Sep 27 2019 at 13:26, on Zulip):

or am I missing something

nikomatsakis (Sep 27 2019 at 13:26, on Zulip):

the vector would be empty, and the only change is the sizeof(Place) is much smaller

eddyb (Sep 27 2019 at 13:26, on Zulip):

okay yeah I would've assumed you don't store identity mappings anyway

nikomatsakis (Sep 27 2019 at 13:27, on Zulip):

so you were just assuming we'd set the threshold too low

eddyb (Sep 27 2019 at 13:27, on Zulip):

yeah my old inflate comment was about 128 specifically

nikomatsakis (Sep 27 2019 at 13:27, on Zulip):

ok ok

nikomatsakis (Sep 27 2019 at 13:27, on Zulip):

so this comes back (for me) to: the logical first step is to intern projections :)

nikomatsakis (Sep 27 2019 at 13:27, on Zulip):

which can then be used to intern the entire place at some later point

nikomatsakis (Sep 27 2019 at 13:28, on Zulip):

in the meantime, it's gotta be better than Box<[...]>

eddyb (Sep 27 2019 at 13:28, on Zulip):

I think we can all agree on interning projections?

eddyb (Sep 27 2019 at 13:28, on Zulip):

in fact I thought it was already happening

nikomatsakis (Sep 27 2019 at 13:28, on Zulip):

maybe I'm out of date :)

nikomatsakis (Sep 27 2019 at 13:28, on Zulip):

in that case, I think the next question would be what challenges exist to doing so, which comes back to the comment that I made a while back and how I would propose to address those challenges

nikomatsakis (Sep 27 2019 at 13:29, on Zulip):

but I'm going to stop typing for a sec because I want to see what @oli and @Santiago Pastorino think :)

Santiago Pastorino (Sep 27 2019 at 13:29, on Zulip):

in fact I thought it was already happening

projections are not being interned, see meeting title :joy:

eddyb (Sep 27 2019 at 13:30, on Zulip):

I mean that you were working towards it

Santiago Pastorino (Sep 27 2019 at 13:30, on Zulip):

yeah yeah, was kidding but yeah, I guessed we were already sold on it

Santiago Pastorino (Sep 27 2019 at 13:31, on Zulip):

so :+1:

Santiago Pastorino (Sep 27 2019 at 13:31, on Zulip):

but I'm going to stop typing for a sec because I want to see what oli and Santiago Pastorino think :)

so seems like there's a bunch of things that we all agree on?, I'd need to re-read the whole conversation to make some clear set of tasks

Santiago Pastorino (Sep 27 2019 at 13:32, on Zulip):

I guess this is what you were doing on HackMD @nikomatsakis ?

Santiago Pastorino (Sep 27 2019 at 13:32, on Zulip):

I mean, more or less taking some more clear things out :)

nikomatsakis (Sep 27 2019 at 13:32, on Zulip):

I guess one question is whether to intern projections to a List<> or some sort of per-mir index, but that seems like not the "high order bit" to me, it's to some extent the easiest part

nikomatsakis (Sep 27 2019 at 13:32, on Zulip):

that's what I was trying to do, yeah

nikomatsakis (Sep 27 2019 at 13:32, on Zulip):

I would definitely start with List<>

nikomatsakis (Sep 27 2019 at 13:33, on Zulip):

although... hmmm ...

Santiago Pastorino (Sep 27 2019 at 13:33, on Zulip):

yeah, to me is still not clear where to start

Santiago Pastorino (Sep 27 2019 at 13:33, on Zulip):

do I get rid of Static?

Santiago Pastorino (Sep 27 2019 at 13:33, on Zulip):

do I start interning projections?

nikomatsakis (Sep 27 2019 at 13:33, on Zulip):

I think that is clearly orthogonal

Santiago Pastorino (Sep 27 2019 at 13:33, on Zulip):

and things like that

nikomatsakis (Sep 27 2019 at 13:33, on Zulip):

getting rid of static

nikomatsakis (Sep 27 2019 at 13:34, on Zulip):

hold on, I'm rearranging a few things :)

Santiago Pastorino (Sep 27 2019 at 13:34, on Zulip):

so first thing to do would be to intern projections to List

nikomatsakis (Sep 27 2019 at 13:34, on Zulip):

take a look at the hackmd now

nikomatsakis (Sep 27 2019 at 13:34, on Zulip):

I'm curious if everyone agrees with the organization I put there

nikomatsakis (Sep 27 2019 at 13:36, on Zulip):

I have to do a bit of code browsing though, the main reason I was thinking that maybe per-mir indices are "interesting" is that the MIR would still own their expanded contents

nikomatsakis (Sep 27 2019 at 13:36, on Zulip):

and hence MutVisitor might plausibly be retained in roughly its current form

Santiago Pastorino (Sep 27 2019 at 13:36, on Zulip):

take a look at the hackmd now

seems good

Santiago Pastorino (Sep 27 2019 at 13:37, on Zulip):

one thing I'm not entirely sure now is about the contruction step you mentioned at the beginning

nikomatsakis (Sep 27 2019 at 13:37, on Zulip):

yeah we could dig a bit into that

Santiago Pastorino (Sep 27 2019 at 13:37, on Zulip):

I mean, does it have some weird implication that I may not clearly see?

nikomatsakis (Sep 27 2019 at 13:37, on Zulip):

not that I see

Santiago Pastorino (Sep 27 2019 at 13:37, on Zulip):

:+1:

nikomatsakis (Sep 27 2019 at 13:37, on Zulip):

so, for everyone's context, what I was talking about is that

nikomatsakis (Sep 27 2019 at 13:37, on Zulip):

when building MIR, we have functions like fn foo() -> Place

nikomatsakis (Sep 27 2019 at 13:37, on Zulip):

we build things recursively

nikomatsakis (Sep 27 2019 at 13:38, on Zulip):

so if you have a.b.c....z you would wind up interning .b, .b.c, .b.c.d etc

nikomatsakis (Sep 27 2019 at 13:38, on Zulip):

seems bad

nikomatsakis (Sep 27 2019 at 13:38, on Zulip):

but we could refactor to something like fn foo() -> PlaceBuilder that builds up a vector

nikomatsakis (Sep 27 2019 at 13:38, on Zulip):

and retain the "recursive" form

nikomatsakis (Sep 27 2019 at 13:38, on Zulip):

and then when we "convert" that to a Place, it would intern only once

Santiago Pastorino (Sep 27 2019 at 13:38, on Zulip):

yeah, that seems easy to do, was one of the things I had on my todo list

eddyb (Sep 27 2019 at 13:38, on Zulip):

oooh that's what you meant by builder. basically Place<Vec> :P

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

yes

Santiago Pastorino (Sep 27 2019 at 13:39, on Zulip):

lol, you really want that generic thing :)

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

That seems much nicer than trying to radically rewrite construction to an iterative form which (imo) will also be less natural

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

Though I could be persuaded otherwise

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

but even then

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

I'd still want to do the builder approach first

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

to try and separate concerns

Santiago Pastorino (Sep 27 2019 at 13:39, on Zulip):

lol, you really want that generic thing :)

which to be honest, seems good @eddyb

nikomatsakis (Sep 27 2019 at 13:39, on Zulip):

I'm vaguely negative on the generic thing :P

eddyb (Sep 27 2019 at 13:40, on Zulip):

(we don't have HKT anyway)

nikomatsakis (Sep 27 2019 at 13:40, on Zulip):

only because ... how much code re-use are we really enabling here

nikomatsakis (Sep 27 2019 at 13:40, on Zulip):

and it seems overall less obvious to people reading the codebase

Santiago Pastorino (Sep 27 2019 at 13:40, on Zulip):

That seems much nicer than trying to radically rewrite construction to an iterative form which (imo) will also be less natural

defitely, I have tried to do it and it's really less natural

nikomatsakis (Sep 27 2019 at 13:40, on Zulip):

this is a tuple of two fields people :P

eddyb (Sep 27 2019 at 13:40, on Zulip):

existing construction matches up a list of projections much better though, because Vec::push is at the end - iteration is the problem, because it's from the start to the end but our projection recursions were always from the end

Santiago Pastorino (Sep 27 2019 at 13:41, on Zulip):

and it seems overall less obvious to people reading the codebase

agree on this yeah, I was mentioning the benefits, not the drawbacks :P

nikomatsakis (Sep 27 2019 at 13:41, on Zulip):

sorry, construction matches what better (and better than what)?

eddyb (Sep 27 2019 at 13:41, on Zulip):

recursion -> iterating tends to work out while recursion -> iterator is a hard problem in general

nikomatsakis (Sep 27 2019 at 13:41, on Zulip):

(it seems like PlaceRef is the "counterpart" to PlaceBuilder, for those cases where consuming by recursion is more natural, but those are relatively few)

nikomatsakis (Sep 27 2019 at 13:42, on Zulip):

ok so I think you mean @eddyb that converting recursive code that consumed a place is relatively easy

nikomatsakis (Sep 27 2019 at 13:42, on Zulip):

But converting recursive code that builds a place, not so much

nikomatsakis (Sep 27 2019 at 13:42, on Zulip):

(did I understand correctly?)

eddyb (Sep 27 2019 at 13:42, on Zulip):

yeah, and it also feels pointless to turn things into iterators unless the data they're working on happens to be iterator-friendly in the first place

Santiago Pastorino (Sep 27 2019 at 13:43, on Zulip):

But converting recursive code that builds a place, not so much

it definitely seems like that, and more with projection being a slice :)

eddyb (Sep 27 2019 at 13:43, on Zulip):

as long as projections are always appended, the builder suggestion seems perfect and we don't need to bother with iterator contraptions

nikomatsakis (Sep 27 2019 at 13:44, on Zulip):

ok, so do we have consensus on this section on construction?

eddyb (Sep 27 2019 at 13:44, on Zulip):

(we can use SmallVec or something if really necessary etc.)

Santiago Pastorino (Sep 27 2019 at 13:44, on Zulip):

yeah, and it also feels pointless to turn things into iterators unless the data they're working on happens to be iterator-friendly in the first place

one of the cool things I ended adding is https://github.com/rust-lang/rust/blob/93387160ef71918d3a7ceb9f6bb2cf4b1897f589/src/librustc_mir/build/matches/mod.rs#L1300, unsure if people have different opinions

Santiago Pastorino (Sep 27 2019 at 13:44, on Zulip):

but in general you need the elem and the proj_base

nikomatsakis (Sep 27 2019 at 13:45, on Zulip):

that link didn't work for me

nikomatsakis (Sep 27 2019 at 13:45, on Zulip):

woah

Santiago Pastorino (Sep 27 2019 at 13:45, on Zulip):

sorry, took that from a current local branch

nikomatsakis (Sep 27 2019 at 13:45, on Zulip):

oh, that's the recursive stuff I was talking about

nikomatsakis (Sep 27 2019 at 13:45, on Zulip):

yeah, makes sense

nikomatsakis (Sep 27 2019 at 13:46, on Zulip):

I feel like it might be more obvious if we encapsulated that in a pattern but +1 overall

Santiago Pastorino (Sep 27 2019 at 13:46, on Zulip):

I feel like it might be more obvious if we encapsulated that in a pattern but +1 overall

say more about that, unsure I got it :)

eddyb (Sep 27 2019 at 13:47, on Zulip):

we used to do this a lot even with the recursive projections, because loops are nicer than writing recursive functions most of the time

Santiago Pastorino (Sep 27 2019 at 13:47, on Zulip):

the bad thing is having the mut cursor around, but with that pattern there seems a nice way to iterate

nikomatsakis (Sep 27 2019 at 13:47, on Zulip):

I was just saying that I'd imagine that code to be also expressable via something like:

let mut cursor = PlaceRef::from(...);
while let Some(elem) = cursor.pop_back() {
    ...
}
eddyb (Sep 27 2019 at 13:47, on Zulip):

you can just use a slice iterator, I think?

nikomatsakis (Sep 27 2019 at 13:48, on Zulip):

where pop_back returns &mut ProjectionElement and adjusts the cursor in place

nikomatsakis (Sep 27 2019 at 13:48, on Zulip):

(and yeah I think there are some slice methods that are similar)

eddyb (Sep 27 2019 at 13:48, on Zulip):

like, std::slice::Iter has a method to turn it back into a slice, I think

nikomatsakis (Sep 27 2019 at 13:49, on Zulip):

e.g., cursor.split_last_mut, analogous to slice:split_last_mut

nikomatsakis (Sep 27 2019 at 13:49, on Zulip):

yeah but I think we want methods on PlaceRef

nikomatsakis (Sep 27 2019 at 13:49, on Zulip):

that retain the placebase

nikomatsakis (Sep 27 2019 at 13:49, on Zulip):

I mean you can also do it on slices, but e.g. see this cod here, that rebuilds the PlaceRef

nikomatsakis (Sep 27 2019 at 13:49, on Zulip):

anyway, a bit afield

nikomatsakis (Sep 27 2019 at 13:50, on Zulip):

we've only got 10 minutes before design meeting

nikomatsakis (Sep 27 2019 at 13:50, on Zulip):

it seems like we settled a lot

Santiago Pastorino (Sep 27 2019 at 13:50, on Zulip):

I was going to say exactly that

Santiago Pastorino (Sep 27 2019 at 13:50, on Zulip):

yeah

Santiago Pastorino (Sep 27 2019 at 13:51, on Zulip):

so, I can start with things from https://hackmd.io/vHP5hbCKQkq-HW_tnuAsoA?view

nikomatsakis (Sep 27 2019 at 13:51, on Zulip):

I think one open question that remains is what to do about the MutVisitor, but I want to investigate if we could start (and maybe finish!) by moving to per-MIR indices, though that carries some 'portability' cost of its own, not sure if that's easier (in particular, you can't just deref the projections slice anymore, ooooh, right, and these tricks you're doing here wouldn't work)

nikomatsakis (Sep 27 2019 at 13:51, on Zulip):

never mind, I think we should do List<> first :)

Santiago Pastorino (Sep 27 2019 at 13:51, on Zulip):

yeah to both things :)

nikomatsakis (Sep 27 2019 at 13:52, on Zulip):

well, I guess you still could

nikomatsakis (Sep 27 2019 at 13:52, on Zulip):

do the slicing tricks

nikomatsakis (Sep 27 2019 at 13:52, on Zulip):

but it wouldl still mean that you need to do something like mir.projections(index) instead of just place.projections

Santiago Pastorino (Sep 27 2019 at 13:52, on Zulip):

do the slicing tricks

what do you mean?

nikomatsakis (Sep 27 2019 at 13:52, on Zulip):

what I mean is that mir.projections(index) can return a &[Projection] borrowed from the MIR, which can be sliced etc. But that might be a pain sometimes.

oli (Sep 27 2019 at 13:52, on Zulip):

having a.b.c not take up extra interning memory if a.b.c.d exists

nikomatsakis (Sep 27 2019 at 13:53, on Zulip):

no, I didn't actually mean that

oli (Sep 27 2019 at 13:53, on Zulip):

oh

nikomatsakis (Sep 27 2019 at 13:53, on Zulip):

although that's a thing too :)

nikomatsakis (Sep 27 2019 at 13:54, on Zulip):

what I mean is that if you have

struct Place { base: ..., projections: ProjectionIndex }
nikomatsakis (Sep 27 2019 at 13:54, on Zulip):

and you had that index into a list of projections on the MIR

nikomatsakis (Sep 27 2019 at 13:54, on Zulip):

that'd have some interesting characteristics but would also be a pain and overall I don't think it's the right first step (and maybe not ever right)

nikomatsakis (Sep 27 2019 at 13:55, on Zulip):

what you're saying @oli seems to be more about &[Projection] vs List<Projection>, confirm?

oli (Sep 27 2019 at 13:55, on Zulip):

yes

nikomatsakis (Sep 27 2019 at 13:55, on Zulip):

( I noted it in the hackmd, btw, it wasn't something we'd explicitly discussed before )

Wesley Wiser (Sep 27 2019 at 13:55, on Zulip):

:time: 5 minute warning

nikomatsakis (Sep 27 2019 at 13:55, on Zulip):

Yep, thanks <3

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

so the nice thing is

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

that I think the first steps for construction are something @Santiago Pastorino can pursue

Santiago Pastorino (Sep 27 2019 at 13:56, on Zulip):

:+1:

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

i.e., you can port over to a PlaceBuilder that builds a Vec

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

where the final step converts frm Vec to the Box<[...]> we have today

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

(in fact, I'm not sure what we're doing today? reallocating?)

Santiago Pastorino (Sep 27 2019 at 13:56, on Zulip):

(deleted)

nikomatsakis (Sep 27 2019 at 13:56, on Zulip):

and that gives time to work out the remaining questions...

Santiago Pastorino (Sep 27 2019 at 13:56, on Zulip):

that I think the first steps for construction are something Santiago Pastorino can pursue

yes and it's definitely a very easy thing to do

Santiago Pastorino (Sep 27 2019 at 13:57, on Zulip):

(in fact, I'm not sure what we're doing today? reallocating?)

yes, I think so

Santiago Pastorino (Sep 27 2019 at 13:58, on Zulip):

should be a nice win for such an easy change I think

nikomatsakis (Sep 27 2019 at 13:58, on Zulip):

yep

nikomatsakis (Sep 27 2019 at 13:59, on Zulip):

cool, gotta run, any final thoughts? take a look at the hackmd doc, maybe @Santiago Pastorino you want to add it to the compiler-team repo as minutes?

Santiago Pastorino (Sep 27 2019 at 13:59, on Zulip):

I can definitely do that

Santiago Pastorino (Sep 27 2019 at 13:59, on Zulip):

and don't have any other thoughts, so :wave: from my side :)

Santiago Pastorino (Oct 01 2019 at 17:43, on Zulip):

@eddyb @nikomatsakis you have mentioned in the meeting, a possible use of SmallVec for construction, if I got it right

Santiago Pastorino (Oct 01 2019 at 17:44, on Zulip):

with projection being a Box<PlaceElem<'tcx>> I think that using SmallVec is worser than just a Vec

Santiago Pastorino (Oct 01 2019 at 17:45, on Zulip):

because at the end, when you do into_place on the builder you need to convert to Box

Santiago Pastorino (Oct 01 2019 at 17:45, on Zulip):

on SmallVec in order to go to Box you need to go through Vec

Santiago Pastorino (Oct 01 2019 at 17:46, on Zulip):

still that doesn't matter, the thing is you'd need to reallocate on the heap no matter how big or small that SmallVec is

Santiago Pastorino (Oct 01 2019 at 17:47, on Zulip):

I guess you were talking about possible wins with the SmallVec approach once we go to the interned projection solution

Santiago Pastorino (Oct 01 2019 at 17:47, on Zulip):

right?

nikomatsakis (Oct 01 2019 at 19:28, on Zulip):

I'm confused

nikomatsakis (Oct 01 2019 at 19:28, on Zulip):

I think what we meant was that

nikomatsakis (Oct 01 2019 at 19:28, on Zulip):

the builder would contain a SmallVec<Projection>

nikomatsakis (Oct 01 2019 at 19:28, on Zulip):

maybe I need to check your PR to see what approach you used though

Santiago Pastorino (Oct 01 2019 at 19:29, on Zulip):

@nikomatsakis https://github.com/rust-lang/rust/pull/64922

Santiago Pastorino (Oct 01 2019 at 19:29, on Zulip):

it's very simple

Santiago Pastorino (Oct 01 2019 at 19:29, on Zulip):

I guessed that you wanted me to use SmallVec instead of Vec in the builder, but to me doesn't seem to make a lot of sense until we move to interning

Santiago Pastorino (Oct 01 2019 at 19:29, on Zulip):

unsure, I may have understood something wrong

Santiago Pastorino (Oct 01 2019 at 19:30, on Zulip):

basically there are two things related to that PR

Santiago Pastorino (Oct 01 2019 at 19:30, on Zulip):

one is that it's not giving a huge perf improvement

Santiago Pastorino (Oct 01 2019 at 19:30, on Zulip):

and the other is that one about SmallVec

nikomatsakis (Oct 01 2019 at 19:34, on Zulip):

I guessed that you wanted me to use SmallVec instead of Vec in the builder, but to me doesn't seem to make a lot of sense until we move to interning

oh, I see, because we're going to have to make a Box<[Elem]> eventually, you're saying

nikomatsakis (Oct 01 2019 at 19:35, on Zulip):

yeah that seems fine

Santiago Pastorino (Oct 01 2019 at 19:36, on Zulip):

seems fine means that I'm correct or that I need to do that and it will be fine

Santiago Pastorino (Oct 01 2019 at 19:36, on Zulip):

to me seems like I'd be converting back and forth with no wins

nikomatsakis (Oct 01 2019 at 19:36, on Zulip):

yeah, it's just a micro-optimization at best anyway

Santiago Pastorino (Oct 01 2019 at 19:37, on Zulip):

yeah but I guess that works once you want to go to things like &[T]

Santiago Pastorino (Oct 01 2019 at 19:38, on Zulip):

so when projection as SmallVec is small and it's there as an array you can just use a pointer to it, or even copy the array

Santiago Pastorino (Oct 01 2019 at 19:38, on Zulip):

but not if at the end you need to convert to Box

Santiago Pastorino (Oct 01 2019 at 19:38, on Zulip):

it's like you start with an array to avoid allocating on the heap but end allocating there anyway

Santiago Pastorino (Oct 01 2019 at 19:38, on Zulip):

so seems better to just go with Vec since the beginning

Wesley Wiser (Oct 01 2019 at 19:41, on Zulip):

I think SmallVec might help because, when you do the interning, you need to copy to the Arena. So by using SmallVec we potentially avoid allocating a Vec that just gets copied into the Arena and then discarded.

Wesley Wiser (Oct 01 2019 at 19:42, on Zulip):

But yeah, if we're not interning yet, then its probably not actually an optimization.

Santiago Pastorino (Oct 01 2019 at 19:42, on Zulip):

exactly, I was saying it doesn't seem to be useful meanwhile we are not interning

Santiago Pastorino (Oct 01 2019 at 19:42, on Zulip):

after interning is a different story :)

Last update: Nov 17 2019 at 08:25UTC