Wasmtime GitHub notifications bot (Jun 22 2023 at 01:55): Wasmtime GitHub notifications bot (Jun 22 2023 at 01:55):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.
Wasmtime GitHub notifications bot (Jun 22 2023 at 01:55):sofia-snow requested fitzgen for a review on PR #6622.
Wasmtime GitHub notifications bot (Jun 22 2023 at 01:55):sofia-snow requested wasmtime-compiler-reviewers for a review on PR #6622.
Wasmtime GitHub notifications bot (Jun 22 2023 at 06:01):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
unionbelow 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.
Wasmtime GitHub notifications bot (Jun 22 2023 at 06:41):jameysharp merged PR #6622.
Last updated: Oct 23 2024 at 20:03 UTC