Clock function in search algorithm generally returning 0

Question

I'm sure this may seem like a trivial problem, but I'm having issues with the "clock()" function in my program (please note I have checked similar issues but they didn't seem to relate in the same context). My clock outputs are almost always 0, however there seem to be a few 10's as well (which is why I'm baffled). I considered the fact that maybe the function calling is too quickly processed but judging by the sorting algorithms, surely there should be some time taken.

Thank you all in advance for any help! :)

P.S I'm really sorry about the mess regarding correlation of variables between functions (it's a group code I've merged together, and I'm focusing of correct output before beautifying it) :D

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int bruteForce(int array[], const int& sizeofArray);

int maxSubArray (int array[], int arraySize);

int kadane_Algorithm(int array[], int User_size);

int main()
{
    int maxBF, maxDC, maxKD;
    clock_t t1, t2, t3;
    int arraySize1 = 1;
    double t1InMSEC, t2InMSEC, t3InMSEC;

    while (arraySize1 <= 30000)
    {
        int* array = new int [arraySize1];

        for (int i = 0; i < arraySize1; i++)
        {
            array[i] = rand()% 100 + (-50);
        }

        t1 = clock();
        maxBF = bruteForce(array, arraySize1);
        t1 = clock() - t1;
        t1InMSEC = (static_cast <double>(t1))/CLOCKS_PER_SEC * 1000.00;

        t2 = clock();
        maxDC = maxSubArray(array, arraySize1);
        t2 = clock() - t2;
        t2InMSEC = (static_cast <double>(t2))/CLOCKS_PER_SEC * 1000.00;

        t3 = clock();
        maxKD = kadane_Algorithm(array, arraySize1);
        t3 = clock() - t3;
        t3InMSEC = (static_cast <double>(t3))/CLOCKS_PER_SEC * 1000.00;

        cout << arraySize1 << '\t' << t1InMSEC << '\t' << t2InMSEC << '\t' << t3InMSEC << '\t' << endl;
        arraySize1 = arraySize1 + 100;
        delete [] array;
    }
    return 0;
}

int bruteForce(int array[], const int& sizeofArray)
{
    int maxSumOfArray = 0;
    int runningSum = 0;
    int subArrayIndex = sizeofArray;

    while(subArrayIndex >= 0)
    {
        runningSum += array[subArrayIndex];

        if (runningSum >= maxSumOfArray)
        {
            maxSumOfArray = runningSum;
        }

        subArrayIndex--;
    }
return maxSumOfArray;
}

int maxSubArray (int array[], int arraySize)
{
  int leftSubArray = 0;
  int rightSubArray = 0;
  int leftSubArraySum = -50;
  int rightSubArraySum = -50;
  int sum = 0;
  if (arraySize == 1) return array[0];

  else
  {
    int midPosition = arraySize/2;
    leftSubArray = maxSubArray(array, midPosition);
    rightSubArray = maxSubArray(array, (arraySize - midPosition));

    for (int j = midPosition; j < arraySize; j++)
    {
        sum = sum + array[j];
        if (sum > rightSubArraySum)
        rightSubArraySum = sum;
    }
    sum = 0;

    for (int k = (midPosition - 1); k >= 0; k--)
    {
        sum = sum + array[k];
        if (sum > leftSubArraySum)
        leftSubArraySum = sum;
    }

  }
  int maxSubArraySum = 0;

  if (leftSubArraySum > rightSubArraySum)
  {
      maxSubArraySum = leftSubArraySum;
  }

  else maxSubArraySum = rightSubArraySum;

  return max(maxSubArraySum, (leftSubArraySum + rightSubArraySum));
}

int kadane_Algorithm(int array[], int User_size)
{
    int maxsofar=0, maxending=0, i;

    for (i=0; i < User_size; i++)
    {
        maxending += array[i];

        if (maxending < 0)
        {
            maxending = 0 ;
        }

        if (maxsofar < maxending)
        {
            maxsofar = maxending;
        }
    }
return maxending;
}

Output is as follows: (just used a snippet for visualization)

29001 0 0 0
29101 0 10 0
29201 0 0 0
29301 0 0 0
29401 0 10 0
29501 0 0 0
29601 0 0 0
29701 0 0 0
29801 0 10 0
29901 0 0 0

Please be more specific: what is it is that "almost always 0"? You have a whole bunch of things related to `clock()` going on here. — Scott Hunter, Aug 21 '15 at 17:22
While `t1InMSEC` and `t3InMSEC` are mostly 0 or 1 while `t2InMSEC` goes up with larger arrays (max = 4) on my system. — Simon Kraemer, Aug 21 '15 at 17:24
If you mean the measured time is usually 0 or 10, it is probably because `clock()` on your system does not have sufficient precision for the time periods you are trying to measure. — mattnewport, Aug 21 '15 at 17:25

score 4 · Accepted Answer · 2015-08-21T17:31:08.883

4

Your problem is probably that clock() doesn't have enough resolution: you truly are taking zero time to within the precision allowed. And if not, then it's almost surely that the compiler is optimizing away the computation since it's computing something that isn't being used.

By default, you really should be using the chrono header rather than the antiquated C facilities for timing. In particular, high_resolution_clock tends to be good for measuring relatively quick things should you find yourself really needing that.

Accurately benchmarking things is a nontrivial exercise, and you really should read up on how to do it properly. There are a surprising number of issues involving things like cache or surprising compiler optimizations or variable CPU frequency that many programmers have never even thought about before, and ignoring them can lead to incorrect conclusions.

One particular aspect is that you should generally arrange to time things that actually take some time; e.g. run whatever it is you're testing on thousands of different inputs, so that the duration is, e.g., on the order of a whole second or more. This tends to improve both the precision and the accuracy of your benchmarks.

edited Aug 21 '15 at 17:31

answered Aug 21 '15 at 17:25

I'm looking up the use of the high resolution clock at this very moment. Unfortunately, we are required to bench the time of those exact operations (which apparently should be quite easy). I'll be running it on my older pc in hopes of the slower CPU helping out. Thanks for the feedback! – Jared Aug 21 '15 at 17:33
Note - if running windows, some versions of windows / Visual Studio don't use a high resolution clock for the std::chrono stuff. One alternative is to use [QueryPerformanceCounter](http://msdn.microsoft.com/en-us/library/windows/desktop/ms644904(v=vs.85).aspx) and [QueryPerformanceFrequency](http://msdn.microsoft.com/en-us/library/windows/desktop/ms644905(v=vs.85).aspx) – rcgldr Aug 21 '15 at 21:56
@rcgldr: Thanks for pointing that out. I've found some relevant links: [stackoverflow question about it in VS2012](http://stackoverflow.com/questions/16299029/resolution-of-stdchronohigh-resolution-clock-doesnt-correspond-to-measureme) and the [bug report indicating it's fixed in 2015](https://connect.microsoft.com/VisualStudio/feedback/details/719443/c-chrono-headers-high-resolution-clock-does-not-have-high-resolution) – Aug 21 '15 at 22:15

score 0 · Answer 2 · answered Aug 24 '15 at 12:58

Thanks for all the help guys! It seems to be some kind of issue with any windows/windows emulation software.

I decided to boot up ubuntu and rather give it a shot there, and voila! I get a perfect output :)

I guess Open Source really is the best way to go :D

Clock function in search algorithm generally returning 0

2 Answers2