Avatar for the egraphs-good user
egraphs-good
egglog
BlogDocsChangelog

Add multisets

#446Merged
Comparing
saulshanabrook:multiset
(
0042f72
) with
main
(
b9f4c58
)
CodSpeed Performance Gauge
0%
Improvements
0
Regressions
0
Untouched
8
New
0
Dropped
0
Ignored
83

Benchmarks

Passed

lambda
benches/example_benchmarks.rs::benches::criterion_benchmark::lambda
CodSpeed Performance Gauge
0%
145 ms
145.2 ms
python_array_optimize
benches/example_benchmarks.rs::benches::criterion_benchmark::python_array_optimize
CodSpeed Performance Gauge
0%
6.2 s
6.2 s
eggcc-extraction
benches/example_benchmarks.rs::benches::criterion_benchmark::eggcc-extraction
CodSpeed Performance Gauge
0%
4.3 s
4.3 s
typeinfer
benches/example_benchmarks.rs::benches::criterion_benchmark::typeinfer
CodSpeed Performance Gauge
0%
402.9 ms
403.6 ms
cykjson
benches/example_benchmarks.rs::benches::criterion_benchmark::cykjson
CodSpeed Performance Gauge
0%
342.9 ms
343.6 ms
math-microbenchmark
benches/example_benchmarks.rs::benches::criterion_benchmark::math-microbenchmark
CodSpeed Performance Gauge
0%
4.1 s
4.1 s
stresstest_large_expr
benches/example_benchmarks.rs::benches::criterion_benchmark::stresstest_large_expr
CodSpeed Performance Gauge
0%
2.8 s
2.8 s
herbie
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie
CodSpeed Performance Gauge
0%
283.2 ms
284.3 ms

Ignored

antiunifyIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::antiunify
CodSpeed Performance Gauge
0%
2.1 ms
2.1 ms
arrayIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::array
CodSpeed Performance Gauge
-1%
26.3 ms
26.4 ms
bddIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bdd
CodSpeed Performance Gauge
0%
15.1 ms
15.2 ms
before-proofsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::before-proofs
CodSpeed Performance Gauge
0%
1.6 ms
1.6 ms
birewriteIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::birewrite
CodSpeed Performance Gauge
0%
1.3 ms
1.3 ms
bitwiseIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bitwise
CodSpeed Performance Gauge
-1%
672 µs
676 µs
boolIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bool
CodSpeed Performance Gauge
0%
1.4 ms
1.4 ms
calcIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::calc
CodSpeed Performance Gauge
0%
5.4 ms
5.4 ms
combinatorsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::combinators
CodSpeed Performance Gauge
0%
18.2 ms
18.2 ms
combined-nestedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::combined-nested
CodSpeed Performance Gauge
0%
1 ms
1 ms
container-rebuildIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::container-rebuild
CodSpeed Performance Gauge
0%
2 ms
2 ms
cykIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::cyk
CodSpeed Performance Gauge
0%
11.2 ms
11.2 ms
datatypesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::datatypes
CodSpeed Performance Gauge
+6%
580.8 µs
547.8 µs
deleteIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::delete
CodSpeed Performance Gauge
+4%
629.9 µs
603.7 µs
eqsat-basicIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic
CodSpeed Performance Gauge
-1%
1.6 ms
1.6 ms
eqsat-basic-multisetIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic-multiset
CodSpeed Performance Gauge
N/A
N/A
4 ms
eqsolveIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsolve
CodSpeed Performance Gauge
+1%
30.9 ms
30.7 ms
f64Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::f64
CodSpeed Performance Gauge
-1%
931.7 µs
936.6 µs
fail_wrong_assertionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fail_wrong_assertion
CodSpeed Performance Gauge
-1%
1.2 ms
1.3 ms
fibonacciIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci
CodSpeed Performance Gauge
0%
1.6 ms
1.6 ms
fibonacci-demandIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci-demand
CodSpeed Performance Gauge
-3%
2.1 ms
2.2 ms
fusionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fusion
CodSpeed Performance Gauge
+1%
43.8 ms
43.2 ms
herbie-tutorialIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie-tutorial
CodSpeed Performance Gauge
+1%
12.5 ms
12.4 ms
i64Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::i64
CodSpeed Performance Gauge
0%
351.4 µs
351.8 µs
includeIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::include
CodSpeed Performance Gauge
-1%
1.2 ms
1.2 ms
integer_mathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::integer_math
CodSpeed Performance Gauge
0%
12.1 ms
12.1 ms
intersectionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::intersection
CodSpeed Performance Gauge
0%
1.9 ms
1.9 ms
intervalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::interval
CodSpeed Performance Gauge
0%
2.7 ms
2.7 ms
knapsackIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::knapsack
CodSpeed Performance Gauge
-1%
5.7 ms
5.8 ms
levenshtein-distanceIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::levenshtein-distance
CodSpeed Performance Gauge
-1%
15.1 ms
15.3 ms
listIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::list
CodSpeed Performance Gauge
+1%
4.8 ms
4.8 ms
mapIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::map
CodSpeed Performance Gauge
-1%
653.7 µs
657.4 µs
mathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::math
CodSpeed Performance Gauge
0%
35.9 ms
36 ms
matrixIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::matrix
CodSpeed Performance Gauge
+2%
11.6 ms
11.3 ms
merge-during-rebuildIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-during-rebuild
CodSpeed Performance Gauge
0%
1 ms
1 ms
merge-saturatesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-saturates
CodSpeed Performance Gauge
0%
3 ms
3 ms
multisetIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::multiset
CodSpeed Performance Gauge
N/A
N/A
2.3 ms
name-resolutionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::name-resolution
CodSpeed Performance Gauge
+2%
1.2 ms
1.1 ms
pathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::path
CodSpeed Performance Gauge
+1%
1 ms
1 ms
path-unionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::path-union
CodSpeed Performance Gauge
0%
1.1 ms
1.1 ms
pathproofIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::pathproof
CodSpeed Performance Gauge
0%
1.5 ms
1.5 ms
points-toIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::points-to
CodSpeed Performance Gauge
+1%
2 ms
2 ms
primitivesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::primitives
CodSpeed Performance Gauge
+2%
531.3 µs
523.3 µs
primsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::prims
CodSpeed Performance Gauge
+1%
5.4 ms
5.4 ms
push-popIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::push-pop
CodSpeed Performance Gauge
0%
645.4 µs
648.1 µs
rationalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::rational
CodSpeed Performance Gauge
-1%
906.5 µs
911.6 µs
repro-defineIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-define
CodSpeed Performance Gauge
0%
713.9 µs
712.8 µs
repro-desugar-143Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-desugar-143
CodSpeed Performance Gauge
0%
8.3 ms
8.3 ms
repro-empty-queryIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-empty-query
CodSpeed Performance Gauge
-1%
626.8 µs
634.3 µs
repro-equal-constantIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant
CodSpeed Performance Gauge
0%
683 µs
680.7 µs
repro-equal-constant2Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant2
CodSpeed Performance Gauge
-1%
661.6 µs
665 µs
repro-noteqbugIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-noteqbug
CodSpeed Performance Gauge
0%
754.9 µs
754.1 µs
repro-primitive-queryIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-primitive-query
CodSpeed Performance Gauge
+1%
701.5 µs
696.2 µs
repro-querybugIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug
CodSpeed Performance Gauge
0%
954.9 µs
955.4 µs
repro-querybug2Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug2
CodSpeed Performance Gauge
-1%
669.8 µs
676.8 µs
repro-querybug3Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug3
CodSpeed Performance Gauge
0%
2.1 ms
2.1 ms
repro-querybug4Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug4
CodSpeed Performance Gauge
-1%
720.3 µs
726.2 µs
repro-should-saturateIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-should-saturate
CodSpeed Performance Gauge
0%
659.4 µs
660.9 µs
repro-silly-panicIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-silly-panic
CodSpeed Performance Gauge
0%
935.3 µs
932.8 µs
repro-typechecking-scheduleIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-typechecking-schedule
CodSpeed Performance Gauge
0%
469.1 µs
470.6 µs
repro-unsoundIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound
CodSpeed Performance Gauge
0%
265.7 ms
266.7 ms
repro-unsound-htutorialIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound-htutorial
CodSpeed Performance Gauge
0%
867 µs
867.1 µs
repro-vec-unequalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-vec-unequal
CodSpeed Performance Gauge
0%
783.1 µs
784 µs
resolutionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::resolution
CodSpeed Performance Gauge
0%
4.3 ms
4.3 ms
rw-analysisIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::rw-analysis
CodSpeed Performance Gauge
0%
39.8 ms
40 ms
schedule-demoIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::schedule-demo
CodSpeed Performance Gauge
0%
2.2 ms
2.2 ms
semi_naive_set_functionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::semi_naive_set_function
CodSpeed Performance Gauge
+1%
37.9 ms
37.7 ms
setIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::set
CodSpeed Performance Gauge
0%
2.8 ms
2.8 ms
stratifiedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::stratified
CodSpeed Performance Gauge
0%
964.6 µs
961 µs
stringIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::string
CodSpeed Performance Gauge
+1%
553.5 µs
547.6 µs
string_quotesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::string_quotes
CodSpeed Performance Gauge
0%
483.4 µs
485.5 µs
subsumeIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::subsume
CodSpeed Performance Gauge
0%
1.6 ms
1.6 ms
test-combinedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined
CodSpeed Performance Gauge
0%
1.3 ms
1.3 ms
test-combined-stepsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined-steps
CodSpeed Performance Gauge
0%
2.9 ms
2.9 ms
towers-of-hanoiIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::towers-of-hanoi
CodSpeed Performance Gauge
0%
5.5 ms
5.5 ms
tricky-type-checkingIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::tricky-type-checking
CodSpeed Performance Gauge
0%
12.1 ms
12.1 ms
type-constraints-testsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::type-constraints-tests
CodSpeed Performance Gauge
-1%
597 µs
601.9 µs
typecheckIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::typecheck
CodSpeed Performance Gauge
0%
6 ms
6 ms
unification-points-toIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unification-points-to
CodSpeed Performance Gauge
0%
8.4 ms
8.5 ms
unifyIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unify
CodSpeed Performance Gauge
0%
1.1 ms
1.1 ms
unstable-fnIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unstable-fn
CodSpeed Performance Gauge
0%
6.3 ms
6.3 ms
untilIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::until
CodSpeed Performance Gauge
0%
2.8 ms
2.8 ms
vecIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::vec
CodSpeed Performance Gauge
0%
1 ms
1 ms

Commits

Click on a commit to change the comparison range
Base
main
b9f4c58
-9%
Add multisets 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](https://egraphs.zulipchat.com/#narrow/channel/328972-general/topic/Reducing.20node.20explosion.20through.20algebraic.20representations.3F) [threads](https://egraphs.zulipchat.com/#narrow/channel/328972-general/topic/Linear.20and.20Polynomial.20Equations) on zulip for some more background.
23cfd61
9 months ago
by saulshanabrook
-1%
Combine multiset files
b6fb41c
9 months ago
by saulshanabrook
+10%
Switch to im from rpds
b987f89
9 months ago
by saulshanabrook
0%
Cache length of multiset
f090848
9 months ago
by saulshanabrook
0%
Merge branch 'main' into multiset
0042f72
9 months ago
by saulshanabrook
© 2025 CodSpeed Technology
Home Terms Privacy Docs