Stream: t-compiler/wg-nll

Topic: issue-51813-dirty-list-in-dataflow


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

Hey @Pramod Bisht, I saw you assigned https://github.com/rust-lang/rust/issues/51813 to yourself! Sounds good. Let me know how it goes.

Pramod Bisht (Jun 28 2018 at 05:11, on Zulip):

@nikomatsakis
as per your instruction I implemented something like this https://gist.github.com/PramodBisht/3bf922125f8948f27bf053bcd496c208
However I am getting exception like this https://gist.github.com/PramodBisht/858da0bb18c59130e88ace5af3c2136f/revisions?diff=unified

Could you give me pointer or two what I am doing wrong?

nikomatsakis (Jun 28 2018 at 10:02, on Zulip):

leaving aside relatively minor nits, I think the immediate bug is that you are populating the dirty list with the wrong thing. =)

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

roughly speaking, the way that the propagation works is like this:

for each basic block B {
    compute new data D for B;
    for each successor S of B {
        if in_data(S) != D {
            in_data(S) = D;
            changed = true;
        }
    }
}
nikomatsakis (Jun 28 2018 at 10:04, on Zulip):

you changed it to this:

dirty_blocks = [];
for each block B in dirty_blocks {
    compute new data D for B;
    for each successor S of B {
        if in_data(S) != D {
            in_data(S) = D;
            changed = true;
        }
    }
    if any successor changed {
       dirty_blocks.push(B);
    }
}
nikomatsakis (Jun 28 2018 at 10:04, on Zulip):

(sort of)

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

here, you are pushing the block B

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

but in fact that block is now "clean" -- that is, we've processed it

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

the dirty blocks are its successors

nikomatsakis (Jun 28 2018 at 10:05, on Zulip):

that is, you want something like this

dirty_blocks = [];
for each block B in dirty_blocks {
    compute new data D for B;
    for each successor S of B {
        if in_data(S) != D {
            in_data(S) = D;
            dirty_blocks.push(S);
            changed = true;
        }
    }
}
nikomatsakis (Jun 28 2018 at 10:05, on Zulip):

(in fact, we should be able to remove the changed flag eventually and just check whether the dirty list is empty or not)

nikomatsakis (Jun 28 2018 at 10:06, on Zulip):

you can actually manage the worklist quite well with a FxHashSet and a VecDeque combined

nikomatsakis (Jun 28 2018 at 10:06, on Zulip):

but anyway let's get it working first then we'll fine-tune

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

in terms of your gist, you will want to change these lines here:

             builder.propagate_bits_into_graph_successors_of(
                 in_out, &mut self.changed, (mir::BasicBlock::new(bb_idx), bb_data));

because you need to pass the dirty list into the function.

nikomatsakis (Jun 28 2018 at 10:08, on Zulip):

actually, if we look at the source for propagate_bits_into_graph_successors_of, you can see that it mostly calls a helper function

nikomatsakis (Jun 28 2018 at 10:10, on Zulip):

that function is propagate_bits_into_entry_set_for; this function too wants to take the dirty list as argument. Instead of

if set_changed {
            *changed = true;
}

it wants to do

if set_changed {
    dirty_list.push(*bb);
    *changed = true;
}

(Also, we should change it to take mir::BasicBlock and not &mir::BasicBlock -- this is just an integer, so the latter is kind of silly, but that's not really related)

nikomatsakis (Jun 28 2018 at 10:10, on Zulip):

@Pramod Bisht make sense?

Pramod Bisht (Jun 28 2018 at 13:50, on Zulip):

@nikomatsakis yes, it makes sense :)

Pramod Bisht (Jun 29 2018 at 03:29, on Zulip):

Hi @nikomatsakis as you instructed I implemented something like this https://gist.github.com/PramodBisht/3bf922125f8948f27bf053bcd496c208/revisions
This block compiles successfully. However, I am getting some weird error like this
https://gist.github.com/PramodBisht/858da0bb18c59130e88ace5af3c2136f/revisions?diff=unified

