Stream: git-wasmtime

Topic: wasmtime / issue #3525 ISLE: Sort linearized match ops to...


view this post on Zulip Wasmtime GitHub notifications bot (Nov 15 2021 at 23:41):

fitzgen opened issue #3525:

Originally https://github.com/cfallin/isle/issues/11

<blockquote>

After linearizing rule patterns for a given term, but before we insert those linear match ops into the trie, we should do a custom topological sort of the linear match ops's data-flow graph that seeks to maximize prefix sharing in the eventual trie:

This is greedy algorithm is not optimal, because we don't break ties between equally-emittable operations such that the final trie will have maximal prefix sharing. I can't think of an efficient way to do that right now. But I think this should get us very close to optimal in practice.

</blockquote>

view this post on Zulip Wasmtime GitHub notifications bot (Nov 15 2021 at 23:41):

fitzgen labeled issue #3525:

Originally https://github.com/cfallin/isle/issues/11

<blockquote>

After linearizing rule patterns for a given term, but before we insert those linear match ops into the trie, we should do a custom topological sort of the linear match ops's data-flow graph that seeks to maximize prefix sharing in the eventual trie:

This is greedy algorithm is not optimal, because we don't break ties between equally-emittable operations such that the final trie will have maximal prefix sharing. I can't think of an efficient way to do that right now. But I think this should get us very close to optimal in practice.

</blockquote>

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2023 at 02:42):

jameysharp commented on issue #3525:

I think this is no longer necessary since ISLE doesn't use linearized matches any more. Please re-open if I've misunderstood it though.

view this post on Zulip Wasmtime GitHub notifications bot (Mar 02 2023 at 02:42):

jameysharp closed issue #3525:

Originally https://github.com/cfallin/isle/issues/11

<blockquote>

After linearizing rule patterns for a given term, but before we insert those linear match ops into the trie, we should do a custom topological sort of the linear match ops's data-flow graph that seeks to maximize prefix sharing in the eventual trie:

This is greedy algorithm is not optimal, because we don't break ties between equally-emittable operations such that the final trie will have maximal prefix sharing. I can't think of an efficient way to do that right now. But I think this should get us very close to optimal in practice.

</blockquote>


Last updated: Dec 23 2024 at 13:07 UTC