CS210 Lab: Libraries and Running Time Measurement

Lab Exercise:

Click the little computer above for a detailed description.
In the exercise, the students can add the library, which has been created in this lab, to existing code to test the runtime of three different search algorithms and three different sorting algorithms.

1. Running Time Measurements

A routine's performance can be judged in many ways. In CS210, you have been/will be learning Big Oh. The idea is that you can estimate the routine's projected execution times as a function of the number of data items (N) that it manipulates as it performs its task. The results are estimates of the form O(N), O(LogN) and so on.

Big Oh allows us to group routines based on their projected performance under different conditions (best case, worst case, etc). Remember that Big Oh is only an estimate. It does not take into account factors specific to a particular environment, such the specific implementation, the type of computer system we are using, and the data that we are processing.

To determine how well or poorly a routine will perform in a particular environment, we need to evaluate the routine in that environment.

In "Part 1" of the laboratory exercise, you will measure the performance of three search routines:

• binarySearch()
• linearSearch()
• unknownSearch()
The first two search routines were discussed in CS170. For a review, click
here

In summary, for the binary search, you are given a sorted array. The idea is to divide the array into two equal parts and narrow down the range of the array to be searched either to the low part of the array or high part of the array. We will continue narrowing down the range until the value is located, or until we realize that the value searched for is not in the array.

The linear search is also known as the sequential search. The idea is start with the first element, and sequentially search through the array until we find a match.

Before we can measure the performance of these routines, we must first develop a set of tools that allow us to measure the execution time.

The general approach will be the following:

• Get the current system time (startTime)
• Execute the routine
• Get the current system time (stopTime)
• Calculate the routines's execution time=stopTime-startTime
If the routine executes very rapidly, then the difference between startTime and stopTime may be too small for your computer system to measure. If that is the case, we can execute the routine several times (say n) and then divide the resulting time by the number of repetions (n) as follows:
• Get the current system time (startTime)
• Execute the routine n times
• Get the current system time (stopTime)
• Calculate the routines's execution time = (stopTime-startTime)/n
To capture the startTime and stopTime, we will use a class called Timer which has the following member functions:
• start()
• stop()
• getElapsedTime()
To add some complexity to this lab, we will turn this Timer class into a library and use this library for the lab exercise at the end.

2. Creating a Library and Using it

This section is broken into four subsections:
• Testing that a potential library works
• Definition of a library
• Creating a library
• Using the library

2.1 Testing that a potential library works

We are going to build a library out of the Timer class, but first we want to make sure that it will work. We will download the Timer class and a sample program just to try it out

The three files are :

 complexity.cpp: This is the main program. timer.cpp: This is the implementation of the Timer module.  It can be compiled into a library once it is bug-free. timer.h: This is the header file of the Timer module

Store the three files on your local PC:

D:\Workarea

2. Compile the C++ programs

Using the procedures discussed in Lab 1 do the following:

• create a new project called lab4tst
• add the three files to this project
• build and execute this project

3. Let's have a look at this code:
• timer.h and timer.cpp are useful for calculating the running time measurements. Because we may want to use the class Timer over and over again, we may want to put it in a library.

2.2 Definition of a library

1. What is a library?

A library is a collection of functions or classes. Unlike an object file, a library file stores each function or class, individually. When your program references a function or class contained in a library, it links that function or class and adds its code to your program. This way only functions or classes that you actually use in your program are added to the executable file.

