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: 498ms / 4.3% 72.0MiB / 2.7% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Search 16 12.7ms 60.0% 794μs 1.32MiB 68.4% 84.4KiB 2 16 12.5ms 59.2% 783μs 1.27MiB 66.0% 81.4KiB 1 16 155μs 0.7% 9.69μs 43.4KiB 2.2% 2.71KiB Apply 16 8.21ms 38.8% 513μs 553KiB 28.0% 34.6KiB Rebuild 16 246μs 1.2% 15.4μs 69.7KiB 3.5% 4.35KiB ────────────────────────────────────────────────────────────────────
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.64ms / 82.2% 577KiB / 87.2% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Apply 16 866μs 64.1% 54.1μs 332KiB 66.0% 20.8KiB Search 16 270μs 20.0% 16.9μs 102KiB 20.2% 6.35KiB 1 16 131μs 9.7% 8.20μs 43.4KiB 8.6% 2.71KiB 2 16 123μs 9.1% 7.69μs 53.2KiB 10.6% 3.33KiB Rebuild 16 214μs 15.9% 13.4μs 69.7KiB 13.8% 4.35KiB ────────────────────────────────────────────────────────────────────
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.699628935438294e9, 1.699628935455287e9, false)
This page was generated using Literate.jl.