search

egraphs-good / egglog

egraphs + datalog!
https://egraphs-good.github.io/egglog/
MIT License
458 stars 54 forks source link

Add multisets #446

Closed saulshanabrook closed 3 weeks ago

saulshanabrook commented 1 month ago

This PR adds a multiset sort. It is based on a data structure that implements functional sharing. Using that sort, an example is added to show how you can use it to express associative & commutative operations like addition in multiplication with multisets, so that their canonical forms don't need to re-encoded for every ordering. See these threads on zulip for some more background.

codspeed-hq[bot] commented 1 month ago

CodSpeed Performance Report

Merging #446 will not alter performance

Comparing saulshanabrook:multiset (0042f72) with main (b9f4c58)

Summary

✅ 8 untouched benchmarks

🆕 2 new benchmarks

Benchmarks breakdown

Benchmark main saulshanabrook:multiset Change
🆕 eqsat-basic-multiset N/A 4 ms N/A
🆕 multiset N/A 2.3 ms N/A
oflatt commented 1 month ago

I'm a little hesitant to add new containers given the churn on the API and the new backend coming soon.

Can this be done in egglog already by using a Map and mapping keys to the number of that element?

yihozhang commented 1 month ago

I'm in favor of merging this after some cleanups (e.g., merge the two multiset.rs files), since this is no worse than the containers and higher-order functions we currently have, and we have not had a clear idea about what will and won't be supported for containers in the future. I especially like the implementation of map of this PR. Let's talk about this in the dev meeting this week!