Stream: t-compiler/wg-nll

Topic: issue-51818-share-buffer-on-simulate_block


Santiago Pastorino (Jun 29 2018 at 19:51, on Zulip):

@nikomatsakis back into this, so, without reading further I saw you said it's used just once, so why don't just make it &mut?

Santiago Pastorino (Jun 29 2018 at 19:51, on Zulip):

hehe, stupid thought :P

Santiago Pastorino (Jun 29 2018 at 19:53, on Zulip):

I mean, I was wondering why is it doing clone in the first place

nikomatsakis (Jun 29 2018 at 20:01, on Zulip):

well we need a temporary buffer basically

nikomatsakis (Jun 29 2018 at 20:01, on Zulip):

so as not to modify the original value

Santiago Pastorino (Jun 29 2018 at 20:39, on Zulip):

ok, will check this

Santiago Pastorino (Jun 29 2018 at 20:56, on Zulip):

@nikomatsakis I haven't jumped really into this task yet because this thing is still compiling your branch

Santiago Pastorino (Jun 29 2018 at 20:56, on Zulip):

but just finished reading the issue

Santiago Pastorino (Jun 29 2018 at 20:56, on Zulip):

there's something I don't understand

Santiago Pastorino (Jun 29 2018 at 20:57, on Zulip):

I don't see how this is going to do any better

Santiago Pastorino (Jun 29 2018 at 20:57, on Zulip):

I mean, if I understood correctly simulate_block is being called only from https://github.com/rust-lang/rust/blob/master/src/librustc_mir/borrow_check/nll/type_check/liveness.rs#L52-L54 and that function pass down to simulate_block

Santiago Pastorino (Jun 29 2018 at 20:57, on Zulip):

the thing is, each call is with a different bb, so I don't see any reuse because each call will build a different thing

Santiago Pastorino (Jun 29 2018 at 21:00, on Zulip):

so I'd be basically moving the clone call to the caller and passing that down

Santiago Pastorino (Jun 29 2018 at 21:00, on Zulip):

with no reuse, because I'd need to do that inside the loop

nikomatsakis (Jun 30 2018 at 09:25, on Zulip):

the thing is, each call is with a different bb, so I don't see any reuse because each call will build a different thing

all basic blocks can re-use the same buffer

nikomatsakis (Jun 30 2018 at 09:26, on Zulip):

where we now clone the foo[bb], we would want to use overwrite to write the data in

nikomatsakis (Jun 30 2018 at 09:26, on Zulip):

tbh, I don't know if it will be much of a win or not

nikomatsakis (Jun 30 2018 at 09:26, on Zulip):

it's just saving an allocation basically

nikomatsakis (Jun 30 2018 at 09:26, on Zulip):

(and a free)

Santiago Pastorino (Jun 30 2018 at 14:49, on Zulip):

I know that's very easy what we need to do but I'm still not catching exactly what you meant

Santiago Pastorino (Jun 30 2018 at 14:49, on Zulip):

@nikomatsakis to be 100% specific

Santiago Pastorino (Jun 30 2018 at 14:50, on Zulip):

I was getting that you mean to use a buffer with self.outs[bb] content but that doesn't make any sense to me, that's why I have doubts about exactly what you want to do

Santiago Pastorino (Jun 30 2018 at 14:50, on Zulip):

if you mean to use a buffer with self.outs, makes sense :)

Santiago Pastorino (Jun 30 2018 at 14:51, on Zulip):

if the buffer is about self.outs[bb] I think we would be just moving things around because there's no reuse of the outs for a specific basic block

Santiago Pastorino (Jun 30 2018 at 14:52, on Zulip):

what is reused is self.outs being used on each call with a different bb

Santiago Pastorino (Jul 01 2018 at 03:43, on Zulip):

@nikomatsakis forgot to share a link with my changes to check if that was the idea you had ...

Santiago Pastorino (Jul 01 2018 at 03:43, on Zulip):

https://github.com/spastorino/rust/commit/986bb2a81ee58a35b5deb729fb8f1cdf53b774d3

nikomatsakis (Jul 01 2018 at 09:36, on Zulip):

@Santiago Pastorino I left various comments on the commit — the key differences are:

