Confusion: Timings For Binary Search Algorithm

[RyanV]

Hello,

I have a problem for my Data Structures and Algorithms class
that involves running a binary search in three different programming
languages, C++, C, and Java.

I am supposed to carry out 1,000,000 unsuccessful searches on arrays of
sizes: 128; 512; 2,048; 8,192; 32,768; 131,072; 524,288; 2,097,152.

Then I am supposed to measure the timings for each of these algorithms
in wall clock time. I chose to measure only the time required for the
1,000,000 unsuccessful searches, and not the entire program.

However, after running both my Java and C++ programs, I noticed that my
C++ timings were 10 times the size of my Java timings. Which seemed odd
to me, I thought I remembered being taught that C++ is the leaner of the
two languages.

Does anyone have any insight into this?

If it helps, here is my code in C++ and Java, both timings are measured
in milliseconds.

#include <Windows.h>
#include <iostream>

int binarySearch(int [], int, int, int);

int main()
{
	const int NUMBER_OF_ELEMENTS = (2097152);
	int a[NUMBER_OF_ELEMENTS];
	for(int i = 0; i < NUMBER_OF_ELEMENTS; i++)
	{
		a[i] = i;
	}
	DWORD start, end;
	start = GetTickCount();
	for(int i = 0; i < 1000000; i++)
		binarySearch(a, -50, 0, (NUMBER_OF_ELEMENTS - 1));
	end = GetTickCount();
	std::cout << "Elapsed time: " << (double)(end - start);
	std::cin.get();	
}

int binarySearch(int arrayToBeSearched[], int value, int min, int max)
{
	if(max < min)
		return -1;
	else
	{
		int mid = (int)((min + max) /2 );
		if (arrayToBeSearched[mid] > value)
			return binarySearch(arrayToBeSearched, value, min, (mid - 1));
		else if(arrayToBeSearched[mid] < value)
			return binarySearch(arrayToBeSearched, value, (mid + 1), max);
		else
			return mid;
	}
}

public class Main 
{
    public static void main(String[] args) 
    {
        final int ARRAY_SIZE = (2097152);
        int[] testArray = new int[ARRAY_SIZE];
        for(int i = 0; i < ARRAY_SIZE; i++)
        {
            testArray[i] = i;
        }
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1000000; i++)
        {
            binarySearch(testArray, -10, 0, ARRAY_SIZE - 1);
        }
        long end = System.currentTimeMillis();
        System.out.println("Execution time: " + (end - start));
    }
    
    public static int binarySearch(int[] A, int key, int min, int max)
    {
        if(max < min)
            return -1;
        else
        {
            int mid = (int)((max + min) / 2);
            if(A[mid] > key)
                return binarySearch(A, key, min, mid - 1);
            else if (A[mid] < key)
                return binarySearch(A, key, mid + 1, max);
            else return mid;
        }
    }
}

[Peter87]

Did you turn on optimizations when compiling the C++ program.

[RyanV]

I don't know what that is. I'm using VS2010, how would I do that?

[Peter87]

By Select release build instead of debug build.

[RyanV]

Ooh, yeah, I did that earlier. But when I did it, and ran the program, it
reported that the algorithm took 0 milliseconds to run, which I am pretty
sure is not correct.

Any ideas what could be up with that?

[Cubbi]

const int NUMBER_OF_ELEMENTS = (2097152);
int a[NUMBER_OF_ELEMENTS];

That's one large stack size, not everybody's platform has that. To make this more portable, use vectors (which you should use anyway, this isn't C)

const int NUMBER_OF_ELEMENTS = 2097152;
vector<int> a(NUMBER_OF_ELEMENTS);
...
binarySearch(&a[0], ...

it reported that the algorithm took 0 milliseconds to run, which I am pretty sure is not correct.

C++ throws out irrelevant code: you're not using the results of your searches in any way, so they are not compiled at all.

You could output them, but output would throw off the timing. An easy way to beat that optimization is to add a volatile variable, say
volatile int sink;
and then store the result of your binarySearch in it:
sink = binarySearch(&a[0], -50, 0, (NUMBER_OF_ELEMENTS - 1));

I'm getting ~20 ms from your program on my computer (with a vector; it didn't run with an array), and ~75 ms from your java version.

[AbstractionAnon]

You don't state if you have to use a particular algorithim. You'll get better performance if you use an iterative algorithim rather than a recursive one.

An iterative algorithim will avoid repeatedly pushing registers and arguments onto the stack.

[RyanV]

Thanks for all the replies guys.

What would be the benefit of using a volatile int over a regular int
variable? Also, would setting sink to the result of my binary search
throw off my timings by adding an extra operation in there?

As far as the stack size goes, we are supposed to test it with
8 different array sizes. That was just the largest array size, and my
prof mentioned that it probably would cause an overflow anyways.

As far as a recursive vs. an iterative algorithm goes; it doesn't really
matter which we use. Performance is not the objective here, simply observing the timings.