Practical C Programming, 3rd Edition (2011)
Part II. Simple Programming
Chapter 15. Debugging and Optimization
Bloody instructions which, being learned, return to plague the inventor.
—Shakespeare, on debugging [Macbeth, Act 1, Scene 7].
Debugging
The hardest part of creating a program is not its design and writing, but its debugging phase. In this phase, you find out how your program really works (instead of how you think it works).
In order to eradicate a bug, you need two things: a way of reproducing it and information from the program that lets you locate and correct the problem.
In some cases, finding the bug is easy. You discover the bug yourself, the test department produces a clear and easy test plan that displays the bug, or else the output always comes out bad.
In some cases, especially with interactive programs, reproducing the bug may be 90% of the problem. This statement is especially true when you deal with bug reports sent in by users in the field. A typical call from a user might be:
User:
That database program you gave me is broken.
Programmer:
What’s wrong?
User:
Sometimes, when I’m doing a sort, it gets things in the wrong order.
Programmer:
What command were you using?
User:
The sort command.
Programmer (patiently):
Tell me exactly what you typed, keystroke by keystroke, to get it to fail.
User:
I don’t remember it exactly. I was doing a lot of sorts.
Programmer:
If I come over can you show me the bug?
User:
Of course.
Two minutes later, the programmer is in the user’s office and utters the fatal words, “Show me.” The user types away and the program stubbornly works, no matter what the user does to it.
The programmer gives up and goes back to her office only to find a message from the user: “It failed five minutes after you left.”
Example 15-1 is a short database lookup program. It asks the user for input and checks the input against a hardcoded list of names. Although very simple, the program’s structure is typical of much larger and more complex interactive programs.
Example 15-1. base/base.c
/********************************************************
* Database -- A very simple database program to *
* look up names in a hardcoded list. *
* *
* Usage: *
* database *
* Program will ask you for a name. *
* Enter the name; it will tell you if *
* the name is in the list. *
* *
* A blank name terminates the program. *
********************************************************/
#define STRING_LENGTH 80 /* Length of typical string */
#include <stdio.h>
#include <string.h>
int main()
{
char name[STRING_LENGTH]; /* a name to lookup */
int lookup(char const *const name); /* lookup a name */
while (1) {
printf("Enter name: ");
fgets(name, sizeof(name), stdin);
/* Check for blank name */
/* (remember 1 character for newline) */
if (strlen(name) <= 1)
break;
/* Get rid of newline */
name[strlen(name)-1] = '\0';
if (lookup(name))
printf("%s is in the list\n", name);
else
printf("%s is not in the list\n", name);
}
return (0);
}
/********************************************************
* lookup -- Looks up a name in a list. *
* *
* Parameters *
* name -- Name to look up. *
* *
* Returns *
* 1 -- Name in the list. *
* 0 -- Name not in the list. *
********************************************************/
int lookup(char const *const name)
{
/* List of people in the database */
/* Note: Last name is a NULL for end of list */
static char *list[] = {
"John",
"Jim",
"Jane",
"Clyde",
NULL
};
int index; /* index into list */
for (index = 0; list[index] != NULL; ++index) {
if (strcmp(list[index], name) == 0)
return (1);
}
return (0);
}
A typical execution of this program is:
Enter name:Sam
Sam is not in the list
Enter name: John
John is in the list
Enter name:
When we release this program, of course, the users immediately start complaining about mysterious problems that go away whenever the programmer is around. Wouldn’t it be nice to have a little gremlin that sits on the shoulder, copying down everything the user types? Unfortunately, gremlins are not available; however, we can change this program so that it produces a save file that contains every keystroke that the user typed in.
Our program uses the statement:
fgets(name, sizeof(name), stdin);
to read the user’s data.
Let’s write a new routine, extended_fgets, and use it instead of fgets. It not only gets a line, but also saves the user’s response in a save file. Example 15-2 is a revision of Example 15-1 that includes extended_fgets.
Example 15-2. xgets/xgets.c
#include <stdio.h>
/*
* The main program opens this file if -S is on
* the command line.
*/
FILE *save_file = NULL;
/*********************************************************
* extended_fgets -- Gets a line from the input file *
* and records it in a save file if needed. *
* *
* Parameters *
* line -- The line to read. *
* size -- sizeof(line) -- maximum number of *
* characters to read. *
* file -- File to read data from *
* (normally stdin). *
* *
* Returns *
* NULL -- error or end-of-file in read *
* otherwise line (just like fgets). *
*********************************************************/
char *extended_fgets(char *line, int size, FILE *file)
{
char *result; /* result of fgets */
result = fgets(line, size, file);
/* Did someone ask for a save file?? */
if (save_file != NULL)
fputs(line, save_file); /* Save line in file */
return (result);
}
We also change our main program to handle a new option, -Sfile, to specify a save file. (Typically, uppercase letters are used for debugging and other less used options.) Our new main program is shown in Example 15-3.
Example 15-3. base2/base2.c
[File: base2/base2.c]
/*********************************************************
* Database -- A very simple database program to *
* look up names in a hardcoded list. *
* *
* Usage: *
* database [-S<file>] *
* *
* -S<file> Specifies save file for *
* debugging purposes *
* *
* Program will ask you for a name. *
* Enter the name; program will tell you if *
* it is in the list. *
* *
* A blank name terminates the program. *
*********************************************************/
#include <stdio.h>
#include <stdlib.h>
FILE *save_file = NULL; /* Save file if any */
char *extended_fgets(char *, int, FILE *);
int main(int argc, char *argv[])
{
char name[80]; /* a name to lookup */
char *save_file_name; /* Name of the save file */
int lookup(char const *const name); /* lookup a name */
while ((argc > 1) && (argv[1][0] == '-')) {
switch (argv[1][1]) {
/* -S<file> Specify a save file */
case 'S':
save_file_name = &argv[1][2];
save_file = fopen(save_file_name, "w");
if (save_file == NULL)
fprintf(stderr,
"Warning:Unable to open save file %s\n",
save_file_name);
break;
default:
fprintf(stderr,"Bad option: %s\n", argv[1]);
exit (8);
}
--argc;
++argv;
}
while (1) {
printf("Enter name: ");
extended_fgets(name, sizeof(name), stdin);
/* ... Rest of program ... */
}
}
Now we have a complete record of what the user typed. Looking at the input, we see that the user typed:
Sam
John
The second name begins with a space and although “John” is in the list, “<space>John” is not. In this case, we found the error by inspecting the input; however, more complex programs have much more complex input. We could type all that in when debugging, or we could add another feature to extended_fgets that would add playback file to it. When enabled, input will not be taken from the keyboard, but instead will be taken from the file. Example 15-4 contains the revised extended_fgets.
Example 15-4. xgets2/xgets2.c
#include <stdio.h>
FILE *save_file = NULL; /* Save input in this file */
FILE *playback_file = NULL; /* Playback data from this file */
/*********************************************************
* extended_fgets -- Gets a line from the input file *
* and records it in a save file if needed. *
* *
* Parameters *
* line -- The line to read. *
* size -- sizeof(line) -- maximum number of *
* characters to read. *
* file -- File to read data from *
* (normally stdin). *
* *
* Returns *
* NULL -- error or end-of-file in read *
* otherwise line (just like fgets). *
*********************************************************/
char *extended_fgets(char *line, int size, FILE *file)
{
extern FILE *save_file; /* file to save strings in */
extern FILE *playback_file; /* file for alternate input */
char *result; /* result of fgets */
if (playback_file != NULL) {
result = fgets(line, size, playback_file);
/* echo the input to the standard out so the user sees it */
fputs(line, stdout);
} else
/* Get the line normally */
result = fgets(line, size, file);
/* Did someone ask for a save file? */
if (save_file != NULL)
fputs(line, save_file); /* Save the line in a file */
return (result);
}
We also add a playback option to the command line -Pfile. This option allows us to automatically type the commands that caused the error. Our main program, revised to support the -P option, is Example 15-5.
Example 15-5. base3/base3.c
/*********************************************************
* Database -- A very simple database program to *
* look up names in a hardcoded list. *
* *
* Usage: *
* database [-S<file>] [-P<file>] *
* *
* -S<file> Specifies save file for *
* debugging purposes. *
* *
* -P<file> Specifies playback file for *
* debugging or demonstration. *
* *
* *
* Program will ask you for a name. *
* Enter the name; the program will tell *
* you if it is in the list. *
* *
* A blank name terminates the program. *
*********************************************************/
#include <stdio.h>
#include <stdlib.h>
FILE *save_file = NULL; /* Save file if any */
FILE *playback_file = NULL; /* Playback file if any */
char *extended_fgets(char *, int, FILE *);
int main(int argc, char *argv[])
{
char name[80]; /* a Name to look up */
char *save_file_name; /* Name of the save file */
char *playback_file_name; /* Name of the playback file */
int lookup(char const *const name); /* lookup a name */
while ((argc > 1) && (argv[1][0] == '-')) {
switch (argv[1][1]) {
/* -S<file> Specify save file */
case 'S':
save_file_name = &argv[1][2];
save_file = fopen(save_file_name, "w");
if (save_file == NULL)
fprintf(stderr,
"Warning:Unable to open save file %s\n",
save_file_name);
break;
/* -P<file> Specify playback file */
case 'P':
playback_file_name = &argv[1][2];
playback_file = fopen(playback_file_name, "r");
if (playback_file == NULL) {
fprintf(stderr,
"Error:Unable to open playback file %s\n",
playback_file_name);
exit (8);
}
break;
default:
fprintf(stderr,"Bad option: %s\n", argv[1]);
exit (8);
}
--argc;
++argv;
}
/* ... rest of program ... */
return (0);
}
Now, when a user calls up with an error report, we can tell him, “Try it again with the save-file feature enabled, and then send me a copy of your files.” The user then runs the program and saves the input into the file save.txt:
%database -Ssave.txt
Enter name: Sam
Sam is not in the list
Enter name: John
John is in the list
Enter name:
He sends us the file save.txt, and we run the program with the playback option enabled:
%database -Psave.txt
Enter name: Sam
Sam is not in the list
Enter name: John
John is in the list
Enter name:
We now have a reliable way of reproducing the problem. In many cases, that’s half the battle. After we can reproduce the problem, we can proceed to find and fix the bugs.
A COPY FLIP-FLOP
Once a programmer asked a user to send him a copy of his floppy. A next-day air package arrived at the programmer’s desk containing a photocopy of the floppy. The user was not completely computer illiterate. He knew it was a two-sided floppy, so he had photocopied both sides.
Before you start debugging, save the old, “working” copy of your program in a safe place. (If you are using a source control system like SCCS or RCS, your last working version should be checked in.) Many times while you are searching for a problem, you may find it necessary to try out different solutions or to add temporary debugging code. Sometimes you find you’ve been barking up the wrong tree and need to start over. That’s when the last working copy becomes invaluable.
After you have reproduced the problem, you must determine what caused it to happen. There are several methods for doing this, as described in the following sections.
Divide and Conquer
The divide-and-conquer method has already been briefly discussed in Chapter 6. This method consists of putting in printf statements where you know the data is good (to make sure it is really good), where the data is bad, and at several points in between. In this manner you can start zeroing in on the section of code that contains the error. More printf statements can further reduce the scope of the error until the bug is finally located.
Debug-Only Code
The divide-and-conquer method uses temporary printf statements. They are put in as needed and taken out after they are used. The preprocessor conditional compilation directives can be used to put in and take out debugging code. For example:
#ifdef DEBUG
printf("Width %f Height %f\n", width, height);
#endif /* DEBUG */
The program can be compiled with DEBUG undefined for normal use; you can define it when debugging is needed.
Debug Command-Line Switch
Rather than using a compile-time switch to create a special version of the program, you can permanently include the debugging code and add a special program switch that will turn on the debugging output. For example:
if (debug)
printf("Width %f Height %f\n", width, height);
In the debug example, debug is a variable that is set if -D is present on the command line.
This method has the advantage that only a single version of the program exists. Also, the customer can turn on this switch in the field, save the output, and send it to you for analysis. The method has a disadvantage, though: a larger executable file. The runtime switch should always be used instead of conditional compilation unless there is some reason that you do not want the customer to be able to get at the debugging information.
Some programs use the concept of a debug level. Level outputs only minimal debugging information, level 1 more information, and so on up to level 9, which outputs everything.
The ghostscript[17] program by Aladdin Enterprises implements the idea of debugging letters. The command option -Zxxx sets the debugging flags for each type of diagnostic output wanted. For example, f is the code for the fill algorithm, while p is the code for the path tracer. If I wanted to trace both these sections, I would specify -Zfp.
The option is implemented by the following code:
/*
* Even though we only used one zero, C will fill in the
* rest of the arrays with zeros.
*/
char debug[128] = {0}; /* the debugging flags */
main(int argc, char *argv[])
{
while ((argc > 1) && (argv[1][0] == '-')) {
switch (argv[1][1]) {
/* .... normal switch .... */
/* Debug switch */
case 'Z':
debug_ptr = argv[1][2];
/* loop for each letter */
while (*debug_ptr != '\0') {
debug[*debug_ptr] = 1;
debug_ptr++;
}
break;
}
argc--;
argv++;
}
/* rest of program */
}
This is used inside the program by:
if (debug['p'])
printf("Starting new path\n");
ghostscript is a large program (some 25,000 lines) and rather difficult to debug. This form of debugging allows the user to get a great deal of information easily.
Going Through the Output
Enabling the debug printout is a nice way of getting information, but at many times, there is so much data that the information you want can easily get lost.
C allows you to redirect to a file what would normally go to the screen. For example:
buggy -D9 >tmp.out
runs the program buggy with a high level of debugging and sends the output to the file tmp.out.
The text editor on your system makes a good file browser. You can use its search capabilities to look for the information you want to find.
[17] ghostscript is a PostScript-like interpreter available from the Free Software Foundation for a minimal copying charge. They can be reached at: Free Software Foundation, Inc., 675 Massachusetts Avenue, Cambridge, MA 02139 (617) 876-3296. Their ftp site is prep.ai.mit.edu:/pub/gnu.
Interactive Debuggers
Most compiler manufacturers provide you with an interactive debugger. These debuggers give you the ability to stop the program at any point, examine and change variables, and “single step” through the program. Because each debugger is different, a detailed discussion is not possible.
However, we are going to discuss one debugger, dbx. This program is available on many UNIX machines running the BSD versions of UNIX. On LINUX in particular and other UNIX systems, the Free Software Foundations gdb debugger is popular. SYSTEM-V UNIX uses the debugger sdb, while on HP-UX, the utility cdb is used. Each MS-DOS/Windows compiler has its own debugger. Some compilers actually come with multiple debuggers. For example, Borland C++ comes with a integrated debugger that runs under Windows, a stand-alone debugger that runs under MS-DOS, and a remote debugger that runs on another machine.
Although the exact syntax used by your debugger may be different, the principles shown here will work for all debuggers.
The basic list of dbx commands are:
run
Start execution of a program.
stop at line-number
Insert a breakpoint at the given line number. When a running program reaches a breakpoint, execution stops and control returns to the debugger.
stop in function-name
Insert a breakpoint at the first line of the named function. Commonly, the command stop in main is used to stop at the beginning of the program.
cont
Continue execution after a breakpoint.
print expression
Display the value of an expression.
step
Execute a single line in the program. If the current statement calls a function, the function is single-stepped.
next
Execute a single line in the program, but treat function calls as a single line. This command is used to skip over function calls.
list
List the source program.
where
Print the list of currently active functions.
We have a program that should count the number of threes and sevens in a series of numbers. Unfortunately, it keeps getting the wrong answer for the number of sevens. Our program is shown in Example 15-6. Your results may vary.
Example 15-6. seven/seven.c
1 #include <stdio.h>
2 char line[100]; /* line of input */
3 int seven_count; /* number of sevens in the data */
4 int data[5]; /* the data to count 3 and 7 in */
5 int three_count; /* the number of threes in the data */
6 int index; /* index into the data */
7
8 int main() {
9
10 seven_count = 0;
11 three_count = 0;
12 get_data(data);
13
14 for (index = 1; index <= 5; ++index) {
15
16 if (data[index] == 3)
17 ++three_count;
18
19 if (data[index] == 7)
20 ++seven_count;
21 }
22
23 printf("Threes %d Sevens %d\n",
24 three_count, seven_count);
25 return (0);
26 }
27
28 void get_data(int data)
29 {
30
31 printf("Enter 5 numbers\n");
32 fgets(line, sizeof(line), stdin);
33 sscanf(line, "%d %d %d %d %d",
34 &data[1], &data[2], &data[3],
35 &data[4], &data[5]);
36 }
When we run this program with the data 7 3 7 0 2, the results are:
Threes 1 Sevens 4
We start by invoking the debugger (dbx) with the name of the program we are going to debug (seven). The debugger initializes itself, outputs the prompt (dbx), and waits for a command:
%dbx seven
Reading symbolic information...
Read 72 symbols
(dbx)
We don’t know where the variable is getting changed, so we’ll start at the beginning and work our way through until we get an error. At every step, we’ll display the variable seven_count just to make sure it’s OK.
We need to stop the program at the beginning so that we can single-step through it. The command stop in main tells dbx to set a breakpoint at the first instruction of the function main. The command run tells dbx to start the program and run until it hits the first breakpoint:
(dbx)stop in main
(2) stop in main
The number (2) is used by dbx to identify the breakpoint. Now we need to start the program:
(dbx)run
Running: seven
stopped in main at line 10 in file "/usr/sdo/seven/seven.c"
10 seven_count = 0;
The message “stopped in main...” indicates that the program encountered a breakpoint and the debugger now has control.
We have reached the point where seven_count is initialized. The command next will execute a single statement, treating function calls as one statement. (The names of the command for your debugger may be different.) We go past the initialization and check to see if it worked:
(dbx)next
stopped in main at line 11 in file "/usr/sdo/seven/seven.c"
11 three_count = 0;
(dbx) print seven_count
seven_count = 0
It did. We try the next few lines, checking all the time:
(dbx)next
stopped in main at line 12 in file "/usr/sdo/seven/seven.c"
12 get_data(data);
(dbx) print seven_count
seven_count = 0
(dbx) next
Enter 5 numbers
3 7 3 0 2
stopped in main at line 14 in file "/usr/sdo/seven/seven.c"
14 for (index = 1; index <= 5; index++) {
(dbx) print seven_count
seven_count = 2
seven_count somehow changed value to 2. The last statement we executed was get_data(data), so something is going on in that function. We add a breakpoint at the beginning of get_data and start the program over with the run command:
(dbx)stop in get_data
(4) stop in get_data
(dbx) run
Running: seven
stopped in main at line 10 in file "/usr/sdo/seven/seven.c"
10 seven_count = 0;
We are at the beginning of main. We want to go onto the next breakpoint, so we issue the cont command to continue execution:
(dbx)cont
Running: seven
stopped in get_data at line 31 in file "/usr/sdo/seven/seven.c"
31 printf("Enter 5 numbers\n");
We now start single stepping again until we find the error:
(dbx)print seven_count
seven_count = 0
(dbx) next
Enter 5 numbers
stopped in get_data at line 32 in file "/usr/sdo/seven/seven.c"
32 fgets(line, sizeof(line), stdin);
(dbx) print seven_count
seven_count = 0
(dbx) next
1 2 3 4 5
stopped in get_data at line 33 in file "/usr/sdo/seven/seven.c"
35 &data[4], &data[5]);
(dbx) print seven_count
seven_count = 0
(dbx) next
stopped in get_data at line 36 in file "/usr/sdo/seven/seven.c"
36 }
(dbx) print seven_count
seven_count = 5
(dbx) list 30,40
30
31 printf("Enter 5 numbers\n");
32 fgets(line, sizeof(line), stdin);
33 sscanf(line, "%d %d %d %d %d",
34 &data[1], &data[2], &data[3],
35 &data[4], &data[5]);
36 }
(dbx)quit
At line 32, the data was good, but when we reached line 36, the data was bad, so the error is located at line 33 of the program, the sscanf. We’ve narrowed the problem down to one statement. By inspection we can see that we are using data[5], an illegal member of the array data.
The computer happened to store seven_count after the data array, so that is why (confusingly enough) the problem turned up there. It would be nice if we could get a clear error message whenever we step outside the declared array, but bounds checking is time consuming and difficult in C. There are some specialized debugging tools such as Bounds-Checker by Nu-Mega (MS-DOS/ Windows) and Purify by Pure Software (UNIX).
Debugging a Binary Search
The binary search algorithm is fairly simple. You want to see if a given number is in an ordered list. Check your number against the one in the middle of the list. If it is the number, you were lucky -- stop. If your number was bigger, then you might find it in the top half of the list; try the middle of the top half. If it was smaller, try the bottom half. Keep trying and dividing the list in half until you find the number or the list gets down to a single number.
Example 15-7 uses a binary search to see if a number can be found in the file numbers.dat.
Example 15-7. search/search1.c
[File: search/search1.c]
/********************************************************
* search -- Searches a set of numbers. *
* *
* Usage: *
* search *
* You will be asked numbers to look up. *
* *
* Files: *
* numbers.dat -- Numbers 1 per line to search *
* (numbers must be ordered). *
********************************************************/
#include <stdio.h>
#define MAX_NUMBERS 1000 /* Max numbers in file */
const char DATA_FILE[] = "numbers.dat"; /* File with numbers */
int data[MAX_NUMBERS]; /* Array of numbers to search */
int max_count; /* Number of valid elements in data */
int main()
{
FILE *in_file; /* Input file */
int middle; /* Middle of our search range */
int low, high; /* Upper/lower bound */
int search; /* Number to search for */
char line[80]; /* Input line */
in_file = fopen(DATA_FILE, "r");
if (in_file == NULL) {
fprintf(stderr,"Error:Unable to open %s\n", DATA_FILE);
exit (8);
}
/*
* Read in data
*/
max_count = 0;
while (1) {
if (fgets(line, sizeof(line), in_file) == NULL)
break;
/* convert number */
sscanf(line, "%d", data[max_count]);
++max_count;
}
while (1) {
printf("Enter number to search for or -1 to quit:" );
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &search);
if (search == -1)
break;
low = 0;
high = max_count;
while (1) {
middle = (low + high) / 2;
if (data[middle] == search) {
printf("Found at index %d\n", middle);
}
if (low == high) {
printf("Not found\n");
break;
}
if (data[middle] < search)
low = middle;
else
high = middle;
}
}
return (0);
}
Our data file, numbers.dat, contains:
4
6
14
16
17
When we run this program, the results are:
%search
Segmentation fault (core dumped)
These results are not good. They mean that something went wrong in our program and it tried to read memory that wasn’t there. A file called core was created when the error occurred. It contains a snapshot of our executing program. The debugger dbx can read this file and help us determine what happened:
%dbx search
Reading symbolic information...
Read 79 symbols
warning: core file read error: address not in data space
warning: core file read error: address not in data space
warning: core file read error: address not in data space
program terminated by signal SEGV (no mapping at the fault address)
(dbx)
The message “warning: core file...” is the debugger’s way of telling you that the temporary variable space (the stack) has been trashed and contains bad data. The where command tells you which function is calling which function (also known as a stack trace). The current function is printed first, then the function that called it, and so on until we reach the outer function main:
(dbx)where
number() at 0xdd7d87a
_doscan() at 0xdd7d329
sscanf(0xdfffadc, 0x200e3, 0x0) at 0xdd7ce7f
main(0x1, 0xdfffb58, 0xdfffb60), line 41 in "search.c"
(dbx)
The above example tells us that main called sscanf. The call was made from line 41 of main. sscanf called _doscan. Because sscanf is a standard library routine, we cannot get line-number information. The instruction number is 0xdd7ce7f; however, this information is not very useful to us. The procedure _doscan called number. number was what tried to perform the illegal memory access.
This information does not mean that there is a bug in number. The problem could be caused by the parameters passed to number by _doscan, which could have gotten parameters from sscanf, which got parameters from main. Any one of the functions along this chain could contain an error that caused a bad pointer to be passed to another function.
Usually the standard library has been debugged, so we should probably look for the error in our code. Looking at the stack trace, we see that the last line of our program to be executed was line 41 of main.
Using the list command, we can examine that line:
(dbx)list 41
41 sscanf(line, "%d", data[max_count]);
(dbx)
This line caused the problem.
Another way of finding the problem is to single-step the program until the error occurs. First, we list a section of the program to find a convenient place to put the breakpoint, then start the execution and the single-step process:
(dbx)list 26,31
22 int low, high; /* Upper/lower bound */
23 int search; /* Number to search for */
24 char line[80]; /* Input line */
25
26 in_file = fopen(DATA_FILE, "r");
27 if (in_file == NULL) {
28 fprintf(stderr,"Error:Unable to open %s\n",
DATA_FILE);
29 exit (8);
30 }
31
(dbx) stop at 26
(1) stop at "search.c":26
(dbx) run
Running: search
stopped in main at line 26 in file "search.c"
26 in_file = fopen(DATA_FILE, "r");
(dbx) step
stopped in main at line 27 in file "search.c"
27 if (in_file == NULL) {
(dbx) step
stopped in main at line 35 in file "search.c"
35 max_count = 0;
(dbx) step
stopped in main at line 37 in file "search.c"
37 if (fgets(line, sizeof(line), in_file) == NULL)
(dbx) step
stopped in main at line 41 in file "search.c"
41 sscanf(line, "%d", data[max_count]);
(dbx) step
signal SEGV (no mapping at the fault address) in number at 0xdd7d87a
number+0x520: movl a6@(0x1c),a0
(dbx) quit
This method also points at line 41 as the culprit. On inspection, we notice that we forgot to put an ampersand (&) in front of the variable for sscanf. So we change line 41 from:
sscanf(line, "%d", data[max_count]);
to:
sscanf(line, "%d", &data[max_count]);
and try again. The first number in our list is 4, so we try it. This time our output looks like:
Enter number to search for or -1 to quit:4
Found at index 0
Found at index 0
Not found
Enter number to search for or -1 to quit:^C
The program should find the number, let us know it’s at index 0, and then ask for another number. Instead, we get two “found” messages and one “not found” message. We know that everything is running smoothly up until we get the first “found” message. After that point, things go downhill. So we have at least one more bug in our program.
Getting back into the debugger, we use the list command to locate the found message and put a breakpoint there:
%dbx search
Reading symbolic information...
Read 79 symbols
(dbx) list 58,60
58
59 if (data[middle] == search) {
60 printf("Found at index %d\n", middle);
61 }
62
63 if (low == high) {
64 printf("Not found\n");
65 break;
66 }
67
(dbx) stop at 60
(3) stop at "search.c":60
(dbx) run
stopped in main at line 60 in file "search.c"
60 printf("Found at index %d\n", middle);
(dbx)
Now we start single-stepping to see what happens:
60 printf("Found at index %d\n", middle);
(dbx)step
Found at index 0
stopped in main at line 63 in file "search.c"
63 if (low == high) {
(dbx) step
stopped in main at line 68 in file "search.c"
68 if (data[middle] < search)
(dbx) step
stopped in main at line 71 in file "search.c"
71 high = middle;
(dbx) step
stopped in main at line 57 in file "search.c"
57 middle = (low + high) / 2;
(dbx)quit
The program doesn’t exit the loop. Instead, it continues with the search. Because the number has already been found, in strange behavior results. We are missing a break after the printf.
We need to change:
if (data[middle] == search) {
printf("Found at index %d\n", middle);
}
to:
if (data[middle] == search) {
printf("Found at index %d\n", middle);
break;
}
Making this fix, we try our program again:
%search
Enter number to search for or -1 to quit:4
Found at index 0
Enter number to search for or -1 to quit:6
Found at index 1
Enter number to search for or -1 to quit:3
Not found
Enter number to search for or -1 to quit:5
...program continues forever or until we abort it...
We have a runaway program. This time, instead of setting a breakpoint, we just start running the program. After a few seconds pass and we believe that we are stuck in the infinite loop, we stop the program with a CTRL-C to return to the shell prompt. Because we are running with the debugger, control returns to dbx:
%dbx search
Reading symbolic information...
Read 80 symbols
(dbx) run
Running: search
Enter number to search for or -1 to quit:5
^C
interrupt in main at line 70 in file "search.c"
70 low = middle;
Now we can use the single-step command to step through our infinite loop, looking at key values along the way:
70 low = middle;
(dbx)step
stopped in main at line 57 in file "search.c"
57 middle = (low + high) / 2;
(dbx) step
stopped in main at line 59 in file "search.c"
59 if (data[middle] == search) {
(dbx) print middle
middle = 0
(dbx) print data[middle]
data[middle] = 4
(dbx) print search
search = 5
(dbx) step
stopped in main at line 64 in file "search.c"
64 if (low == high) {
(dbx) step
stopped in main at line 69 in file "search.c"
69 if (data[middle] < search)
(dbx) step
stopped in main at line 70 in file "search.c"
70 low = middle;
(dbx) step
stopped in main at line 57 in file "search.c"
57 middle = (low + high) / 2;
(dbx) step
stopped in main at line 59 in file "search.c"
59 if (data[middle] == search) {
(dbx) step
stopped in main at line 64 in file "search.c"
64 if (low == high) {
(dbx) step
stopped in main at line 69 in file "search.c"
69 if (data[middle] < search)
(dbx) step
stopped in main at line 70 in file "search.c"
70 low = middle;
(dbx) step
stopped in main at line 57 in file "search.c"
57 middle = (low + high) / 2;
(dbx) step
stopped in main at line 59 in file "search.c"
59 if (data[middle] == search) {
(dbx) step
stopped in main at line 64 in file "search.c"
64 if (low == high) {
(dbx) step
stopped in main at line 69 in file "search.c"
69 if (data[middle] < search)
(dbx) print low,middle,high
low = 0
middle = 0
high = 1
(dbx) print search
search = 5
(dbx) print data[0], data[1]
data[0] = 4
data[1] = 6
(dbx)quit
The problem is that we have reached a point where:
low= 0
middle= 0
high= 1
The item we are seeking (value 5) falls between element (value 4) and element 1 (value 6). Our algorithm has an off-by-one error. This type of error occurs when one variable in a program is just one off the value it should have. In this case, the variable is our index middle.
We have narrowed our search to the interval to 1. We then take the middle of this interval. But our algorithm is flawed. Because the interval is so small, the “middle” works out to be element 1. So we “narrow” our search from to 1 to the new interval to 1, and start over. Because this interval is what we started out with, we have an infinite loop.
To solve this problem, we look at the code. If the middle element matches, we print out a “found” message and exit. That fact means that we don’t need to search the middle element again. So, we adjust our code from:
if (data[middle] < search)
low = middle;
else
high = middle;
to:
if (data[middle] < search)
low = middle +1;
else
high = middle -1;
The full version of our corrected program is shown in Example 15-8.
Example 15-8. search/search4.c
[File: search/search4.c]
/********************************************************
* search -- Searches a set of numbers. *
* *
* Usage: *
* search *
* You will be asked numbers to look up. *
* *
* Files: *
* numbers.dat -- Numbers 1 per line to search *
* (Numbers must be ordered). *
********************************************************/
#include <stdio.h>
#define MAX_NUMBERS 1000 /* Max numbers in file */
const char DATA_FILE[] = "numbers.dat"; /* File with numbers */
int data[MAX_NUMBERS]; /* Array of numbers to search */
int max_count; /* Number of valid elements in data */
int main()
{
FILE *in_file; /* Input file */
int middle; /* Middle of our search range */
int low, high; /* Upper/lower bound */
int search; /* number to search for */
char line[80]; /* Input line */
in_file = fopen(DATA_FILE, "r");
if (in_file == NULL) {
fprintf(stderr,"Error:Unable to open %s\n", DATA_FILE);
exit (8);
}
/*
* Read in data
*/
max_count = 0;
while (1) {
if (fgets(line, sizeof(line), in_file) == NULL)
break;
/* convert number */
sscanf(line, "%d", &data[max_count]);
++max_count;
}
while (1) {
printf("Enter number to search for or -1 to quit:" );
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &search);
if (search == -1)
break;
low = 0;
high = max_count;
while (1) {
if (low >= high) {
printf("Not found\n");
break;
}
middle = (low + high) / 2;
if (data[middle] == search) {
printf("Found at index %d\n", middle);
break;
}
if (data[middle] < search)
low = middle +1;
else
high = middle -1;
}
}
return (0);
}
Interactive debuggers work well for most programs. Sometimes they need a little help. Consider Example 15-9. We try to debug it and find it fails when point_number is 735. We want to put a breakpoint before the calculation is made. When the debugger inserts a breakpoint into a program, the program will execute normally until it hits the breakpoint, then control will return to the debugger. This allows the user to examine and change variables as well as perform other debugging commands. When a continue command is typed, the program will continue execution as if nothing had happened. The problem is that there are 734 points before the one we want, and we don’t want to stop for each of them.
Example 15-9. cstop/cstop.c
extern float lookup(int index);
float point_color(int point_number)
{
float correction; /* color correction factor */
extern float red,green,blue;/* current colors */
correction = lookup(point_number);
return (red*correction * 100.0 +
blue*correction * 10.0 +
green*correction);
}
How do we force the debugger to stop only when part_number == 735? We can do this by adding the following temporary code:
48 if (point_number == 735) /* ### Temp code ### */
49 point_number = point_number; /* ### Line to stop on ### */
Line 49 does nothing useful except serve a line that the debugger can stop on. We can put a breakpoint on that line with the command stop at 49. The program will process the first 734 points, then execute line 49, hitting the breakpoint. (Some debuggers have a conditional breakpoint. The advanced dbx command stop at 49 if point_number == 735 would also work; however, your debugger may not have such advanced features.)
Runtime Errors
Runtime errors are usually the easiest to fix. Some types of runtime errors are:
§ Segmentation Violation. This error indicates that the program tried to dereference a pointer containing a bad value.
§ Stack Overflow. The program tried to use too many temporary variables. Sometimes, stack overflow happens because the program is too big or is using too many big temporary arrays, but most of the time this is due to infinite recursion problems. Almost all UNIX systems automatically check for this error. Turbo C++ and Borland C++ check for stack overflow only if the compile-time option -N is used.
§ Divide by 0. Divide by is an obvious error. UNIX masks the problem by reporting an integer divide by zero with the error message “Floating exception (core dumped).”
All these errors stop program execution. On UNIX, an image of the running program, called a core file, is written out.
One problem with runtime errors is that when they occur, the program execution stops immediately. The buffers for buffered files are not flushed. This can lead to some unexpected surprises. Consider Example 15-10.
Example 15-10. flush/flush.c
#include <stdio.h>
int main()
{
int i,j; /* two random integers */
i = 1;
j = 0;
printf("Starting\n");
printf("Before divide...");
i = i / j; /* divide by zero error */
printf("After\n");
return(0);
}
When run, this program outputs the following:
Starting
Floating exception (core dumped)
This program might lead you to think the divide had never started, when in fact it had. What happened to the message “Before divide...”? The printf statement executed and put the message in a buffer, and then the program died. The buffer never got a chance to be emptied.
By putting explicit flush buffer commands inside the code, we get a truer picture of what is happening. See Example 15-11.
Example 15-11. flush2/flush2.c
[File: flush2/flush2.c]
#include <stdio.h>
int main()
{
int i,j; /* two random integers */
i = 1;
j = 0;
printf("Starting\n");
fflush(stdout);
printf("Before divide...");
fflush(stdout);
i = i / j; /* divide by zero error */
printf("After\n");
fflush(stdout);
return(0);
}
The flush statement makes the I/O less efficient, but more current.
The Confessional Method of Debugging
The confessional method of debugging is one in which the programmer explains the program to someone: an interested party, an uninterested party, a wall—the actual recipient is not important, as long the programmer talks about the program.
A typical confessional session goes like this: “Hey Bill, could you take a look at this. My program has a bug in it. The output should be 8.0 and I’m getting -8.0. The output is computed using this formula and I’ve checked out the payment value and rate, and the date must be correct unless there is something wrong with the leap year code, which—Thank you, Bill, you’ve found my problem.” Bill never says a word.
This type of debugging is also called a “walkthrough.” Getting other people involved brings a fresh point of view to the process, and frequently, other people can spot problems that you have overlooked.
Optimization
Optimization is the art of going through a program and making the code more efficient so that it runs faster. Most compilers have a command-line switch that causes them to generate optimized code. This efficiency comes at the cost of compile time; the compiler takes a lot longer to generate code when optimization is turned on.
The other type of optimization occurs when a programmer modifies a program to use a more efficient algorithm. This section discusses this second type of optimization.
And now a word on optimization: don’t. Most programs do not need to be optimized. They run fast enough. Who cares if an interactive program takes 0.5 seconds to start up instead of 0.2?
The simplest way to get your program to run faster is to get a faster computer. Many times buying a more powerful machine is cheaper than optimizing a program, and possibly introducing new errors into your code. Don’t expect miracles from optimization. Usually most programs can be sped up by only 10% to 20%.
Still, to give you an idea what you can accomplish, I’ll optimize a sample function. Example 15-12 initializes a matrix (two-dimensional array).
Example 15-12. matrix/matrix1.c
[File: matrix/matrix1.c]
#define X_SIZE 60
#define Y_SIZE 30
/* A random matrix */
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
int x,y; /* current element to zero */
for (x = 0; x < X_SIZE; ++x) {
for (y = 0; y < Y_SIZE; ++y) {
matrix[x][y] = -1;
}
}
}
How can this function be optimized? First, we notice that we are using two local variables. By using the qualifier register on these variables, we tell the compiler that they are frequently used and should be placed in fast registers instead of relatively slow main memory. The number of registers varies from computer to computer. Slow machines like the PC have two registers, most UNIX systems have about 11, and supercomputers can have as many as 128. You can declare more register variables than you have registers. C will put the extra variables in main memory.
Our program now looks like Example 15-13.
Example 15-13. matrix/matrix2.c
[File: matrix/matrix2.c]
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
register int x,y; /* current element to zero */
for (x = 0; x < X_SIZE; ++x) {
for (y = 0; y < Y_SIZE; ++y) {
matrix[x][y] = -1;
}
}
}
The outer loop is executed 60 times. This means that the overhead associated with starting the inner loop is executed 60 times. If we reverse the order of the loops, we will have to deal with the inner loop only 30 times.
In general, loops should be ordered so that the innermost loop is the most complex and the outermost loop is the simplest, as in Example 15-14.
Example 15-14. matrix/matrix3.c
[File: matrix/matrix3.c]
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
register int x,y; /* current element to zero */
for (y = 0; y < Y_SIZE; ++y) {
for (x = 0; x < X_SIZE; ++x) {
matrix[x][y] = -1;
}
}
}
The Power of Powers of 2
Indexing an array requires a multiply. Look at the following line from the previous example:
matrix[x][y] = -1;
To get the location where the -1 will be stored, the program must perform the following steps:
1. Get the address of the matrix.
2. Compute x * Y_SIZE.
3. Compute y.
4. Add up all three parts to form the address.
In C, this code looks like:
*(matrix + (x * Y_SIZE) + y) = -1;
However, we typically don’t write a matrix access this way because C handles the details. But being aware of the details can help us generate more efficient code.
Almost all C compilers will convert multiples by a power of 2 (2, 4, 8, ...) into shifts, thus taking an expensive operation (multiply) and changing it into an inexpensive operation (shift).
For example:
i = 32 * j;
is compiled as:
i = j << 5; /* 2**5 == 32 */
Y_SIZE is 30, which is not a power of 2. By increasing it to 32, we waste some memory, but get a faster program, as shown in Example 15-15.
Example 15-15. matrix/matrix4.c
[File: matrix/matrix4.c]
#define X_SIZE 60
#define Y_SIZE 32
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
register int x,y; /* current element to zero */
for (y = 0; y < Y_SIZE; ++y) {
for (x = 0; x < X_SIZE; ++x) {
matrix[x][y] = -1;
}
}
}
Because we are initializing consecutive memory locations, we can initialize the matrix by starting at the first location and storing a -1 in the next X_SIZE * Y_SIZE elements. (See Example 15-16.) Using this method, we cut the number of loops down to one. The indexing of the matrix has changed from a standard index (matrix[x][y]), requiring a shift and add to a pointer dereference (*matrix_ptr), and an increment (matrix_ptr++).
Example 15-16. matrix/matrix5.c
[File: matrix/matrix5.c]
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- set every element of matrix to -1 *
********************************************************/
void init_matrix(void)
{
register int index; /* element counter */
register int *matrix_ptr;
matrix_ptr = &matrix[0][0];
for (index = 0; index < X_SIZE * Y_SIZE; ++index) {
*matrix_ptr = -1;
++matrix_ptr;
}
}
But why have both a loop counter and a matrix_ptr? Couldn’t we combine the two? In fact, we can, as shown in Example 15-17.
Example 15-17. matrix/matrix6.c
[File: matrix/matrix6.c]
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
register int *matrix_ptr;
for (matrix_ptr = &matrix[0][0];
matrix_ptr <= &matrix[X_SIZE-1][Y_SIZE-1];
++matrix_ptr) {
*matrix_ptr = -1;
}
}
The function is now well optimized. The only way we could make it better is to hand-code it into assembly language. This change might make the function faster; however, assembly language is highly nonportable and very error-prone.
The library routine memset can be used to fill a matrix or an array with a single character value. As shown in Example 15-18, we can use it to initialize the matrix in this program. Frequently used library subroutines like memset are often coded into assembly language and may make use of special processor-dependent tricks to do the job faster than could be done in C.
Example 15-18. matrix/matrix7.c
[File: matrix/matrix7.c]
#include <memory.h> /* Gets definition of memset */
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
void init_matrix(void)
{
memset(matrix, -1, sizeof(matrix));
}
Now our function consists of only a single function call. Having to call a function just to call another function seems a shame. We have to pay for the overhead of two function calls. Instead we should call memset from the main function. Why don’t we tell the user to rewrite his code usingmemset instead of init_matrix? Because he has several hundred init_matrix calls and doesn’t want to do all that editing.
If we redefine our function as a macro, we have an init_matrix that looks like a function call. But, because it is a macro, it is expanded inline, avoiding all the extra overhead associated with a function call. Look at Example 15-19.
Example 15-19. matrix/matrix8.c
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
/********************************************************
* init_matrix -- Sets every element of matrix to -1. *
********************************************************/
#define init_matrix() \
memset(matrix, -1, sizeof(matrix));
Question 15-1: Why does memset successfully initialize the matrix to -1, but when we try to use it to set every element to 1 in Example 15-20, we fail? (Click here for the answer Section 15.7)
Example 15-20. matrix/matrix9.c
#define X_SIZE 60
#define Y_SIZE 30
int matrix[X_SIZE][Y_SIZE];
#define init_matrix() \
memset(matrix, 1, sizeof(matrix));
How to Optimize
Our matrix initialization function illustrates several optimizing strategies. These are:
Loop ordering
Nested loops should be ordered with the simplest loop outermost and the most complex loops innermost.
Reduction in strength
This phrase is a fancy way of saying you should use cheap operations instead of expensive ones. Table 15-1 lists the relative cost of common operations.
Table 15-1. Relative Cost of Operations
|
Operation |
Relative cost |
|
printf and scanf |
1000 |
|
mallocand free |
800 |
|
trigonometric functions (sin, cos...) |
500 |
|
floating point (any operation) |
100 |
|
integer divide |
30 |
|
integer multiple |
20 |
|
function call |
10 |
|
simple array index |
6 |
|
shifts |
5 |
|
add/subtract |
5 |
|
pointer dereference |
2 |
|
bitwise and, or, not |
1 |
|
logical and, or, not |
1 |
NOTE
Formatting functions like printf, scanf, and sscanf are extremely costly because they have to go through the format string one character at a time, looking for a format conversion character (%). Then they have to do a costly conversion between a character string and a number. These functions should be avoided in time-critical sections of code.
Powers of 2
Use a power of 2 when doing integer multiply or divide. Most compilers substitute a shift for the operation.
Pointers
Using pointers is faster than indexing an array. Pointers are, however, more tricky to use.
Macros
Using a macro eliminates the overhead associated with a function call. It also makes the code bigger and a little more difficult to debug.
CASE STUDY: MACROS VERSUS FUNCTIONS
I once worked on writing a word processing program for a large computer manufacturer. We had a function, next_char, that was used to get the next character from the current file. It was used in thousands of places throughout the program. When we first tested the program with next_char written as a function, the program was unacceptably slow. Analyzing our program, we found that 90% of our time was spent in next_char. So we changed the function to a macro. The speed doubled, but, our code size went up 40% and required a memory expansion card to work. So the speed was all right, but the size was still unacceptable. We finally had to write the routine as a function in hand-optimized assembly language to get both the size and the speed to acceptable levels.
CASE STUDY: OPTIMIZING A COLOR RENDERING ALGORITHM
I was once asked to optimize a program that did color rendering for a large picture. The problem was that the program took eight hours to process a single picture. This sluggishness limited us to doing one run a day.
The first thing I did was to run the program on a machine with a floating-point accelerator. This brought the time down to about six hours. Next, I got permission to use a high-speed RISC computer that belonged to another project, but was now sitting idle. That reduced the time to two hours.
I saved six hours solely by using faster machines. No code had changed yet.
Two fairly simple functions were being called only once from the innermost loop. Rewriting these functions as macros saved me about 15 minutes.
Next, I changed all applicable floating-point operations to integer operations. The savings amounted to 30 minutes out of an hour and 45 minutes of runtime.
I noticed the program was spending about five minutes reading an ASCII file containing a long list of floating-point numbers used in the conversion process. Knowing that scanf is an extremely expensive function, I cut the initialization process down to almost nothing by making the file binary. Total runtime was now down to one hour and ten minutes.
By carefully inspecting the code and using every trick I knew, I saved another five minutes, leaving me five minutes short of my goal of an hour per run.
At this point, my project was refocused and the program put in mothballs for use at some future date.
Answers
Answer 15-1: The problem is that memset is a character fill routine. An integer consists of 2 or 4 bytes (characters). Each byte is assigned the value 1. So a 2-byte integer will receive the value:
integer = 0x0101;
The 1-byte hex value for -1 is 0xFF. The two-byte hex value of -1 is 0xFFFF. So we can take two single byte -1 values, put them together, and come out with -1. This method also works for 0. Any other number will produce the wrong answer. For example, 1 is 0x01. Two bytes of this is 0x0101, or 257.
Programming Exercises
Exercise 15-1: Take one of your previous programs and run it using the interactive debugger to examine several intermediate values.
Exercise 15-2: Write a matrix multiply function. Create a test program that not only tests the function, but times it as well. Optimize it using pointers and determine the time savings.
Exercise 15-3: Write a program to sum the elements in an array. Optimize it.
Exercise 15-4: Write a program that counts the number of bits in a character array. Optimize it through the use of register integer variables. Time it on several different arrays of different sizes. How much time do you save?
Exercise 15-5: Write your own version of the library function memcpy. Optimize it. Most implementations of memcpy are written in assembly language and take advantage of all the quirks and tricks of the processor. How does your memcpy compare with others?