Santiago Pastorino (Jul 01 2018 at 13:47, on Zulip):
you don't need a separate regular/drops buffer -- the buffer is just a bitset of local variables, and the set of local variables comes from the MIR, it is the same for the regular/drop computation. If we add the helper I suggested below, this would be something like:

let mut simulate_buffer = self.liveness.make_simulate_buffer(self.mir);
Santiago Pastorino (Jul 01 2018 at 13:47, on Zulip):

@nikomatsakis I thought we talked that regular.outs was the set of live locals when you only consider regular uses

Santiago Pastorino (Jul 01 2018 at 13:48, on Zulip):

and drop.outs was the set of live locals you consider for drops

nikomatsakis (Jul 01 2018 at 13:48, on Zulip):

that is correct

nikomatsakis (Jul 01 2018 at 13:48, on Zulip):

however

Santiago Pastorino (Jul 01 2018 at 13:48, on Zulip):

that's why I cloned regulars and drops

nikomatsakis (Jul 01 2018 at 13:48, on Zulip):

both are sets of variables

nikomatsakis (Jul 01 2018 at 13:48, on Zulip):

that is, the "domain" of each set is the same

nikomatsakis (Jul 01 2018 at 13:48, on Zulip):

and the buffer is just a temporary set over that (same) domain

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

more concretely, it is a bit set

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

and the point is that the number of bits in both cases is the same

Santiago Pastorino (Jul 01 2018 at 13:49, on Zulip):

you meant that in the method this thing is overwritten?

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

(but different bits will be set / unset)

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

do you mean "overwritten"?

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

if so, yes

Santiago Pastorino (Jul 01 2018 at 13:49, on Zulip):

yes, overwritten

nikomatsakis (Jul 01 2018 at 13:49, on Zulip):

basically what that method (simulate_block()) does is something like this:

Santiago Pastorino (Jul 01 2018 at 13:49, on Zulip):

ahhh ok ok ok, now makes sense

Santiago Pastorino (Jul 01 2018 at 13:50, on Zulip):

it never made sense until I hear that things are overwritten :)

nikomatsakis (Jul 01 2018 at 13:50, on Zulip):
let mut buffer = starting_value.clone();

for each statement in reverse order {
    mutate(&mut buffer);
    callback(&buffer);
}
Santiago Pastorino (Jul 01 2018 at 13:50, on Zulip):

yes yes

Santiago Pastorino (Jul 01 2018 at 13:50, on Zulip):

now makes sense

Santiago Pastorino (Jul 01 2018 at 13:50, on Zulip):

that's why I wasn't following

nikomatsakis (Jul 01 2018 at 13:50, on Zulip):

and now we will do something like:

let buffer = allocate();
...
loop {
  copy_initial_values(&mut buffer);

  for each statement in reverse order {
    mutate(&mut buffer);
    callback(&buffer);
  }
}
nikomatsakis (Jul 01 2018 at 13:50, on Zulip):

yeah, ok

Santiago Pastorino (Jul 01 2018 at 13:51, on Zulip):

I knew things were modified but not that the buffer was entirely overwritten

nikomatsakis (Jul 01 2018 at 13:51, on Zulip):

tbh I'm not sure if it will be a win :) but it can't hurt I guess

Santiago Pastorino (Jul 01 2018 at 13:51, on Zulip):

I mean

Santiago Pastorino (Jul 01 2018 at 13:51, on Zulip):

mainly because that buffer starts with the set of live locals at the end of the block

nikomatsakis (Jul 01 2018 at 13:51, on Zulip):

njn found that there were a lot more allocations in the NLL path, so part of this is a drive to shave those off and see if it helps

Santiago Pastorino (Jul 01 2018 at 13:51, on Zulip):

so I never imagined that those things were changed

Santiago Pastorino (Jul 01 2018 at 13:53, on Zulip):

so ... to be 100% sure

Santiago Pastorino (Jul 01 2018 at 13:54, on Zulip):

if this bitset has 50 bits of locals set, all those 50 bits will be changed?

Santiago Pastorino (Jul 01 2018 at 13:54, on Zulip):

I'm going to check the code for some reason I was kind of skeptical of that :P

Santiago Pastorino (Jul 01 2018 at 13:55, on Zulip):

because if everything is changed why that doesn't use a new set and start filling it?

nikomatsakis (Jul 01 2018 at 13:57, on Zulip):

