Profiling Lab: Understanding Program Performance
In this exercise, you will modify an existing program to make it run faster. The program is not written for speed. You will find many things to optimize, but you should concentrate on optimizations that will make a significant impact on run time.
The
program
is all in one file called
substitute.cpp
. The purpose of the program is to perform string substitutions on a list of files. The program input is specified on the command line, for example:
substitute.exe replacements.txt file1.txt file2.txt ... fileN.txt
The first file, replacements.txt in this example, contains a list of substitutions to perform. Each string substitution is specified in 3 lines: The first line specifies a string to search for, the next line specifies the replacement string, followed by a blank line. The following is an example substitution file:
the
that
his
her
The remaining files on the command line are the files to be modified. The program reads each file, performs the substitutions one line at a time, and then writes the file. To perform a substitution, the program looks for an exact match to the first string within the file. The matching characters are replaced by the second string. Then the file is searched for another match to the first string. This match is performed on the new state of the file, so it may include characters from any previous substitution. In fact, if the replacement string contains the search string, the program will go into an infinite loop. When no more matches are found, the program moves on to the next line in the substitution file.
A good programming style would be to avoid reading in a whole file at a time because the files might be very large. For this exercise, however, you can assume that there is always enough memory to read the whole file.
Running substitute.exe
Before running substitute.exe, you need some data to run it on. Download this data , create a folder for it, and extract the files from the .zip archive. Since the program will modify some of these files, you will want to either save the .zip archive or save a copy of the files. (You will be running the program many times on this test data.)
To run substitute.exe, you can move it to a directory of your choice, create an MS-DOS command prompt window, and type in the program and command line:
substitute.exe replace.txt call.cpp compiler.cpp driver.cpp getopt.cpp jnk.cpp mach.cpp math.cpp semantics.cpp test.cpp
Profiling substitute.exe
Once everything is running (check the test files to see that the substitutions were applied), you are ready to start optimizing. The first step will be to use a profiler to find out where the program is spending its time and what it is doing with that time. Consult Appendix A Profiler Customized for SSD6 for more information about the profiler.
Your Assignment
You should make a new version of
substitute.exe
and demonstrate, using profiling output, that it runs faster. You should be able to obtain at least a factor of 2 speedup (old run time divided by new run time). You do not have to use Microsoft Foundation Class objects, but given that these are well written and probably correct, you should only replace code that is doing unnecessary work as reflected in profiler measurements.
Submit two files:
- Your modified substitute.cpp
-
A file that contains the following
- a clear but concise description of what you observed before optimization. It should be substantiated by an empirical evidence of the profiler output.
- the bottlenecks you noticed
- the actions you took to address the bottlenecks, and the improvements you observed (again substantiated by empirical evidence)
- if you had decided to continue with the next most promising code segment for optimization, what would it be? Provide reasons for why you did NOT attempt to pursue that optimization.
To verify the correctness of your solution, compare the output files produced before making any source code changes with the output files produced after making source code changes. Since your optimization should not change the external behavior of the program, the corresponding output files should be identical. If the output files differ, your solution is incorrect. You can use the "comp" command in windows to check if the contents of two files differ.
Note: If any of the files you use for this assessment are stored on a network drive, the network I/O time may dwarf the CPU time consumed by the program and may seriously affect your measurements. Make sure all your files are on the hard drive of your local machine.
Final Word
This project is for educational value only. However, you might be intrigued by the power of a string replacement engine like substitute.exe. Often, in software engineering and even web page maintenance, you will need to perform global replacement of variables, classes, and even misspellings. This is so common in large projects that there are many special tools to facilitate this job. Unix tools such as Find and SED and languages such as Awk and Perl make this kind of job simple. In fact, a SED script to replace strings in a file is not much more complicated than the "replace.txt" file read in by this project. With most tools, you can match patterns, allowing you do more powerful things such as substituting only when the search string is followed by any non-alphanumeric-that is, when the search string is not a prefix of some other identifier.
Few programmers are experts at all of these tools. Novices tend to ignore them and do things the hard way. Experienced programmers know they can learn to use another programming language, they teach themselves what they need to know on an as-needed basis, and they get the job done quickly.
