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

Add multisets

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

Benchmarks

Passed

lambda
benches/example_benchmarks.rs::benches::criterion_benchmark::lambda
CodSpeed Performance Gauge
0%
145 ms145.2 ms
python_array_optimize
benches/example_benchmarks.rs::benches::criterion_benchmark::python_array_optimize
CodSpeed Performance Gauge
0%
6.2 s6.2 s
eggcc-extraction
benches/example_benchmarks.rs::benches::criterion_benchmark::eggcc-extraction
CodSpeed Performance Gauge
0%
4.3 s4.3 s
typeinfer
benches/example_benchmarks.rs::benches::criterion_benchmark::typeinfer
CodSpeed Performance Gauge
0%
402.9 ms403.6 ms
cykjson
benches/example_benchmarks.rs::benches::criterion_benchmark::cykjson
CodSpeed Performance Gauge
0%
342.9 ms343.6 ms
math-microbenchmark
benches/example_benchmarks.rs::benches::criterion_benchmark::math-microbenchmark
CodSpeed Performance Gauge
0%
4.1 s4.1 s
stresstest_large_expr
benches/example_benchmarks.rs::benches::criterion_benchmark::stresstest_large_expr
CodSpeed Performance Gauge
0%
2.8 s2.8 s
herbie
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie
CodSpeed Performance Gauge
0%
283.2 ms284.3 ms

Ignored

