Optimize extraction algorithm using worklist, enabling medium-sized benchmarks

egraphs-good / eggcc

MIT License

51 stars 11 forks source link

Optimize extraction algorithm using worklist, enabling medium-sized benchmarks #479

Closed oflatt closed 6 months ago

oflatt commented 6 months ago

This PR optimizes the extraction algorithm to scale to medium-sized benchmarks. It uses a parent table, similar to extraction algorithms in the extraction-gym

yihozhang commented 6 months ago

Also, we don't really need to distinguish root_id for the first extraction pass. After the whole algorithm is merged we should refactor this so that the first pass does not distinguish between the same nodes under different regions.