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

Avoid quadratic memory blowup in TermDag::to_string

#496Merged
Comparing
RiscInside:iurii/faster-termdag-to-string
(
bae753c
) with
main
(
0d03377
)
CodSpeed Performance Gauge
+1%
Improvements
0
Regressions
0
Untouched
8
New
0
Dropped
0
Ignored
86

Benchmarks

Passed

stresstest_large_expr
benches/example_benchmarks.rs::benches::criterion_benchmark::stresstest_large_expr
CodSpeed Performance Gauge
+5%
2.8 s
2.7 s
python_array_optimize
benches/example_benchmarks.rs::benches::criterion_benchmark::python_array_optimize
CodSpeed Performance Gauge
+1%
5.9 s
5.8 s
math-microbenchmark
benches/example_benchmarks.rs::benches::criterion_benchmark::math-microbenchmark
CodSpeed Performance Gauge
0%
4.3 s
4.2 s
typeinfer
benches/example_benchmarks.rs::benches::criterion_benchmark::typeinfer
CodSpeed Performance Gauge
0%
427.5 ms
427.6 ms
eggcc-extraction
benches/example_benchmarks.rs::benches::criterion_benchmark::eggcc-extraction
CodSpeed Performance Gauge
0%
2.2 s
2.2 s
lambda
benches/example_benchmarks.rs::benches::criterion_benchmark::lambda
CodSpeed Performance Gauge
0%
121.3 ms
121.3 ms
cykjson
benches/example_benchmarks.rs::benches::criterion_benchmark::cykjson
CodSpeed Performance Gauge
0%
377.5 ms
377.8 ms
herbie
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie
CodSpeed Performance Gauge
0%
288.2 ms
288.5 ms

Ignored

antiunifyIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::antiunify
CodSpeed Performance Gauge
0%
1.9 ms
1.9 ms
arrayIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::array
CodSpeed Performance Gauge
-1%
26.2 ms
26.4 ms
bddIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bdd
CodSpeed Performance Gauge
0%
16.6 ms
16.6 ms
before-proofsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::before-proofs
CodSpeed Performance Gauge
0%
1.2 ms
1.3 ms
bignumIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bignum
CodSpeed Performance Gauge
+1%
561.7 µs
556 µs
birewriteIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::birewrite
CodSpeed Performance Gauge
0%
1 ms
1 ms
bitwiseIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bitwise
CodSpeed Performance Gauge
0%
528.4 µs
527.8 µs
boolIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::bool
CodSpeed Performance Gauge
0%
1.1 ms
1.1 ms
calcIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::calc
CodSpeed Performance Gauge
0%
5.1 ms
5.1 ms
combinatorsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::combinators
CodSpeed Performance Gauge
0%
18.7 ms
18.7 ms
combined-nestedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::combined-nested
CodSpeed Performance Gauge
-1%
599.6 µs
605.5 µs
container-rebuildIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::container-rebuild
CodSpeed Performance Gauge
+1%
1.5 ms
1.5 ms
cykIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::cyk
CodSpeed Performance Gauge
+1%
11.3 ms
11.2 ms
datatypesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::datatypes
CodSpeed Performance Gauge
+2%
373.6 µs
366 µs
deleteIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::delete
CodSpeed Performance Gauge
+1%
392 µs
388.6 µs
eqsat-basicIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic
CodSpeed Performance Gauge
+1%
1.3 ms
1.3 ms
eqsat-basic-multisetIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsat-basic-multiset
CodSpeed Performance Gauge
0%
3.6 ms
3.6 ms
eqsolveIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::eqsolve
CodSpeed Performance Gauge
+1%
31.5 ms
31.3 ms
f64Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::f64
CodSpeed Performance Gauge
0%
727.1 µs
724.6 µs
fail_wrong_assertionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fail_wrong_assertion
CodSpeed Performance Gauge
+1%
921.2 µs
913.8 µs
fibonacciIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci
CodSpeed Performance Gauge
+1%
945.1 µs
935.6 µs
fibonacci-demandIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fibonacci-demand
CodSpeed Performance Gauge
+2%
1.9 ms
1.8 ms
fusionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::fusion
CodSpeed Performance Gauge
+1%
35.8 ms
35.6 ms
herbie-tutorialIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::herbie-tutorial
CodSpeed Performance Gauge
0%
8.6 ms
8.6 ms
i64Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::i64
CodSpeed Performance Gauge
+1%
238.6 µs
235.3 µs
includeIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::include
CodSpeed Performance Gauge
+1%
796.2 µs
789.2 µs
integer_mathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::integer_math
CodSpeed Performance Gauge
0%
12.5 ms
12.5 ms
intersectionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::intersection
CodSpeed Performance Gauge
+1%
1.4 ms
1.4 ms
intervalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::interval
CodSpeed Performance Gauge
0%
1.5 ms
1.5 ms
knapsackIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::knapsack
CodSpeed Performance Gauge
+1%
5.8 ms
5.8 ms
levenshtein-distanceIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::levenshtein-distance
CodSpeed Performance Gauge
0%
17.3 ms
17.2 ms
listIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::list
CodSpeed Performance Gauge
0%
4 ms
4 ms
looking_up_globalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::looking_up_global
CodSpeed Performance Gauge
0%
268.7 µs
268 µs
looking_up_nonconstructor_in_rewrite_goodIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::looking_up_nonconstructor_in_rewrite_good
CodSpeed Performance Gauge
-1%
417.4 µs
422.9 µs
mapIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::map
CodSpeed Performance Gauge
+1%
407.5 µs
402.5 µs
mathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::math
CodSpeed Performance Gauge
0%
35.8 ms
35.8 ms
matrixIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::matrix
CodSpeed Performance Gauge
-3%
11.1 ms
11.4 ms
merge-during-rebuildIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-during-rebuild
CodSpeed Performance Gauge
+1%
594.7 µs
586.4 µs
merge-saturatesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::merge-saturates
CodSpeed Performance Gauge
0%
2 ms
2 ms
merge_readIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::merge_read
CodSpeed Performance Gauge
0%
250.7 µs
250.5 µs
multisetIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::multiset
CodSpeed Performance Gauge
-1%
2.4 ms
2.4 ms
name-resolutionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::name-resolution
CodSpeed Performance Gauge
+1%
720.7 µs
716.1 µs
pathIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::path
CodSpeed Performance Gauge
+3%
751.4 µs
730 µs
path-unionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::path-union
CodSpeed Performance Gauge
+2%
864.6 µs
850.3 µs
pathproofIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::pathproof
CodSpeed Performance Gauge
+4%
1.1 ms
1 ms
points-toIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::points-to
CodSpeed Performance Gauge
0%
1.6 ms
1.6 ms
primitivesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::primitives
CodSpeed Performance Gauge
+1%
423.7 µs
421.5 µs
primsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::prims
CodSpeed Performance Gauge
+1%
3.4 ms
3.3 ms
push-popIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::push-pop
CodSpeed Performance Gauge
+1%
414.3 µs
408.4 µs
repro-defineIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-define
CodSpeed Performance Gauge
-1%
466.4 µs
472 µs
repro-desugar-143Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-desugar-143
CodSpeed Performance Gauge
+1%
8 ms
8 ms
repro-empty-queryIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-empty-query
CodSpeed Performance Gauge
-1%
393.9 µs
398.6 µs
repro-equal-constantIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant
CodSpeed Performance Gauge
+1%
443.9 µs
439.2 µs
repro-equal-constant2Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-equal-constant2
CodSpeed Performance Gauge
0%
428.3 µs
427.5 µs
repro-noteqbugIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-noteqbug
CodSpeed Performance Gauge
0%
527.3 µs
526.6 µs
repro-primitive-queryIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-primitive-query
CodSpeed Performance Gauge
-1%
468.7 µs
474.9 µs
repro-querybugIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug
CodSpeed Performance Gauge
0%
636.6 µs
635.6 µs
repro-querybug2Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug2
CodSpeed Performance Gauge
0%
438.1 µs
438 µs
repro-querybug3Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug3
CodSpeed Performance Gauge
0%
1.2 ms
1.2 ms
repro-querybug4Ignored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-querybug4
CodSpeed Performance Gauge
+1%
471.3 µs
464.8 µs
repro-should-saturateIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-should-saturate
CodSpeed Performance Gauge
-1%
405.5 µs
408.7 µs
repro-silly-panicIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-silly-panic
CodSpeed Performance Gauge
-1%
560.8 µs
564.7 µs
repro-typechecking-scheduleIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-typechecking-schedule
CodSpeed Performance Gauge
0%
242.3 µs
241.9 µs
repro-unsoundIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound
CodSpeed Performance Gauge
+1%
254.4 ms
252.8 ms
repro-unsound-htutorialIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-unsound-htutorial
CodSpeed Performance Gauge
0%
590.3 µs
590.1 µs
repro-vec-unequalIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::repro-vec-unequal
CodSpeed Performance Gauge
0%
537.8 µs
539.9 µs
resolutionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::resolution
CodSpeed Performance Gauge
0%
3.9 ms
3.9 ms
rw-analysisIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::rw-analysis
CodSpeed Performance Gauge
0%
37.3 ms
37.3 ms
schedule-demoIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::schedule-demo
CodSpeed Performance Gauge
-1%
2 ms
2 ms
setIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::set
CodSpeed Performance Gauge
-1%
1.8 ms
1.8 ms
set_sort_functionIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::set_sort_function
CodSpeed Performance Gauge
0%
323.9 µs
324.2 µs
stratifiedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::stratified
CodSpeed Performance Gauge
+2%
699 µs
688.4 µs
stringIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::string
CodSpeed Performance Gauge
+1%
342 µs
339.9 µs
string_quotesIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::string_quotes
CodSpeed Performance Gauge
0%
271 µs
270.3 µs
subsumeIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::subsume
CodSpeed Performance Gauge
+2%
1.2 ms
1.1 ms
test-combinedIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined
CodSpeed Performance Gauge
0%
876.4 µs
880.8 µs
test-combined-stepsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::test-combined-steps
CodSpeed Performance Gauge
0%
2.7 ms
2.7 ms
towers-of-hanoiIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::towers-of-hanoi
CodSpeed Performance Gauge
+2%
3.4 ms
3.3 ms
tricky-type-checkingIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::tricky-type-checking
CodSpeed Performance Gauge
0%
12.2 ms
12.2 ms
type-constraints-testsIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::type-constraints-tests
CodSpeed Performance Gauge
-1%
373.7 µs
377.9 µs
typecheckIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::typecheck
CodSpeed Performance Gauge
0%
5.7 ms
5.7 ms
unification-points-toIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unification-points-to
CodSpeed Performance Gauge
+1%
7.9 ms
7.8 ms
unifyIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unify
CodSpeed Performance Gauge
0%
771.1 µs
769.6 µs
unstable-fnIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::unstable-fn
CodSpeed Performance Gauge
0%
6.1 ms
6.1 ms
untilIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::until
CodSpeed Performance Gauge
0%
2.5 ms
2.5 ms
vecIgnored
benches/example_benchmarks.rs::benches::criterion_benchmark::vec
CodSpeed Performance Gauge
+1%
778.1 µs
771.3 µs

Commits

Click on a commit to change the comparison range
Base
main
0d03377
+1%
Avoid quadratic memory blowup in TermDag::to_string
bae753c
10 days ago
by RiscInside
Home Terms PrivacyDocs