sofia-snow opened PR #6622 from sofia-snow:patch-1
to bytecodealliance:main
:
Corrected the comment from "path splitting" to "path halving" to align with the implementation.
Path halving only updates every second node, whereas path splitting updates every node along the path. Regardless, their average performance tends to be negligible. Don't need to change the code to implement splitting instead.
sofia-snow requested fitzgen for a review on PR #6622.
sofia-snow requested wasmtime-compiler-reviewers for a review on PR #6622.
jameysharp submitted PR review:
The distinction between the splitting and halving approaches is subtle so I had to think about the implementation carefully to check this PR. And I think you're right! Thanks for noticing this.
If you're looking at this union-find implementation, you may be interested to note that the definition of
union
below is non-standard, neither by-size nor by-rank, so the usual asymptotic complexity analysis doesn't apply. Issue #6126 is related: we kind of rely on this non-standard definition to support efficient hash-consing, but even this definition doesn't quite guarantee that we'll find all duplicate values reliably. You might find that issue interesting to look into. We're currently ignoring it because the results right now seem to be good enough, but I'd be happier if we had a more standard approach here.
jameysharp merged PR #6622.
Last updated: Dec 23 2024 at 12:05 UTC