egraphs-good / extraction-gym

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

Clean up as well as speed up the ILP extractor. #15

Closed TrevorHansen closed 11 months ago

TrevorHansen commented 11 months ago

The ILP extractor is really bad. It's more than 100 times slower than the bottom_up extractor and produces results that are only about 60% as good as it. This patch is a start to addressing the problem. It improves the encoding sent to coin-or cbc and makes the logic clearer.

It's now about 30% faster and produces nearly the same results as previously.

Previously:

cumulative time for bottom_up: 3209ms
cumulative time for ilp_cbc: 402724ms
bottom_up / ilp_cbc
geo mean
tree: 0.5667
dag: 0.6615
micros: 0.0131
quantiles
tree:   0.0605, 0.4844, 0.5313, 0.6642, 1.0000
dag:    0.0976, 0.5708, 0.6330, 0.7702, 1.2106
micros: 0.0001, 0.0093, 0.0157, 0.0214, 0.1406

Now:

cumulative time for bottom-up: 3194ms
cumulative time for ilp_cbc: 283199ms
bottom-up / ilp_cbc
geo mean
tree: 0.5734
dag: 0.6673
micros: 0.0208
quantiles
tree:   0.0604, 0.4878, 0.5394, 0.6740, 1.0000
dag:    0.0976, 0.5751, 0.6366, 0.7717, 1.2106
micros: 0.0001, 0.0142, 0.0238, 0.0348, 0.1298
mwillsey commented 11 months ago

I agree, the ILP extractor needs a lot of work. Thanks for the PR.