birewrite
benches/example_benchmarks.rs::benches::criterion_benchmark::birewrite
Ignored
CodSpeed Performance Gauge
0%
1.3 ms1.3 ms
bool
benches/example_benchmarks.rs::benches::criterion_benchmark::bool
Ignored
CodSpeed Performance Gauge
0%
1.4 ms1.4 ms
prims
benches/example_benchmarks.rs::benches::criterion_benchmark::prims
Ignored
CodSpeed Performance Gauge
+1%
5.4 ms5.4 ms
push-pop
benches/example_benchmarks.rs::benches::criterion_benchmark::push-pop
Ignored
CodSpeed Performance Gauge
0%
645.4 µs648.1 µs
bitwise
benches/example_benchmarks.rs::benches::criterion_benchmark::bitwise
Ignored
CodSpeed Performance Gauge
-1%
672 µs676 µs
array
benches/example_benchmarks.rs::benches::criterion_benchmark::array
Ignored
CodSpeed Performance Gauge
-1%
26.3 ms26.4 ms
rational
benches/example_benchmarks.rs::benches::criterion_benchmark::rational
Ignored
CodSpeed Performance Gauge
-1%
906.5 µs911.6 µs
bdd
benches/example_benchmarks.rs::benches::criterion_benchmark::bdd
Ignored
CodSpeed Performance Gauge
0%
15.1 ms15.2 ms
repro-equal-constant2
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant2
Ignored
CodSpeed Performance Gauge
-1%
661.6 µs665 µs
repro-desugar-143
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-desugar-143
Ignored
CodSpeed Performance Gauge
0%
8.3 ms8.3 ms
repro-noteqbug
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-noteqbug
Ignored
CodSpeed Performance Gauge
0%
754.9 µs754.1 µs
repro-define
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-define
Ignored
CodSpeed Performance Gauge
0%
713.9 µs712.8 µs
repro-querybug
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug
Ignored
CodSpeed Performance Gauge
0%
954.9 µs955.4 µs
repro-equal-constant
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant
Ignored
CodSpeed Performance Gauge
0%
683 µs680.7 µs
calc
benches/example_benchmarks.rs::benches::criterion_benchmark::calc
Ignored
CodSpeed Performance Gauge
0%
5.4 ms5.4 ms
before-proofs
benches/example_benchmarks.rs::benches::criterion_benchmark::before-proofs
Ignored
CodSpeed Performance Gauge
0%
1.6 ms1.6 ms
cyk
benches/example_benchmarks.rs::benches::criterion_benchmark::cyk
Ignored
CodSpeed Performance Gauge
0%
11.2 ms11.2 ms
repro-querybug2
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug2
Ignored
CodSpeed Performance Gauge
-1%
669.8 µs676.8 µs
repro-querybug4
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug4
Ignored
CodSpeed Performance Gauge
-1%
720.3 µs726.2 µs
repro-should-saturate
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-should-saturate
Ignored
CodSpeed Performance Gauge
0%
659.4 µs660.9 µs
repro-empty-query
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-empty-query
Ignored
CodSpeed Performance Gauge
-1%
626.8 µs634.3 µs
combined-nested
benches/example_benchmarks.rs::benches::criterion_benchmark::combined-nested
Ignored
CodSpeed Performance Gauge
0%
1 ms1 ms
repro-primitive-query
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-primitive-query
Ignored
CodSpeed Performance Gauge
+1%
701.5 µs696.2 µs
container-rebuild
benches/example_benchmarks.rs::benches::criterion_benchmark::container-rebuild
Ignored
CodSpeed Performance Gauge
0%
2 ms2 ms
repro-typechecking-schedule
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-typechecking-schedule
Ignored
CodSpeed Performance Gauge
0%
469.1 µs470.6 µs
repro-unsound-htutorial
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound-htutorial
Ignored
CodSpeed Performance Gauge
0%
867 µs867.1 µs
antiunify
benches/example_benchmarks.rs::benches::criterion_benchmark::antiunify
Ignored
CodSpeed Performance Gauge
0%
2.1 ms2.1 ms
string
benches/example_benchmarks.rs::benches::criterion_benchmark::string
Ignored
CodSpeed Performance Gauge
+1%
553.5 µs547.6 µs
repro-querybug3
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug3
Ignored
CodSpeed Performance Gauge
0%
2.1 ms2.1 ms
combinators
benches/example_benchmarks.rs::benches::criterion_benchmark::combinators
Ignored
CodSpeed Performance Gauge
0%
18.2 ms18.2 ms
delete
benches/example_benchmarks.rs::benches::criterion_benchmark::delete
Ignored
CodSpeed Performance Gauge
+4%
629.9 µs603.7 µs
subsume
benches/example_benchmarks.rs::benches::criterion_benchmark::subsume
Ignored
CodSpeed Performance Gauge
0%
1.6 ms1.6 ms
stratified
benches/example_benchmarks.rs::benches::criterion_benchmark::stratified
Ignored
CodSpeed Performance Gauge
0%
964.6 µs961 µs
test-combined
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined
Ignored
CodSpeed Performance Gauge
0%
1.3 ms1.3 ms
rw-analysis
benches/example_benchmarks.rs::benches::criterion_benchmark::rw-analysis
Ignored
CodSpeed Performance Gauge
0%
39.8 ms40 ms
repro-silly-panic
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-silly-panic
Ignored
CodSpeed Performance Gauge
0%
935.3 µs932.8 µs
repro-vec-unequal
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-vec-unequal
Ignored
CodSpeed Performance Gauge
0%
783.1 µs784 µs
repro-unsound
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound
Ignored
CodSpeed Performance Gauge
0%
265.7 ms266.7 ms
set
benches/example_benchmarks.rs::benches::criterion_benchmark::set
Ignored
CodSpeed Performance Gauge
0%
2.8 ms2.8 ms
resolution
benches/example_benchmarks.rs::benches::criterion_benchmark::resolution
Ignored
CodSpeed Performance Gauge
0%
4.3 ms4.3 ms
datatypes
benches/example_benchmarks.rs::benches::criterion_benchmark::datatypes
Ignored
CodSpeed Performance Gauge
+6%
580.8 µs547.8 µs
schedule-demo
benches/example_benchmarks.rs::benches::criterion_benchmark::schedule-demo
Ignored
CodSpeed Performance Gauge
0%
2.2 ms2.2 ms
tricky-type-checking
benches/example_benchmarks.rs::benches::criterion_benchmark::tricky-type-checking
Ignored
CodSpeed Performance Gauge
0%
12.1 ms12.1 ms
semi_naive_set_function
benches/example_benchmarks.rs::benches::criterion_benchmark::semi_naive_set_function
Ignored
CodSpeed Performance Gauge
+1%
37.9 ms37.7 ms
typecheck
benches/example_benchmarks.rs::benches::criterion_benchmark::typecheck
Ignored
CodSpeed Performance Gauge
0%
6 ms6 ms
string_quotes
benches/example_benchmarks.rs::benches::criterion_benchmark::string_quotes
Ignored
CodSpeed Performance Gauge
0%
483.4 µs485.5 µs
eqsolve
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsolve
Ignored
CodSpeed Performance Gauge
+1%
30.9 ms30.7 ms
test-combined-steps
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined-steps
Ignored
CodSpeed Performance Gauge
0%
2.9 ms2.9 ms
unification-points-to
benches/example_benchmarks.rs::benches::criterion_benchmark::unification-points-to
Ignored
CodSpeed Performance Gauge
0%
8.4 ms8.5 ms
f64
benches/example_benchmarks.rs::benches::criterion_benchmark::f64
Ignored
CodSpeed Performance Gauge
-1%
931.7 µs936.6 µs
type-constraints-tests
benches/example_benchmarks.rs::benches::criterion_benchmark::type-constraints-tests
Ignored
CodSpeed Performance Gauge
-1%
597 µs601.9 µs
fusion
benches/example_benchmarks.rs::benches::criterion_benchmark::fusion
Ignored
CodSpeed Performance Gauge
+1%
43.8 ms43.2 ms
until
benches/example_benchmarks.rs::benches::criterion_benchmark::until
Ignored
CodSpeed Performance Gauge
0%
2.8 ms2.8 ms
eqsat-basic
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic
Ignored
CodSpeed Performance Gauge
-1%
1.6 ms1.6 ms
intersection
benches/example_benchmarks.rs::benches::criterion_benchmark::intersection
Ignored
CodSpeed Performance Gauge
0%
1.9 ms1.9 ms
i64
benches/example_benchmarks.rs::benches::criterion_benchmark::i64
Ignored
CodSpeed Performance Gauge
0%
351.4 µs351.8 µs
merge-during-rebuild
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-during-rebuild
Ignored
CodSpeed Performance Gauge
0%
1 ms1 ms
eqsat-basic-multiset
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic-multiset
Ignored
CodSpeed Performance Gauge
N/A
N/A4 ms
interval
benches/example_benchmarks.rs::benches::criterion_benchmark::interval
Ignored
CodSpeed Performance Gauge
0%
2.7 ms2.7 ms
vec
benches/example_benchmarks.rs::benches::criterion_benchmark::vec
Ignored
CodSpeed Performance Gauge
0%
1 ms1 ms
include
benches/example_benchmarks.rs::benches::criterion_benchmark::include
Ignored
CodSpeed Performance Gauge
-1%
1.2 ms1.2 ms
unstable-fn
benches/example_benchmarks.rs::benches::criterion_benchmark::unstable-fn
Ignored
CodSpeed Performance Gauge
0%
6.3 ms6.3 ms
map
benches/example_benchmarks.rs::benches::criterion_benchmark::map
Ignored
CodSpeed Performance Gauge
-1%
653.7 µs657.4 µs
unify
benches/example_benchmarks.rs::benches::criterion_benchmark::unify
Ignored
CodSpeed Performance Gauge
0%
1.1 ms1.1 ms
towers-of-hanoi
benches/example_benchmarks.rs::benches::criterion_benchmark::towers-of-hanoi
Ignored
CodSpeed Performance Gauge
0%
5.5 ms5.5 ms
fibonacci
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci
Ignored
CodSpeed Performance Gauge
0%
1.6 ms1.6 ms
herbie-tutorial
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie-tutorial
Ignored
CodSpeed Performance Gauge
+1%
12.5 ms12.4 ms
fibonacci-demand
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci-demand
Ignored
CodSpeed Performance Gauge
-3%
2.1 ms2.2 ms
levenshtein-distance
benches/example_benchmarks.rs::benches::criterion_benchmark::levenshtein-distance
Ignored
CodSpeed Performance Gauge
-1%
15.1 ms15.3 ms
list
benches/example_benchmarks.rs::benches::criterion_benchmark::list
Ignored
CodSpeed Performance Gauge
+1%
4.8 ms4.8 ms
integer_math
benches/example_benchmarks.rs::benches::criterion_benchmark::integer_math
Ignored
CodSpeed Performance Gauge
0%
12.1 ms12.1 ms
pathproof
benches/example_benchmarks.rs::benches::criterion_benchmark::pathproof
Ignored
CodSpeed Performance Gauge
0%
1.5 ms1.5 ms
matrix
benches/example_benchmarks.rs::benches::criterion_benchmark::matrix
Ignored
CodSpeed Performance Gauge
+2%
11.6 ms11.3 ms
multiset
benches/example_benchmarks.rs::benches::criterion_benchmark::multiset
Ignored
CodSpeed Performance Gauge
N/A
N/A2.3 ms
path-union
benches/example_benchmarks.rs::benches::criterion_benchmark::path-union
Ignored
CodSpeed Performance Gauge
0%
1.1 ms1.1 ms
path
benches/example_benchmarks.rs::benches::criterion_benchmark::path
Ignored
CodSpeed Performance Gauge
+1%
1 ms1 ms
points-to
benches/example_benchmarks.rs::benches::criterion_benchmark::points-to
Ignored
CodSpeed Performance Gauge
+1%
2 ms2 ms
name-resolution
benches/example_benchmarks.rs::benches::criterion_benchmark::name-resolution
Ignored
CodSpeed Performance Gauge
+2%
1.2 ms1.1 ms
primitives
benches/example_benchmarks.rs::benches::criterion_benchmark::primitives
Ignored
CodSpeed Performance Gauge
+2%
531.3 µs523.3 µs
knapsack
benches/example_benchmarks.rs::benches::criterion_benchmark::knapsack
Ignored
CodSpeed Performance Gauge
-1%
5.7 ms5.8 ms
math
benches/example_benchmarks.rs::benches::criterion_benchmark::math
Ignored
CodSpeed Performance Gauge
0%
35.9 ms36 ms
fail_wrong_assertion
benches/example_benchmarks.rs::benches::criterion_benchmark::fail_wrong_assertion
Ignored
CodSpeed Performance Gauge
-1%
1.2 ms1.3 ms
merge-saturates
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-saturates
Ignored
CodSpeed Performance Gauge
0%
3 ms3 ms

Commits

Click on a commit to change the comparison range
Base
main
b9f4c58
-8.55%
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
11 months ago
by saulshanabrook
-1.37%
Combine multiset files
b6fb41c
11 months ago
by saulshanabrook
+9.68%
Switch to im from rpds
b987f89
11 months ago
by saulshanabrook
+0.07%
Cache length of multiset
f090848
11 months ago
by saulshanabrook
-0.02%
Merge branch 'main' into multiset
0042f72
11 months ago
by saulshanabrook
© 2025 CodSpeed Technology
Home Terms Privacy Docs