Stream: git-wasmtime

Topic: wasmtime / PR #8473 Isle sets and hash

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 12:44):

KGrewal1 opened PR #8473 from KGrewal1:isle-sets_and_hash to bytecodealliance:main:

Main aim of this change was to change the behaviour of DisjointSet to early return as opposed to panic when passed x==y and to somewhat gain familiarity myself with the code

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 12:44):

KGrewal1 requested abrown for a review on PR #8473.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 12:44):

KGrewal1 requested wasmtime-compiler-reviewers for a review on PR #8473.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 14:45):

github-actions[bot] commented on PR #8473:

Subscribe to Label Action

cc @cfallin, @fitzgen

<details>
This issue or pull request has been labeled: "cranelift", "isle"

Thus the following users have been cc'd because of the following labels:

To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.

Learn more.
</details>

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 21:31):

abrown submitted PR review:

Overall this change makes sense to me (minus the dropped assertion) but I will defer to @jameysharp who's more recently touched this code.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 21:31):

abrown submitted PR review:

Overall this change makes sense to me (minus the dropped assertion) but I will defer to @jameysharp who's more recently touched this code.

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 21:31):

abrown created PR review comment:

Not sure about this...

view this post on Zulip Wasmtime GitHub notifications bot (Apr 25 2024 at 22:24):

jameysharp commented on PR #8473:

I want to say first of all that this shows that you've dug into the ISLE implementation pretty deeply and that's awesome. Thanks for working to understand it!

I think these changes are interesting, and although I'm leaning toward not taking these changes, I think the reasons for that are also interesting.

The two changes to use StableMap instead of HashMap both require peeking under the covers to get at the underlying HashMap to iterate over it, which of course is the one thing that StableMap is not supposed to allow. In both cases, the reason we're okay with the unstable iteration order is that we sort the results immediately afterward, making the result deterministic.

In RuleSet::build, the HashMap is used very briefly so it's easy to see that the result is deterministic, and there's a big comment pointing this out. I'm inclined to let that continue to just use a raw HashMap.

In DisjointSets, the HashMap is used a lot of different ways, so yes, it might be nice to use StableMap instead to make it clear that the results can't depend on order. But it's not easy to design a map API that is efficient, stable, and meets the needs of DisjointSets: for example, we could provide a StableMap::keys method that returns a sorted Vec of keys, but that takes time O(n log n) in the total size of the map, which I'd prefer to avoid. So I'm inclined to require instead that DisjointSets must produce deterministic results but it can continue to use non-deterministic implementations internally. It's not very big, so checking this isn't hard.

Finally: replacing assert_ne!(x, y) with an early-return clearly won't change any current behavior, since the early return would only happen when we currently panic, and we're not seeing ISLE panic there. So in that sense it's okay to make that change. It's also okay in the sense that it doesn't violate any data structure invariants. It preserves the current property that there are no singleton sets, which is useful for trie_again.

However, I would be surprised if there were a situation where it was convenient to silently ignore attempts to merge a binding with itself. If you find such a situation, let's talk about it! Otherwise I'd prefer to be explicit where merge is called, like in add_match_equal where there's an if statement checking this and a comment explaining what it means if it happens.

I see one thing this PRs highlights that you could help with, though: The StableMap and DisjointSets guarantees don't mean much if everything else can just reach into their private fields and bypass their carefully-constructed APIs. We should move these types into new modules so that Rust's visibility rules will ensure that the rest of the ISLE compiler can't use them incorrectly. Would you like to do that?

view this post on Zulip Wasmtime GitHub notifications bot (Apr 26 2024 at 08:25):

KGrewal1 commented on PR #8473:

Thanks for looking through this: I will try looking at moving stable map and stable set to different modules so the inner maps are made private by the compiler!

view this post on Zulip Wasmtime GitHub notifications bot (Apr 26 2024 at 08:25):

KGrewal1 closed without merge PR #8473.

Last updated: Nov 22 2024 at 16:03 UTC