E-Matching Non-Canonical Nodes
- 主要言語
- Haskell
- スター
- 98
- フォーク
- 17
- PR マージ指標
- 30日以内にマージされた PR はありません
説明
I have been playing with alternative e-matching implementations and tried comparing my versions with the existing matching. Largely the differences are fairly minor, but dumping all rule triggers for the test suite showed some interesting differences:
- Currently the E-Matching builds a database from the hashcons structure. In test/Sym.hs the analysis removes other E-Nodes if their E-Class has a constant representation, but the hashcons still contains those E-Nodes so the rules still trigger on them
- Neither the hashcons structure nor the class node-lists are canonicalized/deduplicated. Afaict the only time the E-Graph deduplicates is when nodes are reinserted because a child class merged, and only if the reinserts happen during the same worklist step.
- E-Matching can multiply these duplicates out. This doesn't affect performance, but mostly because the scheduler counts these duplicates as extra matches and blocks the affected rules earlier.
Not sure if those are critical issues, but the scheduler blocking extra rules makes performance comparisons tricky. And disabling the scheduler seems to cause occasional exponential slowdowns for the existing genericJoin, I haven't figured out if its something about the join algorithm or if the duplicates actually cause exponentially more results.
コントリビューションガイド
このリポジトリのコントリビューションガイドは索引されていません
評価
この issue はまだ評価されていません。