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:      365ms /  12.2%           21.6MiB /   8.8%    

 Section   ncalls     time    %tot     avg     alloc    %tot      avg
 ────────────────────────────────────────────────────────────────────
 Search        16   29.3ms   65.7%  1.83ms   1.34MiB   70.2%  85.5KiB
   2           16   29.1ms   65.4%  1.82ms   1.29MiB   67.8%  82.6KiB
   1           16    107μs    0.2%  6.70μs   43.4KiB    2.2%  2.71KiB
 Apply         16   15.0ms   33.7%   938μs    511KiB   26.2%  32.0KiB
 Rebuild       16    250μs    0.6%  15.6μ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.44ms /  82.4%            575KiB /  87.3%    

 Section   ncalls     time    %tot     avg     alloc    %tot      avg
 ────────────────────────────────────────────────────────────────────
 Apply         16    825μs   69.7%  51.6μs    332KiB   66.1%  20.7KiB
 Rebuild       16    212μs   17.9%  13.3μs   69.4KiB   13.8%  4.34KiB
 Search        16    147μs   12.4%  9.18μs    101KiB   20.1%  6.30KiB
   1           16   71.2μs    6.0%  4.45μs   43.4KiB    8.6%  2.71KiB
   2           16   64.1μs    5.4%  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.715372674934138e9, 1.715372674949756e9, false, "none")

This page was generated using Literate.jl.