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
KGrewal1 requested abrown for a review on PR #8473.
KGrewal1 requested wasmtime-compiler-reviewers for a review on PR #8473.
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:
- cfallin: isle
- fitzgen: isle
To subscribe or unsubscribe from this label, edit the <code>.github/subscribe-to-label.json</code> configuration file.
Learn more.
</details>
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.
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.
abrown created PR review comment:
Not sure about this...
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 ofHashMap
both require peeking under the covers to get at the underlyingHashMap
to iterate over it, which of course is the one thing thatStableMap
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
, theHashMap
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 rawHashMap
.In
DisjointSets
, theHashMap
is used a lot of different ways, so yes, it might be nice to useStableMap
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 ofDisjointSets
: for example, we could provide aStableMap::keys
method that returns a sortedVec
of keys, but that takes timeO(n log n)
in the total size of the map, which I'd prefer to avoid. So I'm inclined to require instead thatDisjointSets
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 fortrie_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 inadd_match_equal
where there's anif
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
andDisjointSets
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?
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!
KGrewal1 closed without merge PR #8473.
Last updated: Dec 23 2024 at 12:05 UTC