saulshanabrook:multiset - Branch - egraphs-good/egglog

Blog Docs

Add multisets(#446)

Merged

Comparing

saulshanabrook:multiset

(

0042f72

) with

main

(

b9f4c58

)

IMPROVEMENTS: 0

REGRESSIONS: 0

UNTOUCHED: 8

NEW: 0

DROPPED: 0

IGNORED: 83

Benchmarks

Passed

lambda

benches/example_benchmarks.rs::benches::criterion_benchmark::lambda

145 ms

145.2 ms

python_array_optimize

benches/example_benchmarks.rs::benches::criterion_benchmark::python_array_optimize

6.2 s

eggcc-extraction

benches/example_benchmarks.rs::benches::criterion_benchmark::eggcc-extraction

4.3 s

typeinfer

benches/example_benchmarks.rs::benches::criterion_benchmark::typeinfer

402.9 ms

403.6 ms

cykjson

benches/example_benchmarks.rs::benches::criterion_benchmark::cykjson

342.9 ms

343.6 ms

math-microbenchmark

benches/example_benchmarks.rs::benches::criterion_benchmark::math-microbenchmark

4.1 s

stresstest_large_expr

benches/example_benchmarks.rs::benches::criterion_benchmark::stresstest_large_expr

2.8 s

herbie

benches/example_benchmarks.rs::benches::criterion_benchmark::herbie

283.2 ms

284.3 ms

Ignored

antiunifyIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::antiunify

2.1 ms

arrayIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::array

-1%

26.3 ms

26.4 ms

bddIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::bdd

15.1 ms

15.2 ms

before-proofsIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::before-proofs

1.6 ms

birewriteIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::birewrite

1.3 ms

bitwiseIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::bitwise

-1%

672 µs

676 µs

boolIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::bool

1.4 ms

calcIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::calc

5.4 ms

combinatorsIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::combinators

18.2 ms

combined-nestedIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::combined-nested

1 ms

container-rebuildIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::container-rebuild

2 ms

cykIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::cyk

11.2 ms

datatypesIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::datatypes

+6%

580.8 µs

547.8 µs

deleteIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::delete

+4%

629.9 µs

603.7 µs

eqsat-basicIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic

-1%

1.6 ms

eqsat-basic-multisetIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic-multiset

N/A

4 ms

eqsolveIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::eqsolve

+1%

30.9 ms

30.7 ms

f64Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::f64

-1%

931.7 µs

936.6 µs

fail_wrong_assertionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::fail_wrong_assertion

-1%

1.2 ms

1.3 ms

fibonacciIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci

1.6 ms

fibonacci-demandIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci-demand

-3%

2.1 ms

2.2 ms

fusionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::fusion

+1%

43.8 ms

43.2 ms

herbie-tutorialIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::herbie-tutorial

+1%

12.5 ms

12.4 ms

i64Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::i64

351.4 µs

351.8 µs

includeIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::include

-1%

1.2 ms

integer_mathIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::integer_math

12.1 ms

intersectionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::intersection

1.9 ms

intervalIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::interval

2.7 ms

knapsackIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::knapsack

-1%

5.7 ms

5.8 ms

levenshtein-distanceIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::levenshtein-distance

-1%

15.1 ms

15.3 ms

listIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::list

+1%

4.8 ms

mapIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::map

-1%

653.7 µs

657.4 µs

mathIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::math

35.9 ms

36 ms

matrixIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::matrix

+2%

11.6 ms

11.3 ms

merge-during-rebuildIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::merge-during-rebuild

1 ms

merge-saturatesIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::merge-saturates

3 ms

multisetIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::multiset

N/A

2.3 ms

name-resolutionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::name-resolution

+2%

1.2 ms

1.1 ms

pathIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::path

+1%

1 ms

path-unionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::path-union

1.1 ms

pathproofIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::pathproof

1.5 ms

points-toIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::points-to

+1%

2 ms

primitivesIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::primitives

+2%

531.3 µs

523.3 µs

primsIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::prims

+1%

5.4 ms

push-popIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::push-pop

645.4 µs

648.1 µs

rationalIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::rational

-1%

906.5 µs

911.6 µs

repro-defineIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-define

713.9 µs

712.8 µs

repro-desugar-143Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-desugar-143

8.3 ms

repro-empty-queryIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-empty-query

-1%

626.8 µs

634.3 µs

repro-equal-constantIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant

683 µs

680.7 µs

repro-equal-constant2Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant2

-1%

661.6 µs

665 µs

repro-noteqbugIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-noteqbug

754.9 µs

754.1 µs

repro-primitive-queryIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-primitive-query

+1%

701.5 µs

696.2 µs

repro-querybugIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug

954.9 µs

955.4 µs

repro-querybug2Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug2

-1%

669.8 µs

676.8 µs

repro-querybug3Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug3

2.1 ms

repro-querybug4Ignored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug4

-1%

720.3 µs

726.2 µs

repro-should-saturateIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-should-saturate

659.4 µs

660.9 µs

repro-silly-panicIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-silly-panic

935.3 µs

932.8 µs

repro-typechecking-scheduleIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-typechecking-schedule

469.1 µs

470.6 µs

repro-unsoundIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound

265.7 ms

266.7 ms

repro-unsound-htutorialIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound-htutorial

867 µs

867.1 µs

repro-vec-unequalIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::repro-vec-unequal

783.1 µs

784 µs

resolutionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::resolution

4.3 ms

rw-analysisIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::rw-analysis

39.8 ms

40 ms

schedule-demoIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::schedule-demo

2.2 ms

semi_naive_set_functionIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::semi_naive_set_function

+1%

37.9 ms

37.7 ms

setIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::set

2.8 ms

stratifiedIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::stratified

964.6 µs

961 µs

stringIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::string

+1%

553.5 µs

547.6 µs

string_quotesIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::string_quotes

483.4 µs

485.5 µs

subsumeIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::subsume

1.6 ms

test-combinedIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined

1.3 ms

test-combined-stepsIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined-steps

2.9 ms

towers-of-hanoiIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::towers-of-hanoi

5.5 ms

tricky-type-checkingIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::tricky-type-checking

12.1 ms

type-constraints-testsIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::type-constraints-tests

-1%

597 µs

601.9 µs

typecheckIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::typecheck

6 ms

unification-points-toIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::unification-points-to

8.4 ms

8.5 ms

unifyIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::unify

1.1 ms

unstable-fnIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::unstable-fn

6.3 ms

untilIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::until

2.8 ms

vecIgnored

benches/example_benchmarks.rs::benches::criterion_benchmark::vec

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

1 month ago

by saulshanabrook

-1%

Combine multiset files

b6fb41c

1 month ago

by saulshanabrook

+10%

Switch to im from rpds

b987f89

1 month ago

by saulshanabrook

Cache length of multiset

f090848

1 month ago

by saulshanabrook

Merge branch 'main' into multiset

0042f72

28 days ago

by saulshanabrook

ResourcesHome Pricing Docs Blog GitHub Changelog

Getting StartedSample repository Explore repositories Support

AboutCareers Twitter Discord Contact Us Terms of Service Privacy Policy