Each function or class defined in the C or C++ standard library has a header file associated with it. The header files that relate to the functions that you use in your programs should be included (using #include) in your program.
There are two reasons for this:

1. to get the data types that work with many functions or classes in the standard library. Your program must have access to these data types that are defined in the header file related to each function or class
2. to obtain the prototypes for the standard library functions

3. Why create your own Library?

Libraries can be regarded as pre-compiled functions or classes that do not need to be re-compiled if other parts of your project change. If you have a "bug-free" module (a piece of self-contained code) that could be reused with other projects, you can compile this module to a library. After you link this library to your new project, you will then be able to use any of the functions or classes in this library as if they are defined locally in your project.

One major advantage is that the functions or classes in the library will not be recompiled, which saves time compiling your entire project.

In our example, "timer" is a perfect candidate: it does not contain any bugs and we can use it again in other projects.

2.3 Creating a library

In this program, timer.h and timer.cpp define and implement a time measuring class Timer. This class is independent of the kind of program it is measuring. In other words, we can reuse this Timer class to measure the running time of other programs. It naturally follows that once we make this class bug-free, we can compile it into a library.  To use this time-measuring class, we simply include the header file (i.e.timer.h) in the program and link the library to this program.

The following shows you how we do this:

Step 1. Create the library

• Start Microsoft Visual Studio .NET
• Choose File->New->Project...
• A "New Project" Dialogue box will appear
• Expand the "Visual C++ Projects" folder and select the "Win32" sub folder
• From the "Templates" pane, select "Win32 Console Project"
• Name: mylibrary
• Location: D:\Workarea
• Click OK
• The "Win32 Application Wizard" Dialogue box will appear (see the below picture)
• Under Application Settings, choose Static library

Step 2. Add the necessary files to mylibrary and build the library

• Copy the files timer.cpp and timer.h into the mylibrary directory
• Highlight timer.cpp and timer.h
• Click Open

Step 3. Build mylibrary

• Select Build->Build mylibrary

The following message should be displayed in the output area:

------ Build started: Project: mylibrary, Configuration: Debug Win32 ------

Compiling...
timer.cpp
Creating library...

Build log was saved at "file://d:\Workarea\mylibrary\Debug\BuildLog.htm"
mylibrary - 0 error(s), 0 warning(s)

---------------------- Done ----------------------

Build: 1 succeeded, 0 failed, 0 skipped

Let's just stop for a second. We've created a libray with timer.cpp and timer.h. The library is stored in a file called mylibrary.lib, under the D:\Workarea\mylibrary\Debug folder.

We've got this library, but what do we do with it? It has member functions and data members, but we aren't making use of them--we are just defining them.

2.4 Using the library

• Choose File->New->Project...
• A "New Project" Dialogue box will appear
• Expand the "Visual C++ Projects" folder and select the "Win32" sub folder
• From the "Templates" pane select "Win32 Console Project"
• Name: lab4
• Click OK
• In the "Win32 Application Wizard" Dialogue box, select Application Settings, and check Empty project
• Copy the files complexity.cpp and timer.h into the lab4 directory (you do not need to add timer.cpp, since you have already compiled it into a library)
• Highlight complexity.cpp and timer.h, then click Open
You now have to do two things to add the library that you created to the "link line".
1. Add mylibrary.lib to the Project Properties
• From the main menu, select: Project->Properties
• A "lab4 Property Pages" Dialogue Box should be displayed (as shown below)
• Expand the Linker folder and select the Input subcategory
• Click on the "Additional Dependencies" on the right-hand side and type: mylibrary.lib
• Click OK

2. Add the corresponding path (or location of this library) to the project. The path is used to locate the library files when the VC++ project is being built.
• From the main menu, select: Tools->Options
• An "Options" Dialogue Box should appear (as shown below)
• Expand the Projects folder and select the VC++ Directories subcategory
• In the drop down menu titled "Show directories for:" select Library Files
• Click on the "New Line" icon to insert a new line. Then, type: "D:\Workarea\mylibrary\Debug" (the location where the mylibrary.lib can be found)
• Click OK

You should see the following output if you have followed the above steps correctly.
Select Build->Build lab4

------ Build started: Project: lab4, Configuration: Debug Win32 ------

Compiling...
complexity.cpp

Build log was saved at "file://d:\Workarea\lab4\Debug\BuildLog.htm"
lab4 - 0 error(s), 0 warning(s)

---------------------- Done ----------------------

Build: 1 succeeded, 0 failed, 0 skipped

Your output should look like the following:

3. Lab Exercise

There are two parts to this exercise. In the first part, you will plot the execution times of three searching routines. In the second part, you will plot the execution times of three sorting routines.

Part 1

• Get the files:
```Click here
To get the zipped files for this exercise
```
• Extract all of the files to the WORKAREA. Open the WORKAREA\exercise_runtime folder and double click on the exercise_runtime solution or project file. This will open up the project. There are three files used in this program:
• search.cpp contains the implementation of a set of searching routines.
• sort.cpp contains the implementation of a set of sorting routines (used to sort the array so that binary search will work).
• timesrch.cpp -- the main program. Outputs the runtime of the three searching routines.

1. Include the timer library into this program.
2. Compare the execution times of the three searching routines.

Steps include:

• Add timer.h to the project.
Tip: Put a copy of timer.h into the exercise directory

• Compile and run the project. You will notice that the values are printed in the following format:
```Enter the number of keys (must be at least 1000) : 1000

Search        Time per search (secs.)
--------------    -----------------------
linearSearch           2.5e-006
binarySearch           3.1e-007
unknownSearch          4.85e-006
Press any key to continue
```
The 2.5e-006 is equivalent to 2.5*10-6 or 0.0000025.

• Fill in the handout provided by your instructor.
This involves plotting the time that it takes to run the three algorithms with different numbers of keys. In the end, you will have three lines for the three searches: linear, binary, and unknown.

Suggestion: The increments for the "Search time" axis have been left up to you. First, write everthing as 10-6 seconds. Then, create five tick marks along the y-axis: 10, 20, 30, 40, and 50.

Part 2

• Get the files:
```Click here
To get the zipped files for this exercise
```
• Extract all of the files to the WORKAREA. Open the WORKAREA\exercise_timesort folder and double click on the exercise_timesort solution or project file. This will open up the project. There are two files used in this program:
• sort.cpp contains the implementation of a set of sorting routines (including selectionSort(), quickSort(), and unknownSort())
• timesort.cpp -- the main program. Outputs the runtime of the three sorting routines.

1. Include the timer library into this program.
2. Compare the execution times of the three sorting routines.

• Follow the steps outlined in Part 1 and complete the handout provided by your instructor.

Suggestion: The increments for the "Search time" axis have been left up to you. First, write everthing as 10-4 seconds. Then, create six tick marks along the y-axis: 300, 600, 900, 1200, 1500, and 1800.

4. Postlab Exercises

For postlab exercices, click
here.