Stream: git-wasmtime

Topic: wasmtime / issue #4902 ISLE: merge trie edges across prio...

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

github-actions[bot] commented on issue #4902:

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 (Sep 14 2022 at 18:25):

cfallin commented on issue #4902:

Updated, thanks!

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

elliottt commented on issue #4902:

Does this comment need to be clarified after merging this PR?
https://github.com/bytecodealliance/wasmtime/blob/562bb25360a2f366a482e15fc148bab7267a9266/cranelift/isle/isle/src/trie.rs#L102-L111

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

cfallin commented on issue #4902:

Does this comment need to be clarified after merging this PR?

Indeed, just updated; thanks!

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

jameysharp commented on issue #4902:

I don't understand how this trie construction works, so this question may be nonsense, but is all this frontier machinery necessary? It looks to me like this PR is equivalent to inserting into a list that's sorted by (Reverse<Prio>, TrieSymbol).

Here's a patch on top of 18be532c2b9b9baab654b643c2e27c135c9df673 that I think should be equivalent, using a BTreeMap to maintain the sort order. I haven't tried running it because I should have left work an hour or two ago, but I did verify that it builds without warnings.

trie-btree.txt

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

cfallin commented on issue #4902:

It looks to me like this PR is equivalent to inserting into a list that's sorted by (Reverse<Prio>, TrieSymbol).

Not quite, unfortunately: the subtle difference is in the ability to merge across priorities. The scheme your patch introduces, with edges that are labeled by priorities, is more or less what this PR is replacing. The key invariant that makes this PR work is that edges are not labeled by priority, and rules of different priorities are allowed to share an edge, but we limit the overlap to maintain priority ordering (the frontier).

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

cfallin commented on issue #4902:

@elliottt and I discussed this a bit further this morning and given concerns about the potential reordering before we are fully overlap-checker-clean, we agree it probably makes sense to wait to optimize using the additional reordering flexibility until later. So I'll go ahead and close this PR for now.

Last updated: Nov 22 2024 at 16:03 UTC