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.