search

JuliaSymbolics / Metatheory.jl

Makes Julia reason with equations. General purpose metaprogramming, symbolic computation and algebraic equational reasoning library for the Julia programming language: E-Graphs & equality saturation, term rewriting and more.
https://juliasymbolics.github.io/Metatheory.jl/dev/
MIT License
355 stars 46 forks source link

Draft: Complete Overhaul of Egraphs (even faster) #184

Closed 0x0f0f0f closed 7 months ago

0x0f0f0f commented 7 months ago

New simplified term interface - new rebuild - compact enodes as UInt vectors - simplified analysis

github-actions[bot] commented 7 months ago

Benchmark Results

master 4229c342ecdce9... t[master]/t[4229c342ecdce9...]
basic_maths/simpl1 0.0581 ± 0.0042 s 28.5 ± 3.8 ms 2.04
calc_logic/demorgan 0.613 ± 0.013 ms 0.424 ± 0.0091 ms 1.45
egraph/addexpr 19.6 ± 1.2 ms 8.78 ± 0.4 ms 2.23
egraph/constructor 0.588 ± 0.024 μs 0.794 ± 0.048 μs 0.74
prop_logic/demorgan 0.984 ± 0.02 ms 0.539 ± 0.012 ms 1.83
prop_logic/freges_theorem 0.0395 ± 0.0033 s 13.4 ± 0.29 ms 2.96
prop_logic/prove1 0.445 ± 0.025 s 0.133 ± 0.002 s 3.36
prop_logic/rewrite 0.0771 ± 0.0015 ms 0.049 ± 0.0012 ms 1.57
while_superinterpreter/while_10 0.122 ± 0.0012 s 0.0647 ± 0.00096 s 1.89
time_to_load 0.257 ± 0.00099 s 0.155 ± 0.00056 s 1.66

Benchmark Plots

A plot of the benchmark results have been uploaded as an artifact to the workflow run for this PR. Go to "Actions"->"Benchmark a pull request"->[the most recent run]->"Artifacts" (at the bottom).

codecov-commenter commented 7 months ago

Codecov Report

Attention: 68 lines in your changes are missing coverage. Please review.

Comparison is base (85f608b) 69.11% compared to head (4229c34) 75.57%.

Files Patch % Lines
src/EGraphs/egraph.jl 84.61% 34 Missing :warning:
src/TermInterface.jl 81.57% 7 Missing :warning:
src/EGraphs/saturation.jl 93.33% 5 Missing :warning:
src/Rules.jl 0.00% 5 Missing :warning:
src/Rewriters.jl 55.55% 4 Missing :warning:
src/extras/graphviz.jl 0.00% 4 Missing :warning:
src/Syntax.jl 90.00% 3 Missing :warning:
src/Patterns.jl 85.71% 2 Missing :warning:
src/EGraphs/extract.jl 97.91% 1 Missing :warning:
src/matchers.jl 94.44% 1 Missing :warning:
... and 2 more

:exclamation: Your organization needs to install the Codecov GitHub app to enable full functionality.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #184 +/- ## ========================================== + Coverage 69.11% 75.57% +6.46% ========================================== Files 16 19 +3 Lines 1350 1261 -89 ========================================== + Hits 933 953 +20 + Misses 417 308 -109 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

0x0f0f0f commented 7 months ago

Moved to ale/3.0 branch #185