Bloody instructions which, being learned, return to plague the inventor.
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:
That database program you gave me is broken.
What’s wrong?
Sometimes, when I’m doing a sort, it gets things in the wrong order.
What command were you using?
The sort command.
Tell me exactly what you typed, keystroke by keystroke, to get it to fail.
I don’t remember it exactly. I was doing a lot of sorts.
If I come over can you show me the bug?
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.
/******************************************************** * 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] = ' '; if (lookup(name)) printf("%s is in the list ", name); else printf("%s is not in the list ", 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
.
#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, -S
file
, 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.
[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 ", save_file_name); break; default: fprintf(stderr,"Bad option: %s ", 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
.
#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 -P
file
. 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.
/********************************************************* * 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 ", 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 ", playback_file_name); exit (8); } break; default: fprintf(stderr,"Bad option: %s ", 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.
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.
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.
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 ", width, height); #endif /* DEBUG */
The program can be compiled with DEBUG
undefined for normal use; you can
define it when debugging is needed.
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 ", 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 -Z
xxx
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 != ' ') { 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 ");
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.
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.
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
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
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
where
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.
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 ", 24 three_count, seven_count); 25 return (0); 26 } 27 28 void get_data(int data) 29 { 30 31 printf("Enter 5 numbers "); 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
");
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 "); 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).
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.
[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 ", 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 ", middle); } if (low == high) { printf("Not found "); 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 ", 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 ", middle); 61 } 62 63 if (low == high) { 64 printf("Not found "); 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 ", middle); (dbx)
Now we start single-stepping to see what happens:
60 printf("Found at index %d ", 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 ", middle); }
to:
if (data[middle] == search) { printf("Found at index %d ", 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.
[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 ", 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 "); break; } middle = (low + high) / 2; if (data[middle] == search) { printf("Found at index %d ", 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.
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 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.
#include <stdio.h> int main() { int i,j; /* two random integers */ i = 1; j = 0; printf("Starting "); printf("Before divide..."); i = i / j; /* divide by zero error */ printf("After "); 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.
[File: flush2/flush2.c] #include <stdio.h> int main() { int i,j; /* two random integers */ i = 1; j = 0; printf("Starting "); fflush(stdout); printf("Before divide..."); fflush(stdout); i = i / j; /* divide by zero error */ printf("After "); fflush(stdout); return(0); }
The flush
statement makes the
I/O less efficient, but more current.
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 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).
[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.
[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.
[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; } } }
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:
Get the address of the matrix.
Compute x * Y_SIZE
.
Compute y
.
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.
[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++
).
[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.
[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.
[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 using memset
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.
#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)
Our matrix initialization function illustrates several optimizing strategies. These are:
Nested loops should be ordered with the simplest loop outermost and the most complex loops innermost.
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.
Operation | Relative cost |
| 1000 |
| 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 |
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.
Use a power of 2 when doing integer multiply or divide. Most compilers substitute a shift for the operation.
Using pointers is faster than indexing an array. Pointers are, however, more tricky to use.
Using a macro eliminates the overhead associated with a function call. It also makes the code bigger and a little more difficult to debug.
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.
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?
[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.
3.142.171.64