Why is this benchmark code for linear and binary search not working?

Question

I am trying to benchmark linear and binary search as a part of an assignment. I have written the necessary search and randomizer functions. But when I try to benchmark them I get 0 delay even for higher array sizes.

The code:

#include<iostream>
#include <time.h>
#include <windows.h>
using namespace std;

double getTime()
{
    LARGE_INTEGER t, f;
    QueryPerformanceCounter(&t);
    QueryPerformanceFrequency(&f);
    return (double)t.QuadPart/(double)f.QuadPart;
}


int linearSearch(int arr[], int len,int target){
    int resultIndex = -1;
    for(int i = 0;i<len;i++){
        if(arr[i] == target){
           resultIndex = i;
           break;
        }
    }

    return resultIndex;
}

void badSort(int arr[],int len){
    for(int i = 0 ; i< len;i++){
        int indexToSwapWith = i;
        for(int j = i+1;j < len;j++){
            if(arr[j] < arr[indexToSwapWith] )
                indexToSwapWith = j;
        }
        if(indexToSwapWith != i){
            int t = arr[i];
            arr[i] = arr[indexToSwapWith];
            arr[indexToSwapWith] = t;
        }
    }
}

int binSearch(int arr[], int len,int target){
    int resultIndex = -1;

    int first = 0;
    int last = len;
    int mid = first;

    while(first <= last){
        mid = (first + last)/2;
        if(target < arr[mid])
            last = mid-1;
        else if(target > arr[mid])
            first = mid+1;
        else
            break;
    }

    if(arr[mid] == target)
        resultIndex = mid;

    return resultIndex;
}

void fillArrRandomly(int arr[],int len){
    srand(time(NULL));
    for(int i = 0 ; i < len ;i++){
        arr[i] = rand();
    }
}

void benchmarkRandomly(int len){

    float startTime = getTime();

    int arr[len];
    fillArrRandomly(arr,len);
    badSort(arr,len);

    /*
    for(auto i : arr)
        cout<<i<<"\n";
    */

    float endTime = getTime();
    float timeElapsed = endTime - startTime;
    cout<< "prep took " << timeElapsed<<endl;

    int target = rand();

    startTime = getTime();
    int result = linearSearch(arr,len,target);

    endTime = getTime();
    timeElapsed = endTime - startTime;
    cout<<"linear search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";

    startTime = getTime();
    result = binSearch(arr,len,target);
    endTime =  getTime();
    timeElapsed = endTime - startTime;
    cout<<"binary search result for "<<target<<":"<<result<<" after "<<startTime<<" to "<<endTime <<":"<<timeElapsed<<"\n";
}

int main(){
    benchmarkRandomly(30000);
}

Sample output:

prep took 0.9375

linear search result for 29445:26987 after 701950 to 701950:0

binary search result for 29445:26987 after 701950 to 701950:0

I have tried using clock_t as well but it was the result was the same. Do I need even higher array size or am I benchmarking the wrong way?

In the course I have to implement most of the stuff myself. That's why I'm not using stl. I'm not sure if using stl::chrono is allowed but I'd like to ensure that the problem does not lie elsewhere first.

Edit: In case it isn't clear, I can't include the time for sorting and random generation in the benchmark.

Jon Guiton · Accepted Answer · 2019-05-10T09:50:57.417

2

One problem is that you set startTime = getTime() before you pack your test arrays with random values. If the random number generation is slow this might dominate that returned results. The main effort is sorting your array, the search time will be extremely low compared to this. It is probably too course an interval as you suggest. For a binary search on 30k objects we are talking about just 12 or 13 iterations so on a modern machine 20 / 1000000000 seconds at most. This is approximately zero ms.

Increasing the number of array entries won't help much, but you could try increasing the array size until you get near the memory limit. But now your problem will be that the preparatory random number generation and sorting will take forever.

I would suggest either :-

A. Checking for a very large number of items :-

unsigned int total;
startTime = getTime();
for (i=0; i<10000000; i++)
    total += binSearch(arr, len, rand());
endTime = getTime();

B. Modify your code to count the number of times you compare elements and use that information instead of timing.

edited May 10 '19 at 09:50

answered May 09 '19 at 19:06

Jon Guiton

1,360
1
9
11

A. Nope, that doesn't use the result of `binSearch` inside the loop, so it should optimize away. The OP's code *doesn't* have that problem: it saves the search result and prints it after the loop. They should be measuring *something*, maybe float rounding is making it 0. (But yes, a repeat loop *with* some optimization-defeating use of the result, like `volatile int result = binSearch(...)` would be better to amortize the measurement overhead, and to warm up code caches for the function. And yes, a random search key should help avoid warming up branch prediction as well.) – Peter Cordes May 09 '19 at 23:45
Good point. I've altered the suggested code fragment to use the result noting that total will wrap around multiple times. – Jon Guiton May 10 '19 at 09:52
That's better. QueryPerformanceCounter should still be able to time 1 iteration *roughly*, though. I still think `float` rounding and/or formatting on `cout` is a likely explanation for seeing `0`, like I said in my answer. Two calls to `QueryPerformanceCounter` won't return the same value, so the OP's time calculation is broken if they can't measure nanoseconds correctly. (It has overhead of dozens to hundreds of clock cycles, though, so it's not perfect for microbenchmarking, but to do better you have to inline `_rdtsc()` and worry about out-of-order exec.) – Peter Cordes May 10 '19 at 10:00
I don't really need the time for sorting/random gen. But averaging call times worked. Thanks. – Arturo May 10 '19 at 10:48

score 0 · Answer 2 · answered May 10 '19 at 00:21

It looks like you're using the search result (by printing it with cout *outside the timed region, that's good). And the data + key are randomized, so the search shouldn't be getting optimized away at compile time. (Benchmarking with optimization disabled is pointless, so you need tricks like this.)

Have you looked at timeElapsed with a debugger? Maybe it's a very small float that prints as 0 with default cout settings?

Or maybe float endTime - float startTime actually is equal to 0.0f because rounding to the nearest float made them equal. Subtracting two large nearby floating-point numbers produces "catastrophic cancellation".

Remember that float only has 24 bits of significand, so regardless of the frequency you divide by, if the PerformanceCounter values differ in less than 1 part in 2^24, you'll get zero. (If that function returns raw counts from x86 rdtsc, then that will happen if your system's last reboot was more than 2^24 times longer ago than the time interval. x86 TSC starts at zero when the system boots, and (on CPUs in the last ~10 years) counts at a "reference frequency" that's (approximately) equal to your CPU's rated / "sticker" frequency, regardless of turbo or idle clock speeds. See Get CPU cycle count?)

double might help, but much better to subtract in the integer domain before dividing. Also, rewriting that part will take QueryPerformanceFrequency out of the timed interval!

As @Jon suggests, it's often better to put the code under test into a repeat loop inside one longer timed interval, so (code) caches and branch prediction can warm up.

But then you have the problem of making sure repeated calls aren't optimized away, and of randomizing the search key inside the loop. (Otherwise a smart compiler might hoist the search out of the loop).

Something like volatile int result = binSearch(...); can help, because assigning to (or initializing) a volatile is a visible side-effect that can't be optimized away. So the compiler needs to actually materialize each search result in a register.

For some compilers, e.g. ones that support GNU C inline asm, you can use inline asm to require the compiler to produce a value in a register without adding any overhead of storing it anywhere. AFAIK this isn't possible with MSVC inline asm.

Why is this benchmark code for linear and binary search not working?

2 Answers2