Stream: wg-traits

Topic: fuel friendly branch


nikomatsakis (Dec 06 2019 at 21:28, on Zulip):

OK @Jack Huey I pushed a bunch of nits and minor changes to your branch. I'm going to merge the PR, assuming travis is green. I sort of convinced myself that the strategy is correct, modulo that I think we're not handling the "refined answers" correctly, but that is probably pre-existing, as you pointed out.

I suspect we can continue to cleanup the code, but that seems better pursued as an iterative strategy. (If nothing else, I found that some of the comments made more sense in the recursive setup.)

nikomatsakis (Dec 06 2019 at 21:28, on Zulip):

One thing I found a bit hard to read was the idiom where we would pop something from the stack after getting a result to look at the "next top-most" thing. I'm not quite sure what would make it nicer though. =)

nikomatsakis (Dec 06 2019 at 21:29, on Zulip):

I think probably just a naming convention would help

nikomatsakis (Dec 06 2019 at 21:29, on Zulip):

e.g., some way to flag "this is the strand that was on top from the strand we started with"

nikomatsakis (Dec 06 2019 at 21:29, on Zulip):

I guess a good name might be "caller"

nikomatsakis (Dec 06 2019 at 21:29, on Zulip):

maybe I'll toy with that

nikomatsakis (Dec 06 2019 at 21:30, on Zulip):

I wonder also about doing something like &mut depth for modifying the depth variable

nikomatsakis (Dec 06 2019 at 21:31, on Zulip):

debatable, I guess, if the depth variable is even adding much value here

nikomatsakis (Dec 06 2019 at 21:31, on Zulip):

oh, nm, we use it to index a lot, forgot

Jack Huey (Dec 06 2019 at 21:36, on Zulip):

Just looked through your changes, they all look good to me :)

nikomatsakis (Dec 06 2019 at 21:37, on Zulip):

trying one last thing

Jack Huey (Dec 06 2019 at 21:37, on Zulip):

So, I definitely see where you're coming from with the "next top-most thing"

Jack Huey (Dec 06 2019 at 21:38, on Zulip):

I thought about this. Was thinking of how to maybe delay that handling to the beginning of the next loop (like storing some sort of answer), but didn't explore too much. If anything, it can be done iteratively

Jack Huey (Dec 06 2019 at 21:38, on Zulip):

And, honestly the depth variable is a little messy

Jack Huey (Dec 06 2019 at 21:39, on Zulip):

passing as &mut depth is not the worst idea

Jack Huey (Dec 06 2019 at 21:43, on Zulip):

It might be possible to remove it though

Jack Huey (Dec 06 2019 at 21:43, on Zulip):

or at least, in most cases

Jack Huey (Dec 06 2019 at 21:44, on Zulip):

Off of the top of my head, the only place (there might be others I'm forgetting) we use it is when dealing with cycles

nikomatsakis (Dec 06 2019 at 21:51, on Zulip):

OK, @Jack Huey I have a decent commit

nikomatsakis (Dec 06 2019 at 21:52, on Zulip):

it may be possible to remove depth, not sure, but this change is at least positive

nikomatsakis (Dec 06 2019 at 21:52, on Zulip):

just pushed

Jack Huey (Dec 06 2019 at 21:54, on Zulip):

Ok I'll take a look

nikomatsakis (Dec 06 2019 at 21:56, on Zulip):

it seems to me that there are some invariants that might be nice to document, too

Jack Huey (Dec 06 2019 at 21:56, on Zulip):

Looks good to me!

nikomatsakis (Dec 06 2019 at 21:56, on Zulip):

e.g., "everything on the stack has an active strand on each turn around the loop"

Jack Huey (Dec 06 2019 at 21:57, on Zulip):

Ah true

nikomatsakis (Dec 06 2019 at 21:57, on Zulip):

I suspect that's true at some point ;)

Jack Huey (Dec 06 2019 at 21:58, on Zulip):

I'm thinking about it. But we could might be able to get rid of the idea of a stack nearly entirely at some point

Jack Huey (Dec 06 2019 at 21:59, on Zulip):

I think the only thing we actually have to keep track of is the tables on the stack

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

@Jack Huey Maybe. what I'm actually thinking about now is that I think the stack should persist even when we return "quantum exceeded"

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

and when you enter with the same root table/index

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

we should just jump back down

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

without re-incrementing the clock

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

otherwise, it's probably possible to have something where we don't recognize a cycle

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

and besides it's kind of wasteful, no?

nikomatsakis (Dec 06 2019 at 22:42, on Zulip):

but we'd have to think a bit carefully about it to make sure it all works out

nikomatsakis (Dec 06 2019 at 22:43, on Zulip):

anyway, I merged the PR

nikomatsakis (Dec 06 2019 at 22:43, on Zulip):

I should file some follow-up issues

Jack Huey (Dec 06 2019 at 23:03, on Zulip):

and besides it's kind of wasteful, no?

I think this is where benchmarks would be nice. Just how much overhead is there. The other thing with this: right now, when QuantumExceeded is returned, the next iteration pursues the next strand (and the current one gets put at the end)

nikomatsakis (Dec 06 2019 at 23:18, on Zulip):

Well, that's by design for sure

nikomatsakis (Dec 06 2019 at 23:19, on Zulip):

maybe not a good design :)

nikomatsakis (Dec 06 2019 at 23:19, on Zulip):

but we'd have to think a bit carefully about it to make sure it all works out

but that is precisely the sort of interaction I was thinking about when I wrote this

nikomatsakis (Dec 06 2019 at 23:19, on Zulip):

in other words: the idea of quantum exceeded was "this path isn't that great, let's try another strand"

nikomatsakis (Dec 06 2019 at 23:19, on Zulip):

that said, I think there are better heuristics no doubt

nikomatsakis (Dec 06 2019 at 23:20, on Zulip):

but it may be that in some cases we don't want to do that

nikomatsakis (Dec 06 2019 at 23:20, on Zulip):

and I'm curious to try some other search algorithms

Jack Huey (Dec 06 2019 at 23:21, on Zulip):

Yeah, could be interesting

Last update: Jun 07 2020 at 09:15UTC