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: 438ms / 10.3% 25.4MiB / 7.9% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Search 16 29.3ms 64.7% 1.83ms 1.44MiB 71.8% 92.0KiB 2 16 29.2ms 64.4% 1.83ms 1.39MiB 69.5% 89.0KiB 1 16 102μs 0.2% 6.38μs 44.0KiB 2.1% 2.75KiB Apply 16 15.7ms 34.7% 982μs 513KiB 25.0% 32.1KiB Rebuild 16 281μs 0.6% 17.5μs 65.3KiB 3.2% 4.08KiB ────────────────────────────────────────────────────────────────────
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.41ms / 81.1% 579KiB / 87.3% Section ncalls time %tot avg alloc %tot avg ──────────────────────────────────────────────────────────────────── Apply 16 755μs 65.9% 47.2μs 338KiB 66.9% 21.1KiB Rebuild 16 240μs 20.9% 15.0μs 65.3KiB 12.9% 4.08KiB Search 16 151μs 13.2% 9.45μs 102KiB 20.2% 6.38KiB 1 16 68.7μs 6.0% 4.29μs 44.0KiB 8.7% 2.75KiB 2 16 68.3μs 6.0% 4.27μs 54.3KiB 10.7% 3.39KiB ────────────────────────────────────────────────────────────────────
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.739710348707308e9, 1.739710348829707e9, false, "none")
This page was generated using Literate.jl.