ForkPerfTest2.mesa
Copyright Ó 1993 by Xerox Corporation. All rights reserved.
Created by Christian Jacobi, May 13, 1993
Christian Jacobi, June 8, 1993 11:20 am PDT
Test program to measure speed of forks, parallel processing and similar operations.
For measuring, a quicksort algorithm is used. Quicksort is a good thing to measure because it is neither specially well suited to parallelism nor does it need lots of communication.
While this is about parallelism, the individual test are not re-entrant and only one at a time should run.
DIRECTORY BasicTime, Commander,
IO, Rope;
ForkPerfTest2:
CEDAR
MONITOR
LOCKS lock USING lock: REF Lock
IMPORTS BasicTime, Commander, IO =
BEGIN
Lock: TYPE = MONITORED RECORD [unused: BOOL ¬ FALSE];
constantSeed: INT = 123456;
seed: INT ¬ constantSeed;
Value: TYPE = INT;
maxSize: INT = 100290; --of the array allocation for the array to be sorted
defaultSize: INT = 100290;
size: INT ¬ defaultSize;
Array: TYPE = REF ArrayRep;
ArrayRep: TYPE = ARRAY [0..maxSize) OF Value;
array1: Array ¬ NIL;
array2: Array ¬ NIL;
simpleSizeLimit: INT ¬ 8; --at least 3
startPulses: BasicTime.Pulses;
SetUp:
PROC [doArray:
BOOL ¬
TRUE, secondArray:
BOOL ¬
FALSE] = {
IF array1=NIL THEN array1 ¬ NEW[ArrayRep];
IF doArray
THEN {
FOR i:
INT
IN [0..size)
DO
array1[i] ¬ size-i;
ENDLOOP;
IF secondArray
THEN {
IF array2=NIL THEN array2 ¬ NEW[ArrayRep];
FOR i: [0..maxSize)
IN [0..maxSize)
DO
array2[i] ¬ array1[i];
ENDLOOP;
};
};
startPulses ¬ BasicTime.GetClockPulses[];
};
Report:
PROC [s:
IO.
STREAM, what: Rope.
ROPE, dontTestOrder:
BOOL ¬
FALSE] = {
elapsedPulses: BasicTime.Pulses ¬ BasicTime.GetClockPulses[] - startPulses;
time: REAL ¬ BasicTime.PulsesToSeconds[elapsedPulses];
IO.PutF[s, "%g time: %g seconds", IO.rope[what], IO.real[BasicTime.PulsesToSeconds[elapsedPulses]]];
IO.PutRope[s, "\n"];
};
SimpleSort:
PROC [array: Array, low, high:
INT] = {
FOR i:
INT
IN [low..high)
DO
FOR j:
INT
IN (i..high]
DO
IF array[i] > array[j]
THEN {
x: Value ¬ array[i]; array[i] ¬ array[j]; array[j] ¬ x
};
ENDLOOP
ENDLOOP
};
Partition:
PROC [array: Array, low, high:
INT]
RETURNS [
INT,
INT] = {
m: INT ¬ (low+high)/2;
x, bval: Value;
IF high-low<3 THEN ERROR; --bith, the simple sort and the main loop could bounds fail
SimpleSort[array, m-1, m+1]; --not for real; just gives a better average bval
bval ¬ array[m]; --quite random
DO
WHILE array[low] < bval DO low ¬ low+1 ENDLOOP;
WHILE bval < array[high] DO high ¬ high-1 ENDLOOP;
IF low > high THEN RETURN [high, low];
x ¬ array[high]; array[high] ¬ array[low]; array[low] ¬ x;
low ¬ low+1; high ¬ high-1
ENDLOOP;
};
QuickSort1:
PROC [array: Array, low, high:
INT, extraAllocations:
BOOL] = {
IF extraAllocations
THEN {
ri: REF REF ANY ¬ NIL;
ri ¬ NEW[REF ANY];
ri ¬ ri --hope this fools the optimizer
};
IF high-low<simpleSizeLimit THEN SimpleSort[array, low, high]
ELSE {
lBound, hBound: Value;
[lBound, hBound] ¬ Partition[array, low, high];
IF low<lBound THEN QuickSort1[array, low, lBound, extraAllocations];
IF hBound<high THEN QuickSort1[array, hBound, high, extraAllocations];
};
};
Sort2SCommand: Commander.CommandProc = {
SetUp[TRUE, TRUE];
QuickSort1[array1, 0, size-1, FALSE];
QuickSort1[array2, 0, size-1, FALSE];
Report[cmd.out, "Sort2 Sequential"];
};
Sort2PCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK QuickSort1[array1, 0, size-1, FALSE];
QuickSort1[array2, 0, size-1, FALSE];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Sort2 Parallel"];
};
Sort2SACommand: Commander.CommandProc = {
SetUp[TRUE, TRUE];
QuickSort1[array1, 0, size-1, TRUE];
QuickSort1[array2, 0, size-1, TRUE];
Report[cmd.out, "Sort2 Sequential with allocations"];
};
Sort2PACommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK QuickSort1[array1, 0, size-1, TRUE];
QuickSort1[array2, 0, size-1, TRUE];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Sort2 Parallel with allocations"];
};
FreeCommand: Commander.CommandProc = {
Usefull to free array before running another instance of this program
array1 ¬ NIL;
array2 ¬ NIL;
};
DeepCall:
PROC [i:
INT] = {
IF i>0 THEN DeepCall[i-1];
};
DeepCalls:
PROC [cnt:
INT, depth:
INT ¬ 150] = {
FOR i:
INT
IN [0..cnt)
DO
DeepCall[depth];
ENDLOOP
};
DeepCallSCommand: Commander.CommandProc = {
SetUp[FALSE, FALSE];
DeepCalls[1000];
DeepCalls[1000];
Report[cmd.out, "DeepCalls Sequential"];
};
DeepCallPCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[FALSE, FALSE];
process ¬ FORK DeepCalls[1000];
DeepCalls[1000];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "DeepCalls Parallel"];
};
Locked:
ENTRY
PROC [lock:
REF Lock] = {
lock.unused ¬ FALSE
};
lock1: REF Lock ¬ NEW[Lock];
lock2: REF Lock ¬ NEW[Lock];
ManyLocks:
PROC [cnt:
INT ¬ 150000, lock:
REF Lock] = {
FOR i:
INT
IN [0..cnt)
DO
Locked[lock];
ENDLOOP
};
LockingSCommand: Commander.CommandProc = {
SetUp[FALSE, FALSE];
ManyLocks[450000, lock1];
ManyLocks[450000, lock2];
Report[cmd.out, "Locking Sequential"];
};
LockingPNCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[FALSE, FALSE];
process ¬ FORK ManyLocks[450000, lock1];
ManyLocks[450000, lock2];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Locking Parallel, NO conflicts"];
};
LockingPCCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[FALSE, FALSE];
process ¬ FORK ManyLocks[450000, lock1];
ManyLocks[450000, lock1];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Locking Parallel, WITH conflicts"];
};
DoSome:
PROC [onlyReads:
BOOL, a: Array] = {
x, y, z: Value;
x ¬ a[1]*2;
y ¬ a[2]+1;
z ¬ a[3]-4;
IF ~onlyReads
THEN {
a[1] ¬ y;
a[2] ¬ z;
a[3] ¬ x;
};
};
DoSomes:
PROC [cnt:
INT, onlyReads:
BOOL, a: Array] = {
FOR i:
INT
IN [0..cnt)
DO
DoSome[onlyReads, a];
ENDLOOP;
};
ReadsSCommand: Commander.CommandProc = {
SetUp[TRUE, TRUE];
DoSomes[600000, TRUE, array1];
DoSomes[600000, TRUE, array2];
Report[cmd.out, "Sequential reads"];
};
WritesSCommand: Commander.CommandProc = {
SetUp[TRUE, TRUE];
DoSomes[600000, FALSE, array1];
DoSomes[600000, FALSE, array2];
Report[cmd.out, "Sequential Read/Writes"];
};
ReadsPNCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK DoSomes[600000, TRUE, array1];
DoSomes[600000, TRUE, array2];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Parallel reads, NO conflicts"];
};
ReadsPCCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK DoSomes[600000, TRUE, array1];
DoSomes[600000, TRUE, array1];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Parallel reads, WITH conflicts"];
};
WritesPNCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK DoSomes[600000, FALSE, array1];
DoSomes[600000, TRUE, array2];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Parallel writes, NO conflicts"];
};
WritesPCCommand: Commander.CommandProc = {
process: PROCESS ¬ NIL;
SetUp[TRUE, TRUE];
process ¬ FORK DoSomes[600000, FALSE, array1];
DoSomes[600000, TRUE, array1];
TRUSTED {[] ¬ JOIN process};
Report[cmd.out, "Parallel writes, WITH conflicts"];
};
Actual Measurements
Commander.Register["ForkPerfTest2-Sort2S", Sort2SCommand, "Two sorts Sequential"];
Commander.Register["ForkPerfTest2-Sort2P", Sort2PCommand, "Two sorts Parallel"];
Commander.Register["ForkPerfTest2-Sort2SA", Sort2SACommand, "Two sorts Sequential with Allocations"];
Commander.Register["ForkPerfTest2-Sort2PA", Sort2PACommand, "Two sorts Parallel with Allocations"];
Commander.Register["ForkPerfTest2-DeepCallS", DeepCallSCommand, "Deep calls Sequential"];
Commander.Register["ForkPerfTest2-DeepCallP", DeepCallPCommand, "Deep calls Parallel"];
Commander.Register["ForkPerfTest2-LockingS", LockingSCommand, "Locking Sequential"];
Commander.Register["ForkPerfTest2-LockingPN", LockingPNCommand, "Locking Parallel, NO conflicts"];
Commander.Register["ForkPerfTest2-LockingPC", LockingPCCommand, "Locking Parallel, WITH conflicts"];
Commander.Register["ForkPerfTest2-ReadsS", ReadsSCommand, "Sequential reads"];
Commander.Register["ForkPerfTest2-WritesS", WritesSCommand, "Sequential Read/Writes"];
Commander.Register["ForkPerfTest2-ReadsPN", ReadsPNCommand, "Parallel reads, NO conflicts"];
Commander.Register["ForkPerfTest2-ReadsPC", ReadsPCCommand, "Parallel reads, WITH conflicts"];
Commander.Register["ForkPerfTest2-WritesPN", WritesPNCommand, "Parallel writes, NO conflicts"];
Commander.Register["ForkPerfTest2-WritePC", WritesPCCommand, "Parallel writes, WITH conflicts"];
Setup
Commander.Register["ForkPerfTest2-Free", FreeCommand, "Free arrays"];
END.