---- Running time & code efficiency ----

[Doug Gwyn]

In article <742 at babcock.cerc.wvu.wvnet.edu> siping at cathedral.cerc.wvu.wvnet.edu (Siping Liu) writes:
>Hi. I am trying to analyze my C code and make it run faster.

Let's hope that it really needs to run faster,
or else that you're doing this as an educational exercise.

>The program is to translate files in one format to another.
>I wonder if there is a generic way to decide a lower bound
>of the running time for this kind of problem?

Well, there can't be a simple one since a vast number of nontrivial
programs, including for example compilers, fall into this category.

>I know function calls consume time so I look through
>the code and cut off some unnecessary ones;
>I know you can trade space for speed, however I wonder how far
>you can go along this direction. But I cannot get much from these
>considerations. Any comments? Suggections?

Maintainability of the code suffers as you perform this sort of
low-level tweaking.  Much of the time spent in a typical program
is localized, i.e. involves a small portion of the total code.

>What is your favorate tool for timing analysis? I used "prof" but
>it did not give me the timing imformation for all functions in
>my program -- just a few functions were listed. I also used the
>system provided function called "times", it is pretty good.

"prof" should work pretty well if you compile all your sources with
"cc -p" and if you also LINK with "cc -p" in order to get function
counts for library routines.  If you have a good version of "prof"
(found on fewer and fewer systems as time goes on), you can obtain
a nice plot of an integral histogram over code space, which is very
handy for spotting "hot spots" where a lot of execution time is spent.

>The last questions: why doesn't the "time" command give me an identical
>user time each time I run the same thing? In the "time"'s report,
>is the time spent on the function calls by the system accounted in
>the user time or system time?

"Real time" depends on system load and other external factors, so it
is a poor indicator unless you are able to run your application on
an entirely idle system (no background daemons, spoolers, etc.).
"User time" is time spent executing in "user mode", which means within
the application proper, exclusive of system calls.  "System time" is
that spent by the operating system kernel on behalf of your process as
the result of system calls that the process makes.

The times vary slightly due to clock sampling (quantization) errors
and inherent inaccuracies in assigning time for certain system
services.  Note also that if the process invoked subprocesses, "time"
will include the subprocess times if and only if the subprocesses
terminate before the top-level process.

There are many methods for improving code efficiency.  Sometimes the
algorithm being used is not the most efficient method of solving the
problem, and changing to a better algorithm could speed things up
far more than any amount of low-level tweaking.  If the overall
algorithms are optimal, then once you have located the bottleneck(s)
via profiling you can consider detailed low-level ways to speed them
up.  There are many standard tricks, but sometimes it is possible to
dream up a new way to improve speed.  Jon Bentley's books are a good
starting point for learning such methods.