🚀 go-pugleaf

Here is the original question:

We have an application where we are trying to estimate the order of
a certain algorithm (whether O(N), O(N^2), etc.) by running it a certain
number of times for various values of N.  We measure the CPU time used
by the algorithm using the FORTRAN "SECNDS" command, executing it just 
before and just after the algorithm runs through its paces.

What we are finding is that the CPU measure we get back varies wildly,
even for large values of N (~250) and for large numbers of runs (~30).
The questions are as follows:

(1) Are there aspects of the SECNDS command we don't know about, such as

	o  sensitivity to system functions (user load, time of day, etc.)
	o  inherent uncertainty

(2) Is there a more reliable way to estimate the order of the algorithm?

As you have guessed, we're running in FORTRAN, we're on a shared system,
and we're not taking advantage of parallel processing or any other advanced
programming tool.

And here is a summary of responses:

**********************************************************************

From:	curran@pegasus.hks.com (Bill Mills-Curran)

The VMS documentation for SECNDS ($ HELP FORTRAN INTRINS SECNDS) shows
that it is measuring wall clock time.  Try the C function "clock".
You can call it quite easily from FORTRAN.  Note that it returns an
integer which counts hundreths of a second used in the current
program.

**********************************************************************

From: mpaul@unlinfo.unl.edu (marxhausen paul)

This is no help, but estimating CPU time usage is tough even on dedicated
single-user computers like PCs and similar - much of the "benchmarking"
that goes on in popular computer magazines points this out. Hardware 
issues such as memory and disk cacheing, drive access times, etc. all 
make it hard to get objective results.

In the case of a multiuser computer, things are much worse in this regard.
The system has no real way to eliminate the delays imposed by swapping your
process in and out, and the hardware delays are almost completely unpre-
dicatable since the machine is servicing so many other requests at once.

**********************************************************************

From: kk881595@princeton (kevin knappmiller)

Timing commands on multitasking systems are often tricky if you
want actual execution times.  What is the system you are using?
I would guess that your command is just sampling the system clock
giving real time not execution time.

It has been my experience that you have to do something slightly 
different on almost every system.  One good choice might be
to use the UNIX "time" command, and stucture your code so that
the entire (or nearly) call execution time was taken by the
algorithm.  That is if you are using a UNIX with "time".

**********************************************************************

From: mwj%se17@se01.wg2.waii.com (Mike Johnson)

To a feeble-minded codeslinger like myself, the best way to determine the 
order of an algorithm is by inspection. For example, I know that a bubble 
sort or insertion sort is O(N**2), because, in the worst case, N comparisons 
may be required to put each of the N data items in its place. I know that 
a quicksort is O(N*log N), because log N operations are required for each 
of the N data items.  (By log N, I mean the base 2 logarithm of N.) 

**********************************************************************

Unfortunately, the algorithm is simply too much for us to estimate by
inspection with the time we have at hand.  We were forced to scrap it,
do to the need for a quick turnaround on engineering time.

But the insight on clock time and run time measurement really helped us
reach that decision in a hurry.  Thanks to all who responded.

RG

Who became an engineer thinking "free-body diagrams" might be interesting.