CODEWITHSUNDEEP
c++benchmarking
Megadardery
Megadardery

Reputation: 149

How can I test two algorithms and determine which is faster?

Whenever working on a specific problem, I may come across different solutions. I'm not sure how to choose the better of the two options. The first idea is to compute the complexity of the two solutions, but sometimes they may share the same complexity, or they may differ but the range of the input is small that the constant factor matters.

The second idea is to benchmark both solutions. However, I'm not sure how to time them using c++. I have found this question: How to Calculate Execution Time of a Code Snippet in C++ , but I don't know how to properly deal with compiler optimizations or processor inconsistencies.

In short: is the code provided in the question above sufficient for everyday tests? is there some options that I should enable in the compiler before I run the tests? (I'm using Visual C++) How many tests should I do, and how much time difference between the two benchmarks matters?

Here is an example of a code I want to test. Which of these is faster? How can I calculate that myself?

unsigned long long fiborecursion(int rank){
    if (rank == 0) return 1;
    else if (rank < 0) return 0;
    return fiborecursion(rank-1) + fiborecursion(rank-2);
}

double sq5 = sqrt(5);
unsigned long long fiboconstant(int rank){
    return pow((1 + sq5) / 2, rank + 1) / sq5 + 0.5;
}

Upvotes: 1

Views: 423

Answers (1)

user9478968
user9478968

Reputation:

Using the clock from this answer

#include <iostream>
#include <chrono>

class Timer
{
public:
    Timer() : beg_(clock_::now()) {}
    void reset() { beg_ = clock_::now(); }
    double elapsed() const { 
        return std::chrono::duration_cast<second_>
            (clock_::now() - beg_).count(); }

private:
    typedef std::chrono::high_resolution_clock clock_;
    typedef std::chrono::duration<double, std::ratio<1> > second_;
    std::chrono::time_point<clock_> beg_;
};

You can write a program to time both of your functions.

int main() {
    const int N = 10000;
    Timer tmr;

    tmr.reset();
    for (int i = 0; i < N; i++) {
        auto value = fiborecursion(i%50);
    }
    double time1 = tmr.elapsed();

    tmr.reset();
    for (int i = 0; i < N; i++) {
        auto value = fiboconstant(i%50);
    }
    double time2 = tmr.elapsed();

    std::cout << "Recursion"
            << "\n\tTotal: " << time1
            << "\n\tAvg: " << time1 / N
            << "\n"
            << "\nConstant"
            << "\n\tTotal: " << time2
            << "\n\tAvg: " << time2 / N
            << "\n";
}

I would try compiling with no compiler optimizations (-O0) and max compiler optimizations (-O3) just to see what the differences are. It is likely that at max optimizations the compiler may eliminate the loops entirely.

Upvotes: 1

Related Questions