I am confused

nikomatsakis (Jul 01 2018 at 13:57, on Zulip):

I mean I thikn the answer is yes?

nikomatsakis (Jul 01 2018 at 13:58, on Zulip):

but I'm not sure exactly what you are asking

nikomatsakis (Jul 01 2018 at 13:58, on Zulip):

changed by what?

Santiago Pastorino (Jul 01 2018 at 13:59, on Zulip):

:(

Santiago Pastorino (Jul 01 2018 at 13:59, on Zulip):

hehe

Santiago Pastorino (Jul 01 2018 at 14:00, on Zulip):

I've been having a lot of english/understanding issues with this task :(

Santiago Pastorino (Jul 01 2018 at 14:00, on Zulip):

hmm

Santiago Pastorino (Jul 01 2018 at 14:00, on Zulip):

let me try to explain

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

Before:

loop {
  let mut buffer = starting_value.clone(); // same as:
  // let mut buffer = buffer.allocate(num_locals);
  // copy_initial_values(&mut buffer, &starting_value);

  for each statement in reverse order {
    mutate(&mut buffer);
    callback(&buffer);
  }
}

after:

let buffer = allocate(num_locals);
...
loop {
  copy_initial_values(&mut buffer, &starting_value);

  for each statement in reverse order {
    mutate(&mut buffer);
    callback(&buffer);
  }
}
Santiago Pastorino (Jul 01 2018 at 14:02, on Zulip):

I see what you mean

Santiago Pastorino (Jul 01 2018 at 14:03, on Zulip):

the key is ...

Santiago Pastorino (Jul 01 2018 at 14:03, on Zulip):

buffer.overwrite(&self.outs[block]);

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

(note: this only makes sense because we are using a dense bitset)

Santiago Pastorino (Jul 01 2018 at 14:04, on Zulip):

the problem was ... when you said reuse I've tried to reuse values and you meant reuse memory

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

since then we allocate same amount no matter what

Santiago Pastorino (Jul 01 2018 at 14:04, on Zulip):

I didn't see any way to reuse values

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

ah, I see. Yes.

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

Correct.

Santiago Pastorino (Jul 01 2018 at 14:08, on Zulip):

will change this in a bit if I have time :)

Santiago Pastorino (Jul 01 2018 at 14:08, on Zulip):

was your PR, the one from where I was starting off, merged?

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

I think you mean https://github.com/rust-lang/rust/pull/51896 ?

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

if so, not yet

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

hmm looks like it has some error too

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

will fix

Santiago Pastorino (Jul 01 2018 at 14:16, on Zulip):

ok

Santiago Pastorino (Jul 01 2018 at 19:32, on Zulip):

@nikomatsakis https://github.com/rust-lang/rust/commit/9cc337339c7730335364079cd94ed92f58efa046

nikomatsakis (Jul 02 2018 at 15:35, on Zulip):

@Santiago Pastorino that looks right to me

Santiago Pastorino (Jul 02 2018 at 15:35, on Zulip):

:+1:

nikomatsakis (Jul 02 2018 at 15:35, on Zulip):

overwrite should exist on master; maybe not on that branch. You can use IdxSet::clone_from(...) if not

nikomatsakis (Jul 02 2018 at 15:35, on Zulip):

but that method got renamed to overwrite

Santiago Pastorino (Jul 02 2018 at 15:36, on Zulip):

but clone_from does some clones so it allocates stuff

nikomatsakis (Jul 02 2018 at 15:36, on Zulip):

it does not

Santiago Pastorino (Jul 02 2018 at 15:36, on Zulip):

I wanted to avoid allocations

Santiago Pastorino (Jul 02 2018 at 15:36, on Zulip):

no?

nikomatsakis (Jul 02 2018 at 15:36, on Zulip):

not IdxSet::clone_from, specifically

nikomatsakis (Jul 02 2018 at 15:36, on Zulip):

but there is another method (Clone::clone_from) that does

nikomatsakis (Jul 02 2018 at 15:36, on Zulip):

this is why we renamed IdxSet::clone_from

nikomatsakis (Jul 02 2018 at 15:37, on Zulip):

in https://github.com/rust-lang/rust/pull/51869

Santiago Pastorino (Jul 02 2018 at 15:39, on Zulip):

I see

