Stream: git-wasmtime

Topic: wasmtime / PR #4939 Avoid quadratic behavior in `can_opti...

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:13):

jameysharp requested cfallin for a review on PR #4939.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:13):

jameysharp opened PR #4939 from no-quadratic to main:

This fixes #4938/#4923, with a different take on #4924.

I think this maybe introduces worst-case quadratic behavior in declare_block_predecessor instead, though I think it would happen much less often. I'd appreciate any performance insights during review.

I want to work some more on the comments before merging this, because it was hard to get right and involves subtle invariants. But it does pass the test suite now and I think it's correct.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:13):

jameysharp requested fitzgen for a review on PR #4939.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:24):

jameysharp updated PR #4939 from no-quadratic to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:41):

afonso360 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:42):

bjorn3 created PR review comment:

Should this set in_predecessor_cycle to false?

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:42):

bjorn3 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:43):

afonso360 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 18:45):

afonso360 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:30):

jameysharp submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:30):

jameysharp created PR review comment:

No, it must already be false: there couldn't have been a cycle before because there were at least two predecessors. That's true whether pred is being added or removed.

But it's an excellent question so I'm adding a debug_assert there to check this.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:41):

bjorn3 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:41):

bjorn3 created PR review comment:

What if you went from

block1:
jump block2

block2:
jump block1

which has a predecessor cycle to

block0:
jump block1

block1:
jump block2

block2:
jump block1

which doesn't?

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:51):

jameysharp submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 19:51):

jameysharp created PR review comment:

In that example, block1 had one predecessor (block2), and now we're adding a second (pred is block0). This match is on the number of predecessors excluding pred, so we'd be in the one-predecessor case where pred gets re-assigned to point to block2, not this early-return case.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 20:04):

bjorn3 submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 20:04):

bjorn3 created PR review comment:

I see.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 21:10):

jameysharp updated PR #4939 from no-quadratic to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 21:22):

jameysharp has marked PR #4939 as ready for review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 23:31):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 23:31):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 21 2022 at 23:31):

cfallin created PR review comment:

Can we make add a small helper enum type, like enum AddRemove { Add, Remove } ? That would make the meaning of the bool much clearer.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 21:45):

jameysharp updated PR #4939 from no-quadratic to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 22:17):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 22:19):

cfallin submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 22:19):

cfallin created PR review comment:

a tiny thing but if you add #[derive(PartialEq, Eq)] (or maybe just PartialEq? I'm never clear on what needs what) to the enum, then this can be action == Action::Add, which I personally like a bit more for zero-arg enums (C-style enums). Totally up to you though.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 22:24):

jameysharp submitted PR review.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 22 2022 at 22:24):

jameysharp created PR review comment:

Oh, yeah, that is definitely nicer. Thanks for the suggestion!

I think PartialEq is technically enough but since the derived implementation is actually total, I think it's confusing to leave off Eq, so I'm going with both.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 23 2022 at 16:06):

jameysharp updated PR #4939 from no-quadratic to main.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 23 2022 at 16:08):

jameysharp has enabled auto merge for PR #4939.

view this post on Zulip Wasmtime GitHub notifications bot (Sep 23 2022 at 16:41):

jameysharp merged PR #4939.

Last updated: Dec 23 2024 at 12:05 UTC