Section 3 - Timing is Everything

1A.3.1 Speed

How do we actually measure an algorithm's effectiveness? Its speed, that is, the amount of time we have to wait for an algorithm to finish (when working on some pre-determined amount of data) is one of the most important factors, which raises the question, "how do we measure the algorithm's speed?". We are going to learn some serious theory in this class, and we can argue like philosophers about whether a splay tree is better than an AVL tree for a particular application, and we can even do some fancy math to "prove" which one is faster. But given a real application, there is only one thing that really counts: the actual time the coded algorithm takes to run on a real machine. Like some famous physicist once said, "a beautiful theory can be completely destroyed by a single ugly fact."

With this in mind, let's start by providing some code that will give us actual real running times. The technique is very simple. We will record the start time and stop time of our algorithm and just take the difference. Here's the idea.

   ... do all the prep that might take time -- file reading, preparations
   that don't involve our algorithm, etc.

   // start the clock
   startTime = getTheTime();
   
   // run the algorithm
   blah-biddy-blad-di-blah
   
   // stop the clock
   stopTime = getTheTime();
   
   ... here we can do anything and take as long as we wish, 
   since our two times are safely captured
   
   // eventually, we will report the time to the user
   cout << stopTime - startTime;

(Yeah, I know ... computation in the output; not something you'll find me doing very often. Since this is something we will debug once and use the rest of the quarter, it's okay.)

1A.3.2 time.h

The code above won't actually run because there is no such function getTheTime(), and even if there were, we might not like the form that the return values took (seconds? milliseconds? microseconds?). The actual code that works in C++ comes from the time.h include file (and its corresponding .cpp file where the implementation lives). The time.h functions should be implemented in your compiler, regardless of the operating system. Here is the actual code we'll use:

// for timing our algorithms
#include <time.h>

int main()
{
   // how we time our algorithms -------------------------
   clock_t startTime, stopTime; 
   startTime = clock();

   // run the algorithm
   blah-biddy-blad-di-blah

   // how we determine the time elapsed -------------------
   stopTime = clock();

   // report algorithm time
   cout << "\nAlgorithm Elapsed Time: " 
      << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC 
      << " seconds." << endl << endl;
}

You can see that we have two int-type (actually long int) variables, to capture the start and stop times. We don't have to know what clock() returns -- milliseconds since the premier of "Star Wars" or microseconds since the Big Bang -- because there is a #define in time.h called CLOCKS_PER_SEC that we can use to convert the difference to seconds.

Let's use this to sort 200,000 ints using a bubble sort. The sort algorithm is in a file called Foothill_Sort.h (part of the cs_2c files you will have downloaded and installed), and we won't bother showing here. It is a standard bubble sort the likes of which you learned in CS 2A and then reviewed in CS 2B. (It is a very dull-witted sort, but one that is easy to learn, and that's why I chose it in those beginning courses.) Here's the program that shows our timing code:

// Example of timing a simple sort algorithm

#include <iostream>
using namespace std;

#include "Foothill_Sort.h"

// for timing our algorithms

#include <cstdlib>
#include <time.h>

// --------------- main ---------------
#define ARRAY_SIZE 200000

int main()
{
   int k;
   int arrayOfInts[ARRAY_SIZE];

   for (k = 0; k < ARRAY_SIZE; k++)
      arrayOfInts[k] = rand()%ARRAY_SIZE;

   // how we time our algorithms -------------------------
   clock_t startTime, stopTime; 
   startTime = clock();

   // sort using a home made bubble sort (in Foothill_Sort.h)
   arraySort(arrayOfInts, ARRAY_SIZE);

   // how we determine the time elapsed -------------------
   stopTime = clock();

   // report algorithm time
   cout << "\nAlgorithm Elapsed Time: " 
      << (double)(stopTime - startTime)/(double)CLOCKS_PER_SEC 
      << " seconds." << endl << endl;

   return 0; 
}

Check it out and make sure you see what we are timing. We stuff the array with 200,000 random ints first, before the timing block. We don't want the prep of the array to be counted - we are only counting the sort. Then we start the clock, do the sort and stop the clock.

Well, this is only 200,000 ints, the simplest kind of data. I'm running it on a 3.5 GHz Intel Core i7 on a 64 bit OS with 16 Gig of RAM. So it should be pretty fast, right? A half second. Maybe a couple seconds Let's have a look:

Algorithm Elapsed Time: 59.117 seconds.

Press any key to continue . . .

... oh. Well that's interesting.

We'll see why this was so long and what to do about it later in the course. It also demonstrates how important this course is. We can't be waiting 52 seconds for anything.

By the way, what happens if I change ARRAY_SIZE to 20,000 ints, i.e., reduce the size of the array by a factor of 10. Let's see:

Algorithm Elapsed Time: 0.546 seconds.

Press any key to continue . . .

Hmmm. About 100 times shorter. And if I reduce by another factor or 10 and sort only 2000 ints?:

Algorithm Elapsed Time: 0.003 seconds.

Press any key to continue . . .

This time, reducing the array size by a factor of 10, cut the run-time by a factor of more than 100. Like the country song says, "There's more behind this picture than a wall."

The main thing is to make sure you have a copy of this timing code since you'll need it throughout the course and, probably, throughout your career.

Before we leave the topic of timing, I want to disclose one important fact. Windows is a multi-tasking OS (operating system). That means we really cannot be sure that all time reported on the screen is actually being used by our algorithm. It may be that we have one dedicated processor working full steam, but we may get swapped out for a few thousand machine cycles while the processor checks the stock prices and refreshes its wifi DHCP link. The same is true of Linux, Unix and Mac OS. So this is really just a good approximation. It will be different on different machines. And, it will even run differently on the same machine a few seconds or minutes later. So we would run this a few times to see what range we get. Usually, however, the time is a good representation, and is very good for comparing two algorithms.