Wrong output with 'chrono' library

Question

I was trying to calculate time elapsed during execution of my insertion sort function. So I did as follow. P.S. - function is running correctly and sorting all the numbers. Compiler - GCC Windows

    auto start = chrono::steady_clock::now();
    insertionSort(arr,1000);
    auto end = chrono::steady_clock::now();

    auto diff = start - end; // gives 0 
    auto diff = end - start ; // still zero

    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;

Firstly I tried with 100 input it gave me 0 ms then I changed it to ns it still gave zero. Then I increased my input to 1000. But sadly output is still zero. Is this correct way to write chrono? Someone suggested to try chrono::high_resolution_clock it still gave me 0ns.

Or any method you guys can suggest to calculate time of a function.

UPDATE - So I was looking for solution so I found that if do something like sometimes it gave result.

    auto start = chrono::high_resolution_clock::now();
    insertionSort(arr,1000);
    auto end = chrono::high_resolution_clock::now();

    auto diff = end - start;

    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;


    ofstream  write;
    write.open("sort.txt");
    if(write)
    {
        for(int i = 0 ; i < 1000 ; ++i)
        {
            write<<arr[i]<<endl;
        }
    }
    else{
        cout<<"Unable to open file.\n";
    }

I tried to write it in file now it giving me result if I choose nano second. But if I chose mili its still zero.

Does this mean insertion sort fast is exceptionally fast that C++ can't even measure it ?

Here is reproducable code.

#include<iostream>
#include<fstream>
#include<chrono>
using namespace std;

void readData();
void insertionSort(int * , int );
void readData()
{

    int arr[1000];
    ifstream read;
    read.open("sort.txt",ios::binary);
    if(read)
    {
        int i = 0;
        int temp;
        while(read>>temp)
        {
            arr[i] = temp;
            ++i;
        }
        read.close();

    }
    else{
        cout<<"Unable to open file.\n";
    }


    auto start = chrono::high_resolution_clock::now();
    insertionSort(arr,1000);
    auto end = chrono::high_resolution_clock::now();

    auto diff = end - start;

    cout << chrono::duration <double, nano> (diff).count() << " ns" << endl;

    ofstream  write;
    write.open("sort.txt");
    if(write)
    {
        for(int i = 0 ; i < 1000 ; ++i)
        {
            write<<arr[i]<<endl;
        }
    }
    else{
        cout<<"Unable to open file.\n";
    }

}
void insertionSort(int *arr , int size)
{
    for(int i = 1 ; i < size ; ++i)
    {
        int key = arr[i];
        int j = i -1 ;
        while(j>= 0 && arr[j]> key)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[++j] = key;
    }

}
int main()
{
    readData();
    return 0;
}

Answer 1

Use correct template argument to mark that you want milliseconds:

std::chrono::duration<double, std::milli> diff = end - start ; // still zero
cout << diff.count() << " ms" << endl;

If it is still zero, maybe your operation is so fast that it take less than 1 millisecond to finish? Sorting array o 1000 elements is quite fast these days. Make it bigger or repeat several times.

For 10000 elems it is starting to return some values greater than 0. What is your environment? Maybe in your case high_resolution_clock is not available... Time measurements with High_resolution_clock not working as intended

BTW I also have 0 as a result 50% of the time.

Answer 2

As you are on Windows, you can use QueryPerformanceFrequency(). It will give you the number of ticks your system does in one second. So, you can use it to calculate the actual accuracy of your system clock:

#include <Windows.h>

int main() {
    LARGE_INTEGER freq;
    QueryPerformanceFrequency(&freq);
    std::cout << 1.e9 / freq.QuadPart << "ns accuracy" << std::endl;
}

Everything attempt to measure something faster than this, will result in 0. Any attempt to measure something that is roughly in the same magnitude, will be inaccurate.

For example, on my system above code prints 100ns accuracy. If I run your code, it prints 1100ns most of the time, sometimes 1200ns, sometimes 1000ns. Note how this is always a multiple of the accuracy.

One common way to overcome this is to run the code in question multiple times and take the average, like so:

constexpr int runs = 2000;

auto start = std::chrono::steady_clock::now();
for (int i = 0; i < runs; ++i)
    insertionSort(arr,1000);
auto end = std::chrono::steady_clock::now();

auto diff = end - start;

cout << std::chrono::duration <double, std::nano> (diff).count() / runs << " ns" << endl;

On my system this prints 1016.7ns.