minitest benchmark with timeouts

Question

I want to test that the naive recursive fibonacci (fibo_slow) takes exponential time while DP based fibonacci (fibo) takes linear time. I am using ruby 2.2.2 with Minitest benchmark.

module DSA
  def self.fibo(n)
    f = Array.new(n)
    f[0] = 1
    f[1] = 1

    (2..n).each do |i|
      f[i] = f[i - 1] + f[i - 2]
    end

    f[n]
  end

  def self.fibo_slow(n)
    if(n < 2)
      return 1
    else
      return fibo_slow(n - 1) + fibo_slow(n - 2)
    end
  end
end

The problem is that the recursive fibonacci times out at very low values of n. So, if I do this:

require 'minitest/autorun'
require 'minitest/benchmark'

class BenchFibo < Minitest::Benchmark


  def bench_fibo
    assert_performance_linear 0.9 do |n|
      DSA.fibo(n)
    end
  end

  def self.bench_range 
    [1,10,100, 1000, 10000, 100000]
  end

  def bench_fibo_slow

    assert_performance_exponential 0.9 do |n|
      DSA.fibo_slow(n)
    end
  end
end

~/Desktop/dsa/rb/dsa : ruby benchmarks/bench_fibo.rb 
Run options: --seed 47332

# Running:

bench_fibo   0.000013    0.000010    0.000020    0.000365    0.006358    0.422697
.bench_fibo_slow     0.000013    0.000017 <hangs at n = 100>

The faster fibo passes the assertion, but fibo_slow will not complete with n = 100 anytime (ahem) soon.

If I take lower values of the bench_range, the fit is not very accurate:

class BenchFibo < Minitest::Benchmark
  def bench_fibo
    assert_performance_linear 0.9 do |n|
      DSA.fibo(n)
    end
  end

  def self.bench_range 
    # [1,10,100, 1000, 10000, 100000]
    [1,2,4,8,16,32]
  end

  def bench_fibo_slow

    assert_performance_exponential 0.9 do |n|
      DSA.fibo_slow(n)
    end
  end
end

~/Desktop/dsa/rb/dsa : ruby benchmarks/bench_fibo.rb 
Run options: --seed 61619

# Running:

bench_fibo   0.000017    0.000007    0.000011    0.000011    0.000007    0.000008
Fbench_fibo_slow     0.000008    0.000007    0.000005    0.000009    0.000138    0.316749
F

Finished in 0.360861s, 5.5423 runs/s, 5.5423 assertions/s.

  1) Failure:
BenchFibo#bench_fibo [benchmarks/bench_fibo.rb:9]:
Expected 0.21733687958458803 to be >= 0.9. 

  2) Failure:
BenchFibo#bench_fibo_slow [benchmarks/bench_fibo.rb:21]:
Expected 0.5924648214229373 to be >= 0.9.

2 runs, 2 assertions, 2 failures, 0 errors, 0 skips

So, I could add a time out for fibo_slow in the first code example above, like so:

def self.bench_range 
    [1,10,100, 1000, 10000, 100000]
end

def bench_fibo_slow  
    assert_performance_exponential 0.9 do |n|
      begin
        Timeout::timeout(3) do
          DSA.fibo_slow(n)
        end
      rescue
        # what could I do here, if anything?
      end  
    end
  end 

but that would mess up the performance data, and the assertion would never fit.

Additionally, even when I run with the timeout, I get the unhandled error SystemStackError stack level too deep - so, I could maybe rescue that within the timeout (but there is no point there, since the timeout itself corrupts the fitted curve).

My question is, how do I use benchmark and assert_performance_xxx to test the two fibonacci algos?

Answer 1

Recursive Fibonacci has O(2^n) time complexity (using O(branches ^ depth) formula - why 2^n?), so it's a power function instead of an exponential one. It works with the following config for me:

def self.bench_range
  [25, 30, 35] # Smaller values seem problematic
end

def bench_fibo_slow
  assert_performance_power 0.9 do |n|
    DSA.fibo_slow(n)
  end
end