Wasmtime GitHub notifications bot (Nov 15 2021 at 23:41): 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:
- create a data-flow graph for each pattern
- keep track of "emittable" match operations for each pattern, i.e. those operations whose operands are all already emitted so we can emit this operation if we choose
- count which operations are most emittable across all patterns
- select the operation with the highest count
- for all patterns where this is an emittable operation:
- emit this operation next
- recurse
- for all patterns where that is not an emittable operation:
- choose the operation with the highest count among these remaining patterns
- emit this operation next for these patterns
- recurse
- repeat previous until all patterns have been accounted for
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>
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:
- create a data-flow graph for each pattern
- keep track of "emittable" match operations for each pattern, i.e. those operations whose operands are all already emitted so we can emit this operation if we choose
- count which operations are most emittable across all patterns
- select the operation with the highest count
- for all patterns where this is an emittable operation:
- emit this operation next
- recurse
- for all patterns where that is not an emittable operation:
- choose the operation with the highest count among these remaining patterns
- emit this operation next for these patterns
- recurse
- repeat previous until all patterns have been accounted for
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>
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.
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:
- create a data-flow graph for each pattern
- keep track of "emittable" match operations for each pattern, i.e. those operations whose operands are all already emitted so we can emit this operation if we choose
- count which operations are most emittable across all patterns
- select the operation with the highest count
- for all patterns where this is an emittable operation:
- emit this operation next
- recurse
- for all patterns where that is not an emittable operation:
- choose the operation with the highest count among these remaining patterns
- emit this operation next for these patterns
- recurse
- repeat previous until all patterns have been accounted for
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: Nov 22 2024 at 16:03 UTC