search

egraphs-good / extraction-gym

benchmarking e-graph extraction
MIT License
27 stars 16 forks source link

Global DAG extraction #21

Closed oflatt closed 9 months ago

oflatt commented 10 months ago

This PR adds another greedy DAG extractor which improves the performance of calculating a term's cost. It does this by sharing subterms in a global DAG, and exiting early when doing set unions.

cumulative time for bottom-up: 2474ms
cumulative time for global-greedy-dag: 4239ms
cumulative time for greedy-dag:            35011ms
cumulative dag cost for global-greedy-dag: 76907
cumulative dag cost for greedy-dag:             76907