Benchmarking Fibonacci. E-Graphs memoize computation.
using Metatheory
using Test
function fib end
fibo = @theory x y n begin
x::Int + y::Int => x + y
fib(n::Int) => (n < 2 ? n : :(fib($(n - 1)) + fib($(n - 2))))
end
params = SaturationParams(timeout = 60)
SaturationParams(60, 0x0000000000000000, 5000, 15000, nothing, Metatheory.EGraphs.var"#30#32"(), Metatheory.EGraphs.Schedulers.BackoffScheduler, (), false, true)
We run the saturation twice to see a result that does not include compilation time.
g = EGraph(:(fib(10)))
saturate!(g, fibo, params)
SaturationReport ================= Stop Reason: saturated Iterations: 16 EGraph Size: 15 eclasses, 54 nodes ──────────────────────────────────────────────────────────────────── Time Allocations ─────────────────────── ──────────────────────── Tot / % measured: 362ms / 11.8% 21.6MiB / 8.8% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Search 16 28.1ms 65.8% 1.75ms 1.34MiB 70.2% 85.5KiB 2 16 28.0ms 65.5% 1.75ms 1.29MiB 67.8% 82.6KiB 1 16 94.4μs 0.2% 5.90μs 43.4KiB 2.2% 2.71KiB Apply 16 14.3ms 33.6% 897μs 511KiB 26.2% 32.0KiB Rebuild 16 245μs 0.6% 15.3μs 69.4KiB 3.6% 4.34KiB ────────────────────────────────────────────────────────────────────
That's fast!
z = EGraph(:(fib(10)))
saturate!(z, fibo, params)
SaturationReport ================= Stop Reason: saturated Iterations: 16 EGraph Size: 15 eclasses, 54 nodes ──────────────────────────────────────────────────────────────────── Time Allocations ─────────────────────── ──────────────────────── Tot / % measured: 1.45ms / 80.9% 575KiB / 87.3% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Apply 16 827μs 70.7% 51.7μs 332KiB 66.1% 20.7KiB Rebuild 16 201μs 17.2% 12.6μs 69.4KiB 13.8% 4.34KiB Search 16 143μs 12.2% 8.91μs 101KiB 20.1% 6.30KiB 1 16 67.4μs 5.8% 4.21μs 43.4KiB 8.6% 2.71KiB 2 16 64.1μs 5.5% 4.01μs 53.2KiB 10.6% 3.33KiB ────────────────────────────────────────────────────────────────────
We can test that the result is correct.
@testset "Fibonacci" begin
@test 55 == extract!(g, astsize)
end
Test.DefaultTestSet("Fibonacci", Any[], 1, false, false, true, 1.716974744087244e9, 1.716974744102625e9, false, "none")
This page was generated using Literate.jl.