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:      465ms /  12.6%           24.5MiB /   7.9%    

 Section   ncalls     time    %tot     avg     alloc    %tot      avg
 ────────────────────────────────────────────────────────────────────
 Search        16   38.0ms   64.8%  2.38ms   1.32MiB   68.4%  84.3KiB
   2           16   37.8ms   64.4%  2.36ms   1.27MiB   66.0%  81.3KiB
   1           16    166μs    0.3%  10.4μs   43.2KiB    2.2%  2.70KiB
 Apply         16   20.4ms   34.7%  1.27ms    553KiB   28.1%  34.6KiB
 Rebuild       16    295μs    0.5%  18.4μs   69.4KiB    3.5%  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.85ms /  81.8%            575KiB /  87.3%    

 Section   ncalls     time    %tot     avg     alloc    %tot      avg
 ────────────────────────────────────────────────────────────────────
 Apply         16   1.01ms   67.1%  63.3μs    332KiB   66.2%  20.7KiB
 Search        16    255μs   16.9%  15.9μs    100KiB   20.0%  6.27KiB
   1           16    121μs    8.0%  7.55μs   43.2KiB    8.6%  2.70KiB
   2           16    113μs    7.5%  7.08μs   53.0KiB   10.6%  3.31KiB
 Rebuild       16    242μs   16.0%  15.1μs   69.4KiB   13.8%  4.34KiB
 ────────────────────────────────────────────────────────────────────

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.699626131807928e9, 1.69962613186598e9, false)

This page was generated using Literate.jl.