<<>> <> <> <> <> <<>> <> <<>> <> <<>> <> <<>> 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> 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"]; }; <> 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"]; <> Commander.Register["ForkPerfTest2-Free", FreeCommand, "Free arrays"]; END.