Stream: t-compiler/wg-nll

Topic: liveness-drops-vs-regular-uses


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

ok @Santiago Pastorino was asking me some questions about liveness and I'm moving it here

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

so we compute currently two sets of liveness bits

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

there is definitely some overlap here

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

the first set is "regular use live" — this implies that a variable will be used later on in a "regular" way. e.g., foo(x) makes x live for stuff that came before it

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

the second set is "drop live" — this implies that a variable will be dropped later on ... these are implicit actions generated by the compiler. So e.g. with { let x = vec![...]; ... } the x will be "drop live" during the ... because at the end of the block we are going to drop it

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

(note that mem::drop(x) is just a regular function call, despite its name)

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

there is overlap between these two sets because most things that will be used later may also be dropped — but not all things

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

notably integers or things that do not implement Drop

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

will not have a Drop opcode

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

so actually they are just kind of two distinct, but sometimes overlapping, sets

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

yeah makes sense

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

I think I was confused because you mentioned one thing being a subset of the other one

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

btw @Santiago Pastorino you mentioned sparse sets

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

I may have read it wrong :)

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

using them may well make sense

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

I may have read it wrong :)

no, I did say that, but I was mistaken

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

ok

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

the other optoin — instead of sparse sets — is to go "all in" with dense sets

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

this is what the other dataflow does

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

yeah, your explanation matches my understanding then :)

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

e.g. if you have N variables and M blocks

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

we currently allocate M dense sets of N bits each

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

we could allocate 1 dense set of M*N bits

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

and then just operate on subsets of that

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

this is what the main dataflow does, for locality or whatever else

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

it is unclear which is better :)

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

sparse sets may well be better

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

if you do that it could make sense to merge drops and uses

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

I was hoping off on suggesting much experimentation here because it's not that big a percentage of our overall time

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

I mean, you need more than one bit

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

but it's easy enough to experiment with a sparse set really

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

we have the code after all (hey, you wrote it=)

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

yes, I've copied it but yeah :P

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

:)

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

if you do that it could make sense to merge drops and uses

@nikomatsakis does this makes sense?

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

uh

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

I mean in the dense case and using more than one bit

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

i.e., really we would be allocating 2 sets of M*N

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

but it could be 1 of 2 x M x N instead?

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

well I guess it uses less memory :)

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

yeah, that could make sense, idk

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

it may not make that much difference

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

to do 2 big alloc vs 1 big one :)

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

it's not entirely clear that doing less alloc is really a win here anyway, would have to measure

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

yeah, but how much of those big allocs are done?

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

isn't one per fn?

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

it's not entirely clear that doing less alloc is really a win here anyway, would have to measure

anyway, agree, it should always be measured

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

anyway, if it's 2% of the thing it may not worth spending a lot of time now

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

cool

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

@nikomatsakis so I'm gonna focus on https://github.com/rust-lang/rust/issues/51818, then will ping you to see if worth to do the sparse bit set stuff and the rest I guess can wait

Last update: Nov 21 2019 at 13:10UTC