Santiago Pastorino (Jul 02 2018 at 15:40, on Zulip):

well, does it worth to change the code? no matter what I do is going to conflict in master

Santiago Pastorino (Jul 02 2018 at 15:40, on Zulip):

unless I do this stuff against master itself

Santiago Pastorino (Jul 02 2018 at 15:40, on Zulip):

instead of your branch

nikomatsakis (Jul 02 2018 at 15:42, on Zulip):

I suspect you could rebase on to master and it would be fine, else wait for my branch to land

nikomatsakis (Jul 02 2018 at 15:42, on Zulip):

the PR is r+'d now

Santiago Pastorino (Jul 02 2018 at 15:46, on Zulip):

yeah :)

Santiago Pastorino (Jul 02 2018 at 15:47, on Zulip):

will wait

Santiago Pastorino (Jul 02 2018 at 15:47, on Zulip):

ping me when it lands

nikomatsakis (Jul 02 2018 at 15:48, on Zulip):

ok, I'm planning to push a bit harder on triage and think things over

nikomatsakis (Jul 02 2018 at 15:48, on Zulip):

in terms of "what's next"

Santiago Pastorino (Jul 02 2018 at 17:40, on Zulip):

:+1:

nikomatsakis (Jul 02 2018 at 22:08, on Zulip):

@Santiago Pastorino you could rebase now

Santiago Pastorino (Jul 02 2018 at 22:21, on Zulip):

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

nikomatsakis (Jul 03 2018 at 00:18, on Zulip):

@Santiago Pastorino [00:04:32] tidy error: /checkout/src/librustc_mir/util/liveness.rs:169: line longer than 100 chars

Santiago Pastorino (Jul 03 2018 at 00:19, on Zulip):

@nikomatsakis facepalm, yeah just saw it and was fixing it

Santiago Pastorino (Jul 03 2018 at 00:22, on Zulip):

pushed

Santiago Pastorino (Jul 03 2018 at 00:23, on Zulip):

@nikomatsakis now it's fine :)

Santiago Pastorino (Jul 04 2018 at 18:35, on Zulip):

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

nikomatsakis (Jul 04 2018 at 18:38, on Zulip):

@Santiago Pastorino https://github.com/rust-lang/rust/pull/52007#pullrequestreview-134453710

Santiago Pastorino (Jul 04 2018 at 18:44, on Zulip):

@nikomatsakis ...

Santiago Pastorino (Jul 04 2018 at 18:44, on Zulip):
    /// Create an empty `LocalSet` buffer to be mutably shared accross different calls to
    /// `simulate_block`, hence reducing memory allocation.
Santiago Pastorino (Jul 04 2018 at 18:44, on Zulip):

sounds like proper english?

Santiago Pastorino (Jul 04 2018 at 18:44, on Zulip):

:stuck_out_tongue:

nikomatsakis (Jul 04 2018 at 18:47, on Zulip):

yep :)

Santiago Pastorino (Jul 04 2018 at 18:47, on Zulip):

pushed again

nikomatsakis (Jul 04 2018 at 18:48, on Zulip):

I'm wondering if I should just r+

nikomatsakis (Jul 04 2018 at 18:49, on Zulip):

I guess it might not help

nikomatsakis (Jul 04 2018 at 18:49, on Zulip):

that would not, really, surprise me very much

Santiago Pastorino (Jul 04 2018 at 19:23, on Zulip):

hehe yeah

Santiago Pastorino (Jul 05 2018 at 11:29, on Zulip):

@nikomatsakis https://perf.rust-lang.org/compare.html?start=860d169474acabdc53b9a698f8ce02eba7e0daeb&end=00bcc44fb92c28465c727881355c3235a56a4045&stat=instructions%3Au

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

hmm, kind of looks like noise

nikomatsakis (Jul 05 2018 at 11:35, on Zulip):

I think I'm inclined not to land it

nikomatsakis (Jul 05 2018 at 11:35, on Zulip):

if it doesn't really help performance, it's mildly less clean, and it could make future refactorings more annoying

nikomatsakis (Jul 05 2018 at 11:35, on Zulip):

what do you think?

Santiago Pastorino (Jul 05 2018 at 13:26, on Zulip):

agreed

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

ok, closed

Last update: Nov 21 2019 at 15:15UTC