==============================================================================
C-Scene Issue #06
Optimization Techniques - Part II
Platform: Non-specific
Steve Mertz
==============================================================================
This is my second artcle on optimization. I've had some good feedback on my
last article. I will be using that feedback to help me write this article and
hopefully do as good of a job if not better. Thanks to all that wrote back!
This is article is intended for the novice to intermediate programmer. Most
expert programmers should already know this. And if not I hope they learn
something too!
I would also like to note at this time that there are some C/C++ compilers that
will do optimization at compile time. But quite often this is a switch that
you need to include. Most compilers (that I'm aware of) are defaulted to
including information for debugging purposes. And this will sometimes
counteract any compiler optimizations. It is quite often stated that the
best optimizer is the one between your ears. So why not use it?
Things in this article: Reading and Writing to Files.
The things I used for this article:
OS: Linux
Compiler: gcc
Specific flags: -pg (for profiling)
Other programs: gprof (for profiling)
Other files: THETEST.txt (dracula copied 100 times)
One of the largest bottle necks for programs is the file I/O (or any I/O for
that matter.) This is because one has to wait for the disks to find the
information you want to read and then find a spot to put the information on the
disk. Then you wait for it to actually read or write the information.
The best thing to do about this is to read and write large chunks of
information, all at once. Then, after reading the chunk of information into a
buffer, parse through it.
I'm going to be showing two examples of reading in a file and counting the
number of non-whitespace characters in it. The first program will not use
any kind of buffering (buffering is the use of putting stuff into memory to
be used in the near future.) The second program will have a 64kb buffer.
The file I use for benchmarking this is a file that I created from dracula.txt
(found at http://ftp.sunet.se/pub/etext/wiretap-classic-library/dracula.txt.)
I then copied the file one hundred times into another file to create,
THETEST.txt, which is 86332400 bytes long.
Here is the source for prog6-01.c
#include <time.h>
#include <ctype.h>
#include <stdio.h>
int main(int argc, char **argv)
{
int byte;
FILE *fd;
unsigned long counter = 0;
fd = fopen(argv[1], "r");
do
{
byte = fgetc(fd);
if (!isspace(byte))
counter++;
}while (!feof(fd));
fclose(fd);
printf("There are %lu non-whitespace characters in file: %s\n\n",
counter, argv[1]);
}
This program reads one character from a file and then checks to see if it's a
whitespace character. These include: space, form-feed, newline, carriage
return, horizontal tab, and verticle tab. If it is a white space then it
will continue on and read the next character. If it is not a white space then
it will add one to the counter. And then continue on to read the next
character.
Running this program, I get the following results:
Abishai:$ prog6-01 THETEST.txt
There are 66834001 non-whitespace characters in file: THETEST.txt
Abishai:$
Abishai:$ gprof prog6-01 gmon.out |more
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
100.00 17.92 17.92 1 17920.00 17920.00 main
Here is the second program:
#include <time.h>
#include <ctype.h>
#include <stdio.h>
#define CHUNKSIZE 65536 /* 64kb */
int main(int argc, char **argv)
{
char buf[CHUNKSIZE + 1];
FILE *fd;
unsigned long counter = 0;
int charCount;
fd = fopen(argv[1], "r");
do
{
fgets(buf, CHUNKSIZE, fd);
for (charCount = 0; charCount <= strlen(buf); charCount++)
if (!isspace(buf[charCount]))
counter++;
}while (!feof(fd));
fclose(fd);
printf("There are %lu non-whitespace characters in file: %s\n\n",
counter, argv[1]);
}
This program reads in 64kb from the file then goes through each character that
it just read in, to see if it's a whitespace or not.
Running this program I get:
Abishai:$ prog6-02 THETEST.txt
There are 66834001 non-whitespace characters in file: THETEST.txt
Abishai:$
Abishai:$ gprof prog6-02 gmon.out |more
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
100.00 12.51 12.51 1 12510.00 12510.00 main
As we can see that prog6-02 runs 5.41 seconds faster than prog6-01. This is
because in prog6-02 there is less file i/o to slow things down. Here is why:
prog6-01 has to goto the disk and read 86332400 times. This means going out
seeking for the last place that was read by this program on disk and then
waiting for the hard drive to spin to the right spot and read the next
character in that file.
prog6-02 only has 1318 reads. This means that it only has to find the last
spot that was read by this program 1/64th of the time it does in prog6-01.
But because of the loop for dealing with the buffered data we don't see the
real I/O speed.
A side note: One might think, "So if reading big chunks is faster then why
not just read the entire file in one read?" The answer is, how many people
have enough RAM to actually read an 84meg file all at once? Also, there is
a point where the size of the loop will start making things slow down again.
But this could be solved by unrolling the loop (see "Optimizations Techniques
- Part I" in issue #5.)
This is the end of my article. I have tried to make things as simple as I can
for those new to programming, while trying not to play down anybody's
intelligence. If there are any questions, suggestions or comments please
feel free to write me. This is only my second article ever and I'm still
not sure about how things like this are suppose to be done. So let me know
what I need to build on or what I'm doing good at!
-- Steve Mertz
smertz@premier1.net
This page is Copyright © 1998 By
C Scene. All Rights Reserved