sword@vu-vlsi.UUCP (David Talmage) (12/07/87)
In his _Programming Pearls_ column of _Communications of the ACM_ (March, 1986,
Volume 29, Number 3), Jon L. Bentley writes about "back-of-the-envelope"
calculations. One of the exercises he gives is to calculate the cost of
various operations on a particular system. Since I've got a copy of the
beta-test version of OXXI Modula-2, and since there have been some questions
recently in this group about both OXXI and M2Amiga Modula-2, I thought I'd try
my hand at that exercise.
Each test was run on my two-drive, 512K Amiga 1000. Of the 512K, about
134,000 bytes were free for running the tests because I had both the compiler
and the editor, an enhanced version of MicroGNU Emacs, loaded. There were no
files in any of the editor's buffers.
I timed each test on a cheap digital stopwatch I got from IBM for sitting
through a demo of their AT a few years ago. I started the timer at the same
time as I hit RETURN (see the code fragment below) and stopped the timer when
I saw the CLI prompt (2>).
In all, I made 17 tests, covering the cost of a null FOR loop, a function call,
INTEGER and REAL arithmetic, some REAL functions from MathLib0, and some
String functions.
With three exceptions, I ran each test five times, discarding the greatest and
least of the run times, and averaging the remaining three to the nearest tenth
of a second.
Each of the exceptions, the log, ln, and sin tests, I ran once because each
one had a run time of over 14 minutes and 50 seconds. I couldn't justify
running each one four more times when each of these was so much larger than
the other test times.
In all of the INTEGER arithmetic tests, I used two integers as operands: 7 and
31436, two numbers that are relatively prime.
In all of the REAL arithmetic tests, I used two reals as operands: 47.651 and
31436.008092.
The argument to each of the MathLib0 functions I tested was 31436.008092. I
opened "mathtrans.library" before starting each timed run but the time to
close the library is included in each of the MathLib0 tests.
In the String tests, I used equal strings of length 10, each an array of 11
characters, with the last character an ASCII null. Each was the first 10 ASCII
characters in order.
The body of all of my tests is the program fragment below.
MODULE Null_FOR;
(*
Author: David W. Talmage
Reference: Bentley, Jon. "Programming Pearls", Communications of the ACM,
29, 3 (March, 1986), 176_182.
This little module is my attempt to test the cost per iteration of
a null FOR loop.
Time this with a stop watch then divide the time by N, where N is the
number of iterations of the FOR loop.
*)
FROM InOut IMPORT Read, WriteLn, WriteString;
(*FROM <ModuleName> IMPORT <ImportList>; *)
CONST
N = 1000000D; (* Number of iterations of this test.
The "D" signifies a double or long. *)
VAR
I : LONGCARD;
Wait : CHAR;
(* Other declarations here *)
BEGIN (* Null_FOR *)
WriteString( 'Null_FOR:' );
WriteLn;
WriteString( 'Get your stop watch ready. Start it when you press <CR>.' );
Read( Wait );
FOR I := 1D TO N DO (* We need 1D because I is a LONGCARD. *)
(* Test item goes here *)
END;
END Null_FOR.
The chart below summarizes my findings for a million iterations of each test.
Total
Average Overhead Time of
Operation Time (Sec) Overhead (Sec) Operation (Sec)
========= ========== ======== ======== ===============
FOR 11.0 none 0.0 11.0
INTEGER + 16.4 FOR 11.0 5.4
- 16.4 5.4
* 23.4 12.4
Div 37.8 26.8
REAL + 71.7 60.7
- 78.6 67.6
* 115.5 104.5
/ 132.7 121.7
MathLib0 [1]
sqrt 292.7 FOR, Function 35.2 257.5
log 1024 989
ln 888 853
sin 960 925
real [2] 50.7 15.5
entier [3] 50.9 15.7
String
CompareString 344.3 309.1
CopyString 353.4 318.2
Function Call 40.6 FOR, INTEGER + 16.4 24.2
Notes:
1. Each of these includes the time required to close
"mathtrans.library" once.
2. real converts a LONGINT to a REAL.
3. entier converts a REAL to a LONGINT.
What conclusions can I draw from this exercise? For one, function calls are
relatively expensive compared to INTEGER addition and subtraction, but about
one half to one third the cost of any REAL arithmetic. String operations are
as expensive as you can get outside of the MathLib0 routines, which blow
everybody away in terms of demands on the CPU.
There is a lot of work left to do on these benchmarks and I hope one of you
will take it up. To complete Mr. Bentley's exercise, we need measurements of
I/O time and utilities. For I/O times, Mr. Bentley suggests those of
reading/writing one character/integer, disk access and disk access per database
operation (whatever that is with respect to Modula-2 and the Amiga). For the
utilities, he suggests sorting 10,000 integers and 10,000 strings, and
searching a text file for a string.
I think it would be useful to know how long it takes to allocate and
deallocate chunks of memory, to convert a string to a number and a number to a
string, and to generate a random number using the Random function from the
RandomNumbers module. Also, I'd like to know how small set operations compare
to large set operations using the procedures in the LargeSets module.
Would it be useful to know how long it takes to create a screen, menu, or
requestor? How about reading the system Preferences? Or operations on an
Exec List?
Do any of you have similar benchmarks for C (in various flavors), Amiga BASIC,
or any of the other Amiga languages? I'd be especially interested to know how
fast some of these are in ICON. Since learning ICON is my next project,
perhaps I'll find out and let you all know.
Regards,
David
________________________________________________________________________________
David W. Talmage Villanova U/ University Computing and Information Services
Uucp: ...!vu-vlsi!sword, ...!vu-vlsi!excalibur!talmage (preferred uucp)
Bitnet: talmage@vuvaxcom (best choice over all)
Arpa Gateway: talmage%vuvaxcom.bitnet@eddie.mit.edu (more reliable than wiscvm?)