1

I'm trying to benchmark recursive fibonacci sequence calculator on C++. But surprisingly program outputs 0 nanoseconds, and start calculation after printing result. (CPU usage increase after printing 0 nanoseconds)

I think this is optimization feature of the compiler.

#include <iostream>
#include <chrono>

int fib2(int n) {
    return (n < 2) ? n : fib2(n - 1) + fib2(n - 2);
}

int main(int argc, char* argv[])
{
    auto tbegin = std::chrono::high_resolution_clock::now();
    int a = fib2(50);
    auto tend = std::chrono::high_resolution_clock::now();

    std::cout << (tend - tbegin).count() << " nanoseconds" << std::endl;

    std::cout << "fib => " << a << std::endl;
}

Output:

0 nanoseconds

Is it feature? If yes, how can I disable this feature?

CrazyDeveloper
  • 11
  • 3
  • 1
    Just FYI - 50th Fibonacci's number is definitely not going to fit in an `int` – Fureeish Sep 12 '18 at 23:37
  • 2
    First, as others have pointed out, `int` might not fit `fib2(50);`, meaning you may have a `signed int` overflow which is undefined behavior and can cause your program to do anything. Second, your result (should it fit in `int`) is easily calculable at compile time. The compiler can see that `a` will always have the same value and can calculate it at compile time. Try taking a user input instead of always calculating the 50th term, then the compiler can't assume the result. Finally, you never check the type returned by `high_resolution_clock::now()`. Verify the clock's `rep` and `period`. – François Andrieux Sep 12 '18 at 23:46
  • consider using [`duration_cast`](https://en.cppreference.com/w/cpp/chrono/duration/duration_cast) to nanoseconds to make sure the count is what you expect. – kmdreko Sep 12 '18 at 23:50
  • I tried with uint and casted to nanosecond, but again it calculate after printing 0 nanoseconds. It seems like compiler reorder execution. Also I find this: https://stackoverflow.com/questions/26190364/is-it-legal-for-a-c-optimizer-to-reorder-calls-to-clock – CrazyDeveloper Sep 13 '18 at 00:13
  • @CrazyDeveloper What compiler are you using? What compilation flags are you using? Compilers may be allowed to reorder `now` relative to other code, but no reasonable implementation would allow it. Be sure to try to have your `fib2` parameter depend on user input to reduce the possibility of optimizations. – François Andrieux Sep 13 '18 at 00:22
  • Try declaring tbegin, a and tend as global volatile variables. That should force the compiler to respect the order of assignment, and probably expression evaluation, in the source code. – JimmyB Sep 13 '18 at 00:56
  • Try putting `std::atomic_thread_fence(std::memory_order_seq_cst);` before and after the `int a =` line – M.M Sep 13 '18 at 01:24

1 Answers1

2

The problem is that the result of this function called with a value of 50 doesn't fit to the int type, it's just too big. Try using int64_t instead.

Live demo

Note that I replaced the original Fibbonachi function with a more optimized one, as the execution took too long and the online tool cuts off the execution after some period of time. That is not a fault of the program or the code, it's just a protection of the online tool.

ProXicT
  • 1,903
  • 3
  • 22
  • 46
  • Your example is an improvement on the original code, but it doesn't show that this is definitively the cause of the problem that OP is seeing. This *might* be the cause of the problem and it certainly is *a* problem, but I don't believe it answers the question. Edit : Though I guess that's a problem with UB, you can't really prove that *this* UB is the source of the problem. – François Andrieux Sep 13 '18 at 00:10
  • @FrançoisAndrieux That's a good point, although I *think* the problem with the wrong delta time output is caused by the UB, this answer doesn't really prove it. – ProXicT Sep 13 '18 at 00:15
  • OP has commented, stating that passing to `unsigned int` did not solve the problem. Since `unsigned int` overflow is well defined there must be another cause for the problem. – François Andrieux Sep 13 '18 at 00:26
  • @FrançoisAndrieux Since `n` may never be lower than `2`, it may cause a call stack overflow? – ProXicT Sep 13 '18 at 00:40
  • If you are implying infinite recursion, I don't see how. Though a sufficiently large `n` may cause a stack overflow. And notice that OP's output includes the time elapsed but not the result of the Fibonacci calculation. – François Andrieux Sep 13 '18 at 00:43