Anand Anand - 1 month ago 14
Ruby Question

minitest benchmark with timeouts

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

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