Could you give pointer or two what I am doing wrong?

Pramod Bisht (Jun 29 2018 at 05:38, on Zulip):

please ignore this message, something occurred while checking message on android app.

nikomatsakis (Jun 29 2018 at 09:19, on Zulip):

@Pramod Bisht no worries. The android app is Zulip's big weakness, I would say... :(

nikomatsakis (Jun 29 2018 at 11:06, on Zulip):

@Pramod Bisht btw PR #51896 may interest you -- it adds a similar work queue to the liveness computation

nikomatsakis (Jun 29 2018 at 11:58, on Zulip):

also, @Pramod Bisht, feel free to open a [WIP] PR with your branch. It tends to make it much easier for me to give feedback

Pramod Bisht (Jun 29 2018 at 12:00, on Zulip):

sure @nikomatsakis, first I am trying to implement using naive approach, then I will do changes which will use your new implemented work_queue.

Pramod Bisht (Jun 29 2018 at 12:01, on Zulip):

is that okay?

nikomatsakis (Jun 29 2018 at 12:02, on Zulip):

seems good

Pramod Bisht (Jun 29 2018 at 13:41, on Zulip):

@nikomatsakis please find WIP state here https://github.com/rust-lang/rust/pull/51900

Pramod Bisht (Jun 29 2018 at 13:44, on Zulip):

to be more precise this is the changeset https://github.com/rust-lang/rust/pull/51900/files#diff-e1d33bfc0f6996e6a7d96525162675e4

Pramod Bisht (Jun 29 2018 at 13:46, on Zulip):

I am also waiting for build to complete.

nikomatsakis (Jun 29 2018 at 13:54, on Zulip):

great! first round of feedback here

lqd (Jun 29 2018 at 14:02, on Zulip):

"odd annotation" == odd indentation ? ;)

Pramod Bisht (Jun 29 2018 at 14:17, on Zulip):

I think for this line let sets = builder.flow_state.sets.for_block(bb_idx); , or I should use integer form of BasicBlock?

Pramod Bisht (Jun 29 2018 at 14:18, on Zulip):

video link was posted accidentally :)

Santiago Pastorino (Jun 29 2018 at 14:18, on Zulip):

(deleted)

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

I'm confused

Pramod Bisht (Jun 29 2018 at 14:20, on Zulip):

I think for this line let sets = builder.flow_state.sets.for_block(bb_idx); we may need to maintain counter bb_idx, I think right value should be integer form of BasicBlock right?

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

hmm, let me look

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

oh, yes, you can use bb

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

you can use bb.index() or something like that

lqd (Jun 29 2018 at 14:33, on Zulip):

@Pramod Bisht tidy failed before and is likely going to fail again

Pramod Bisht (Jun 29 2018 at 14:34, on Zulip):

@lqd let me check.

nikomatsakis (Jun 29 2018 at 14:36, on Zulip):

oh tidy

nikomatsakis (Jun 29 2018 at 14:36, on Zulip):

so annoying

Pramod Bisht (Jun 29 2018 at 14:50, on Zulip):

My local build got failed, fixing them.

Pramod Bisht (Jun 29 2018 at 16:01, on Zulip):

@nikomatsakis many testcases related to that failed. I have pasted logs at https://gist.github.com/PramodBisht/0ad38646e007973c0924996a0e186eae

lqd (Jun 29 2018 at 16:04, on Zulip):

you might need https://github.com/rust-lang/rust/pull/51896/commits/f140bcac20777ac15824324b517420b11edd07b2

Pramod Bisht (Jun 29 2018 at 16:05, on Zulip):

@lqd I rebased branch with that commit.

lqd (Jun 29 2018 at 16:08, on Zulip):

and it still fails anyway, you mean ?

Pramod Bisht (Jun 29 2018 at 16:11, on Zulip):

@lqd yes you are right, actually I pushed that to GH but I forgot to take pull on Janitor's remote machine where I execute that.

lqd (Jun 29 2018 at 16:11, on Zulip):

:thumbs_up:

nikomatsakis (Jun 29 2018 at 17:11, on Zulip):

I left some nits @Pramod Bisht but it looks correct to me — are you still getting test failures?

Pramod Bisht (Jun 29 2018 at 17:13, on Zulip):

@nikomatsakis no I am not getting any test case failure. Checking nits

nikomatsakis (Jun 29 2018 at 17:13, on Zulip):

ah, ok, great!

nikomatsakis (Jun 29 2018 at 17:13, on Zulip):

I can merge your changes in and re-profile perhaps

Pramod Bisht (Jun 29 2018 at 17:17, on Zulip):

before that should I change ref target to target, btw that looks much cleaner and other nits. Plus I am waiting for travis CI to complete.

nikomatsakis (Jun 29 2018 at 17:17, on Zulip):

ah well I just meant merge it into this local branch I have

nikomatsakis (Jun 29 2018 at 17:17, on Zulip):

so I can measure the effect

nikomatsakis (Jun 29 2018 at 17:17, on Zulip):

(locally)

nikomatsakis (Jun 29 2018 at 17:17, on Zulip):

I'll r+ once the nits are fixed, yes

nikomatsakis (Jun 29 2018 at 17:17, on Zulip):

(and travis is happy etc)

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

given that this builds on my PR... I wonder if I should just close that in favor of yours

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

I'd like to have the original r+'d

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

seems like it'd be better for them to merge separately though, just to have the perf data if nothing else

Pramod Bisht (Jun 29 2018 at 17:22, on Zulip):

@nikomatsakis do you run perf on your local machine, or we have dedicated machine for that?
Almost a week back, I tried to follow your perf instruction, but got stuck while installing it.

nikomatsakis (Jun 29 2018 at 17:22, on Zulip):

I run perf locally, yes, but we also have a dedicatd perf machine: perf.rust-lang.org

nikomatsakis (Jun 29 2018 at 17:22, on Zulip):

(that shows the results)

nikomatsakis (Jun 29 2018 at 17:22, on Zulip):

it computes the timing results from each PR as it lands

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

but we also sometimes compute results for PRs that not yet landed

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

are you using linux?

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

I'm surprised you had to 'install' perf :)

Pramod Bisht (Jun 29 2018 at 17:23, on Zulip):

Yes

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

or maybe I've always done that and forgotten ;)

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

that said, I should also add instructions for profiling with callgrind and the like

nikomatsakis (Jun 29 2018 at 17:23, on Zulip):

which is also excellent

Pramod Bisht (Jun 29 2018 at 17:24, on Zulip):

`
WARNING: perf not found for kernel 4.6.0-040600rc7

You may need to install the following packages for this specific kernel:
linux-tools-4.6.0-040600rc7-generic
linux-cloud-tools-4.6.0-040600rc7-generic

You may also want to install one of the following packages to keep up to date:
linux-tools-generic-lts-<series>
linux-cloud-tools-generic-lts-<series>

`
I get something like that

nikomatsakis (Jun 29 2018 at 17:24, on Zulip):

ah... I have no idea :)

nikomatsakis (Jun 29 2018 at 17:24, on Zulip):

sounds like you maybe need to upgrade :)

Pramod Bisht (Jun 29 2018 at 17:26, on Zulip):

but those series perf packages were not found when I searched them.
I will check it again some other time.
Yes, I am using Ubuntu 14.04, because of some legacy stuff, I always deferred upgrading it.

nikomatsakis (Jun 29 2018 at 17:26, on Zulip):

yeah, that might be it. you sound a bit like me ;)

Pramod Bisht (Jun 29 2018 at 17:26, on Zulip):

getting back to nits :)

nikomatsakis (Jun 29 2018 at 17:26, on Zulip):

I'm always hating to upgrade

Pramod Bisht (Jun 29 2018 at 17:26, on Zulip):

:)

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

/me just wants the computer to work damn it

Jake Goulding (Jun 29 2018 at 17:32, on Zulip):

/me just wants the computer to work damn it

You know how programmers make the computer work again when it wasn't working in the first place, yeah? :wink:

