Test benchmark fibonaci recursive/non recursive

Tram Ho

Test benchmark fibonacci recursive/non recursive

Motive, reason

Until now, I still have the question that for the same problem between recursive and non-recursive, which one will be the more effective solution. On the occasion of my team members’ code review, everyone talked about recursive / non recursive, so I decided to dig deeper to see if my initial thought was correct.

I have read the documents, almost everyone has the same comment as follows:

Advantages of recursive: Neat, easy to understand, easy to code

Cons: Consume memory space, and processing time due to having to switch context between function calls.

The above are all theoretical comments. From the perspective of a person who is currently an engineer who was a professional student, I only believe when there are experimental results that are specific numbers.

And go , it’s pretty easy for me to do this with the test benchmarks tool

Without saying much more, let’s get to the main topic.

Test benchmarks with fibonacci recursive

First, we implement the algorithm implementation with a recursive approach.

Install benchmark test with input N = 10

Execute the benchmark test with the following command

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Result

Comment: Repeat 4973802 times, each time takes 239.1 ns total 1189236058.2 ns

My phone is up to i7 , I just noticed it now

1 billion more in-depth analysis

Runtime analysis

Run command

go tool pprof profile.out

Use the top command to get the most time consuming processing, sorted in descending order

Result

Total running time loss for FibRecursive is 1.21s

Continue in-depth analysis of each command line for the function FibRecursive

(pprof) list FibRecursive

Result:

Show graph results in png, pdf using command:

(pprof) web

images

End of analysis

(pprof) q

Analysis of memory allocation

go tool pprof memprofile.out

(pprof) web

images

Test benchmarks with fibonacci non recursive

Implement the algorithm with the approach of de-recursion.

Install test benchmark with input N = 10 (same step above)

Optimized

Because the variable tmp is allocated in the loop, it increases the memory quite a lot, causing the wrong conclusion. After finding out the cause, I fixed it as follows:

Analysis

Continue to run the same command

go test -bench=. -benchmem -memprofile memprofile.out -cpuprofile profile.out

Result:

there are 223505781 operations each taking 5,321 5.321 ns total 1189274260.7 ns

Optimized

Run command

go tool pprof profile.out

(pprof) top

Total running time for FibNonRecursive is 980ms

Optimized

Total running time loss for FibNonRecursive is 0.90s

(pprof) list FibNonRecursive

Optimized

(pprof) list web

images

Optimized

images

(pprof) q

Analysis of memory allocation

go tool pprof memprofile.out

(pprof) top

Optimized

(pprof) web

images

Optimized

images

Compare and conclude with the case N = 10

images

CriteriaRecursiveNon RecursiveNon Recursive Optimized
Time1.16s0.01s0.02s
Memory5140.68kB5811.98kB3746.37kB

Note: The memory comparison criterion is not reasonable

Updated

True to the original comment, after optimized Non Recursive has a lower running time and takes less memory than Recursive

Please test it out let try !!!

References

Happy coding!!!

 

Share the news now

Source : Viblo