CODEWITHSUNDEEP
c++recursionc++-chrono
Tristan367
Tristan367

Reputation: 35

Chrono C++ timings not correct

I'm just comparing the speed of a couple Fibonacci functions, one gives an output almost immediately and reads it got done in 500 nanoseconds, while the other, depending on the depth, may sit there loading for many seconds, yet when it is done, it will read that it took it only 100 nanoseconds... After I just sat there and waited like 20 seconds for it.

It's not a big deal as I can prove the other is slower just with raw human perception, but why would chrono not be working? Something to do with recursion?

PS I know that fibonacci2() doesn't give the correct output on odd numbered depths, I'm just testing some things and the output is actually just there so the compiler doesn't optimize it away or something. Go ahead and just copy this code and you'll see fibonacci2() immediately output but you'll have to wait like 5 seconds for fibonacci(). Thank you.

#include <iostream>
#include <chrono>


int fibonacci2(int depth) {

    static int a = 0;
    static int b = 1;

    if (b > a) { 
        a += b; //std::cout << a << '\n'; 
    }
    else { 
        b += a; //std::cout << b << '\n'; 
    }

    if (depth > 1) {
        fibonacci2(depth - 1);
    }

    return a;
}

int fibonacci(int n) {

    if (n <= 1) {
        return n;
    }

    return fibonacci(n - 1) + fibonacci(n - 2);
}


int main() {

    int f = 0;

    auto start2 = std::chrono::steady_clock::now();
    f = fibonacci2(44);
    auto stop2 = std::chrono::steady_clock::now();
    std::cout << f << '\n';
    auto duration2 = std::chrono::duration_cast<std::chrono::nanoseconds>(stop2 - start2);
    std::cout << "faster function time: " << duration2.count() << '\n';

    auto start = std::chrono::steady_clock::now();
    f = fibonacci(44);
    auto stop = std::chrono::steady_clock::now();
    std::cout << f << '\n';
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);
    std::cout << "way slower function with incorrect time: " << duration.count() << '\n';

}

Upvotes: 0

Views: 113

Answers (2)

Meanzie
Meanzie

Reputation: 96

As Mestkon answered the compiler can reorder your code. Examples of how to prevent the compiler from reordering Memory Ordering - Compile Time Memory Barrier

It would be beneficial in the future if you provided information on what compiler you were using.

gcc 7.5 with -O2 for example does not reorder the timer instructions in this given scenario.

Upvotes: 2

Mestkon
Mestkon

Reputation: 4061

I don't know what compiler you are using and with which compiler options, but I tested x64 msvc v19.28 using /O2 in godbolt. Here the compiled instructions are reordered such that it queries the perf_counter twice before invoking the fibonacci(int) function, which in code would look like

auto start = ...;
auto stop = ...;
f = fibonacci(44);

A solution to disallow this reordering might be to use a atomic_thread_fence just before and after the fibonacci function call.

Upvotes: 2

Related Questions