Jake Goulding (Jun 29 2018 at 17:33, on Zulip):

@nikomatsakis is still running Rust 1.0

nikomatsakis (Jun 29 2018 at 17:33, on Zulip):

lololol

nikomatsakis (Jun 29 2018 at 17:33, on Zulip):

you know me

nikomatsakis (Jun 29 2018 at 17:51, on Zulip):

hmm, my profiling results are not that encouraging :( but I'm not sure I trust my measurements.

nikomatsakis (Jun 29 2018 at 17:51, on Zulip):

we should definitely do a bors try run

nikomatsakis (Jun 29 2018 at 17:52, on Zulip):

(we may want to experiment with alternative execution strategies too; it's not always clear that a work queue is fastest, for example)

Pramod Bisht (Jun 29 2018 at 18:37, on Zulip):

should we consider giving flags for alternative execution strategy?

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

I'd say that's a bit premature

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

let's do some more measurement first

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

did you address the nits btw?

Pramod Bisht (Jun 29 2018 at 18:40, on Zulip):

have given build command with those nits

Pramod Bisht (Jun 29 2018 at 18:40, on Zulip):

will raise PR if everything goes fine.

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

:+1:

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

I will I think checkout just your PR

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

and make an optimized build of that

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

plus the master it's based on

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

and compare the two

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

the nits shouldn't really affect perf anyway

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

I guess it's based on my commit

lqd (Jun 29 2018 at 18:45, on Zulip):

(I noticed the nits aren't — this time — signed "Your capricious reviewer" :D)

nikomatsakis (Jun 29 2018 at 19:05, on Zulip):

hmm I was thinking about this some more

nikomatsakis (Jun 29 2018 at 19:05, on Zulip):

there is some research in different eval strategies

nikomatsakis (Jun 29 2018 at 19:06, on Zulip):

e.g., one thing you can do is to compute SCC (strongly connected components / cycles, basically)

nikomatsakis (Jun 29 2018 at 19:06, on Zulip):

which converts the flow graph into a tree

nikomatsakis (Jun 29 2018 at 19:06, on Zulip):

and then you can do a single walk over the tree, iterating only within a component etc

nikomatsakis (Jun 29 2018 at 19:06, on Zulip):

I guess we should go find those papers ;)

nikomatsakis (Jun 29 2018 at 19:07, on Zulip):

@Pramod Bisht hmm yeah I'm definitely finding that your branch is slower :(

nikomatsakis (Jun 29 2018 at 19:07, on Zulip):

for.. whatever reason

nikomatsakis (Jun 29 2018 at 19:08, on Zulip):

the paper I was thinking of https://pdfs.semanticscholar.org/db53/41a4bc653b84a12780139d795a910c1c8b60.pdf

Pramod Bisht (Jun 29 2018 at 19:38, on Zulip):

Yup this should have run faster :( . Lets see what we can get from that paper.

nikomatsakis (Jun 29 2018 at 19:40, on Zulip):

could also be a bug somewhere

nikomatsakis (Jun 29 2018 at 19:40, on Zulip):

might be worth dumping the debug logs

nikomatsakis (Jun 29 2018 at 19:40, on Zulip):

and making sure it's doing what we expect

Pramod Bisht (Jun 29 2018 at 19:42, on Zulip):

if number of iteration have reduced then this should have run faster.

Pramod Bisht (Jun 29 2018 at 19:43, on Zulip):

I think maintaining counter and printing in debug log should help.

Pramod Bisht (Jun 29 2018 at 19:52, on Zulip):

@nikomatsakis instead of populating basic blocks from IndexVec I did this
let mut dirty_queue: WorkQueue<mir::BasicBlock> = WorkQueue::with_all(self.builder.mir.basic_blocks().len()); assuming they are bb in ascending integer order. do you think this can also be a cause ?

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

I think that was the same as what it was doing before

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

there was some revision -- not sure where -- where we were iterating in reverse-post-order instead

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

but you'd have to look back in the history to see where that was removed

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

probably because computing the RPO took time

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

and it wasn't worth it

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

@Pramod Bisht the perf results are quite interesting:

http://perf.rust-lang.org/compare.html?start=87ecf5442ced38a6253e670dd6d87c0c334b21fb&end=ddc3f99bad126b9f5755177d82f651d8f91d8683&stat=instructions%3Au

It seems like my local measurement was correct but misleading -- clap-rs did get slower (by 2.5%) but lots of stuff is way faster!

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

e.g., serde-check goes from a ratio of 1.33 to 1.2

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

seems like we should land it :)

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

though it may be interesting to experiment with further stuff

lqd (Jul 02 2018 at 16:05, on Zulip):

since it looks like it's just clap, it could be a bit of noise as well

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

could be, although I saw it too

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

it turns out that this version of clap is quite different from the current one

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

we should test with "real clap" too

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

this particular one is a historical artifact that used to cause some kind of perf pathology during MIR construction

lqd (Jul 02 2018 at 16:07, on Zulip):

yeah even though it's code from the real world, it was pinpointing a defect much like the other synthetized stress tests

Pramod Bisht (Jul 02 2018 at 16:11, on Zulip):

:thumbs_up::thumbs_up::thumbs_up:

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

I'm inclined to r+, unless you want to cleanup the history @Pramod Bisht

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

it needs a rebase anyway

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

I rebased https://github.com/rust-lang/rust/pull/51896 and r+'d it with p=1

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

since you were building on that

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

so hopefully it'll land in a few hours

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

(it's currently next in the queue)

Pramod Bisht (Jul 02 2018 at 16:14, on Zulip):

Yes, let me clean history and fix conflicts. Will do that once I reach home :)

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

thanks for your work on this

Pramod Bisht (Jul 02 2018 at 17:14, on Zulip):

thanks for your work on this

@nikomatsakis no, thank you, I just did what you instructed. I am very beginner in rust itself :)

lqd (Jul 02 2018 at 18:38, on Zulip):

@Pramod Bisht now that https://github.com/rust-lang/rust/pull/51869 has landed, shouldn't the IdxSet::clone_from be a call to overwrite ?

Pramod Bisht (Jul 02 2018 at 18:44, on Zulip):

@lqd checking

nikomatsakis (Jul 02 2018 at 18:44, on Zulip):

(yes, probably)

nikomatsakis (Jul 02 2018 at 18:45, on Zulip):

left this review to point out the spot: https://github.com/rust-lang/rust/pull/51900#pullrequestreview-133736810

nikomatsakis (Jul 02 2018 at 18:46, on Zulip):

(good catch @lqd)

nikomatsakis (Jul 02 2018 at 18:46, on Zulip):

although I guess travis caught it too ;)

lqd (Jul 02 2018 at 18:46, on Zulip):

I was about to say Travis did catch it before I did :)

Pramod Bisht (Jul 02 2018 at 18:51, on Zulip):

@nikomatsakis @lqd done!

nikomatsakis (Jul 02 2018 at 18:51, on Zulip):

jfyi https://github.com/rust-lang/rust/pull/51896 is pending on bors now

nikomatsakis (Jul 02 2018 at 18:51, on Zulip):

so tonight/tomorrow you can rebase ;)

nikomatsakis (Jul 02 2018 at 18:52, on Zulip):

I dont' know what the cycle time is these days

lqd (Jul 02 2018 at 18:53, on Zulip):

couple hours now IIRC

lqd (Jul 02 2018 at 18:53, on Zulip):

and it started 45mins ago, so not long now :)

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

@Pramod Bisht ok go ahead and rebase :)

Pramod Bisht (Jul 02 2018 at 20:31, on Zulip):

@nikomatsakis rebased with master.

nikomatsakis (Jul 02 2018 at 21:04, on Zulip):

r+

Pramod Bisht (Jul 04 2018 at 14:12, on Zulip):

Yes, let me clean history and fix conflicts. Will do that once I reach home :)

Last update: Nov 21 2019 at 13:05UTC