Anand - 10 days ago 5x
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?

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
``````
Source (Stackoverflow)