Execution time of a short function c++

Question

I want to calculate the execution time of a pretty small function to compare the execution time of a recursive function vs iterative.

Surely, clock() simply cannot do that with not enough resolution. Could you show me how can I use another time sources like GetThreadTimes(). I saw a description on the Microsoft website, but did not catch the principle.

Also, <chrono> header does not work in MS Visual 10.

The code:

int search (int a[], int size, int& num) {

if (size >0) {

    if (a[size-1] == 17) {num = size-1; return num;}
    else {return search (a, --size, num);}}
else {return num=-1;};
}

int searchit (int a[], int size, int& num) {

    for (int i =0; i< size; i++) {
        if (a[i] == 17) {num = i;}
        else num = -1;
    }
    return num;}


int main () {
    srand ((unsigned int) time(0));
    int num = 0;
    const int size = 40;
    int a[size];
    for (int i =0; i< size; i++) {

        a[i] = rand()%100;
        cout << a[i] << endl;}
    cout << '\n';

    search (a, size, num);

    cout << num << endl;

    cin.get();
    cin.ignore();
}

[`std::chrono::high_resolution_clock`](http://en.cppreference.com/w/cpp/chrono/high_resolution_clock) — BoBTFish, Feb 26 '15 at 13:40
time taken to execute a complete function http://stackoverflow.com/a/40380118/6180077 — Abdullah Farweez, May 17 '17 at 05:04

Damon · Accepted Answer · 2015-02-26T15:55:36.787

One solution would be to do many iterations as suggested by @amchacon. This has the advantage of being straightforward and easy.

It has the disadvantage of possibly leading to inaccurate or incorrect results both due to the compiler using different heuristics for inlining and/or instruction pipelining, and due to both instruction and data caches having warmed up after the first iteration.
So while your function might indeed have pretty poor performance due to a bad memory access pattern (maybe resulting in two dozen cache misses costing you 500 cycles each), this might not at all show when you run the function a hundred times, if the total set of cache lines fits into the caches.

What are the alternatives?

a) Not applicable for your problem (since you want to test a recursive algorithm), but I'll state it anyway for the "general" case: Use IACA. It's especially designed for the purpose of micro-benchmarking a small section of code down to the instruction.

b) Use a higher precision timer or use a timer that isn't a timer at all. For this purpose, you have QueryPerformanceCounter and QueryThreadCycleTime (Vista and later) available under Windows. Cycles may be preferrable to time, depending on what you want to measure.

c) Query the thread times. This is in my opinion the best way, since you get reliable, precise, accurate times (much unlike timers, which may include context switches and time spent in other processes!), and it works for any kind of code, letting you distinguish kernel and user time in case your code calls system functions, and differentiate CPU and wall time.
Call GetThreadTimes once before and once after running your function and subtract the respective UserTime and KernelTime values.
Or, start a worker thread if you are also interested in wall time (for wall time, you will subtract CreationTime from ExitTime, and you obviously only get a valid ExitTime after the thread has exited!). Calculating wall time may be useful if your code also involves blocking I/O operations.

I have read about _GetThreadTimes_ even before asking this question. But I was confused how to use it. For example, here (http://www.codeproject.com/Articles/175033/An-eternal-question-of-timing) a pretty hefty way is described. Could you advise on this? — VVG, Feb 26 '15 at 16:03
Unless you have a ton of threads and want to account for parallel execution, it is not that hefty, really. All `GetThreadTimes` does is return the time that one particular thread (given by a handle) was actually running, at 100 nanosecond resolution (though possibly with less precision). Despite the intimidating WinAPI names, they're really just `uint64_t` values, which every compiler can natively subtract (yes, that is sloppy and non-portable, but bleh). To time your own thread, the handle is `GetCurrentThread()` or `(HANDLE) -1`, otherwise it's the handle you got from spawning your worker. — Damon, Feb 26 '15 at 17:07
It only gets complicated when you throw concurrency into the game (but not too much, really). Note that while it seems funny, it is perfectly normal to have thread time being greater than the total time if you have concurrency (that is, if two threads run at 100% you will have 10 seconds of thread time when the program only runs 5 seconds). That is, of course, only normal -- you have 5 seconds, but two threads. — Damon, Feb 26 '15 at 17:11

score 2 · Answer 2 · answered Feb 26 '15 at 13:45

Just do 100 searchs and take average:

    time_t begin,end,total;
    const int iterations = 100;
    begin = clock();

    for (int i = 0;i<iterations;i++)
     search (a, size, num);

    end = clock();
    total = (end-begin)/static_cast<double>(CLOCKS_PER_SEC);

    cout<<"Average time for "<<iterations<<" iterations: "<<total/iterations<<endl;

The compiler will unroll for loop :). Anyway, consume of For loop is negligible.

Execution time of a short function c++

2 Answers2