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: 388ms / 11.8% 21.6MiB / 8.8% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Search 16 30.2ms 65.9% 1.89ms 1.34MiB 70.2% 85.5KiB 2 16 30.1ms 65.6% 1.88ms 1.29MiB 67.8% 82.6KiB 1 16 113μs 0.2% 7.04μs 43.4KiB 2.2% 2.71KiB Apply 16 15.4ms 33.5% 961μs 511KiB 26.2% 32.0KiB Rebuild 16 255μs 0.6% 15.9μ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.49ms / 80.8% 575KiB / 87.3% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Apply 16 832μs 69.3% 52.0μs 332KiB 66.1% 20.7KiB Rebuild 16 215μs 17.9% 13.5μs 69.4KiB 13.8% 4.34KiB Search 16 154μs 12.8% 9.60μs 101KiB 20.1% 6.30KiB 1 16 73.0μs 6.1% 4.56μs 43.4KiB 8.6% 2.71KiB 2 16 69.1μs 5.8% 4.32μ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.712763133436037e9, 1.71276313345246e9, false, "none")
This page was generated using Literate.jl.