search

egraphs-good / extraction-gym

benchmarking e-graph extraction
MIT License
24 stars 15 forks source link

Greedy DAG extraction. #5

Closed ezrosent closed 1 year ago

ezrosent commented 1 year ago

This algorithm is the same as "bottom-up" but incremental estimates of cost only count nodes in the solution set once.

It does this by keeping track of the entirety of these incremental solutions in a persistent set data-structure: essentially a HAMT with PATRICIA-style unions and support for incrementally computed aggregations (in this case, costs).

The diff is large because it includes a full sub-crate implementing this set data-structure (which I had laying around a dev branch for egglog). The interfaces aren't at the stage where I'd want to publish it on its own, so adding it here seemed like the best option. Let me know if I should nest it under a subcrates subdirectory though.

mwillsey commented 1 year ago

Closing this for now in favor the simplified version I pushed already in 95e8a74be6d47314af927262c0550faddcdf88ba