DIRECTORY BasicTime, Commander, CommanderOps, Convert, ForkOps, IO, Process, Random, Rope, WorkerThreads; ForkPerfTest: CEDAR MONITOR LOCKS rp USING rp: REF Pair IMPORTS BasicTime, Commander, CommanderOps, Convert, ForkOps, IO, Process, Random, WorkerThreads = BEGIN constantSeed: INT = 123456; seed: INT ¬ constantSeed; Value: TYPE = INT; maxSize: INT = 200290; --of the array allocation for the array to be sorted defaultSize: INT = 100290; size: INT ¬ defaultSize; array: REF ARRAY [0..maxSize) OF Value ¬ NIL; simpleSizeLimit: INT ¬ 8; --at least 3 forkSizeLimit: INT ¬ 3000; Pair: TYPE = MONITORED RECORD [low, high: INT ¬ 0, done: BOOL ¬ FALSE, waiters: CONDITION]; forksCnt: INT ¬ 0; --counts the "Forks" counterLock: REF Pair ¬ NEW[Pair]; CountFork: ENTRY PROC [rp: REF Pair ¬ counterLock] = { forksCnt ¬ forksCnt+1 }; WaitDone: ENTRY PROC [rp: REF Pair] = { WHILE ~rp.done DO WAIT rp.waiters ENDLOOP }; SetDone: ENTRY PROC [rp: REF Pair] = { rp.done ¬ TRUE; NOTIFY rp.waiters }; startPulses: BasicTime.Pulses; SetUp: PROC [dontArray: BOOL ¬ FALSE] = { IF array=NIL THEN array ¬ NEW[ARRAY [0..maxSize) OF Value]; IF ~dontArray THEN { IF seed#0 THEN { rs: Random.RandomStream ¬ Random.Create[seed: seed]; FOR i: INT IN [0..size) DO array[i] ¬ Random.NextInt[rs]; ENDLOOP; } ELSE { FOR i: INT IN [0..size) DO array[i] ¬ size-i; ENDLOOP } }; forksCnt ¬ 0; 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]]]; IF forksCnt#0 THEN IO.PutF1[s, " forks: %g", IO.int[forksCnt]]; IO.PutRope[s, "\n"]; IF ~dontTestOrder THEN TestOrdering[]; }; SimpleSort: PROC [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 [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[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 [low, high: INT] = { IF high-low=forkSizeLimit THEN {process ¬ FORK QuickSortFORK[np]; CountFork[counterLock]} ELSE QuickSortFORK[np]; }; IF hBound=forkSizeLimit THEN {ForkOps.Fork[QuickSortFork, np]; CountFork[counterLock]} ELSE QuickSortFork[np]; }; IF hBound=forkSizeLimit THEN {Remember[WorkerThreads.Fork[pool, QuickSortWorker, np], activitiesLock]; CountFork[counterLock]} ELSE QuickSortWorker[np]; }; IF hBound0 THEN size ¬ MIN[i, maxSize] ELSE size ¬ defaultSize; IO.PutF1[cmd.out, "Array size set to %g\n", IO.int[size]]; }; SetSeedCommand: Commander.CommandProc = { i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]]; IF i<0 THEN seed ¬ constantSeed ELSE seed ¬ i; IF i=0 THEN IO.PutRope[cmd.out, "Seed set to enforce balanced setup\n"] ELSE IO.PutF1[cmd.out, "Seed set to %g\n", IO.int[seed]]; }; SetSimpleSizeLimitCommand: Commander.CommandProc = { i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]]; IF i<0 THEN simpleSizeLimit ¬ 8 ELSE simpleSizeLimit ¬ MAX[i, 3]; IO.PutF1[cmd.out, "SimpleSortLimit set to %g\n", IO.int[simpleSizeLimit]]; }; SetForkSizeLimitCommand: Commander.CommandProc = { i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]]; forkSizeLimit ¬ i; IO.PutF1[cmd.out, "ForkSizeLimit set to %g\n", IO.int[forkSizeLimit]]; }; SetChainLengthCommand: Commander.CommandProc = { i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]]; chainCnt ¬ i; IO.PutF1[cmd.out, "Chain length set to %g\n", IO.int[chainCnt]]; }; TestOrdering: PROC [] = { val: INT ¬ INT.FIRST; IF array=NIL THEN { ERROR CommanderOps.Failed["Array is NIL\n"]; }; FOR i: INT IN [0..size) DO IF val>array[i] THEN { ERROR CommanderOps.Failed[IO.PutFR1["Failed at position %g\n", IO.int[i]]]; }; val ¬ array[i] ENDLOOP; }; CheckCommand: Commander.CommandProc = { TestOrdering[]; IO.PutRope[cmd.out, "array is sorted\n"] }; PrintParametersCommand: Commander.CommandProc = { IO.PutRope[cmd.out, "ForkPerfTest version June 8, 1993\n"]; IO.PutRope[cmd.out, " last change: added MultiChained forks%\n"]; IO.PutF1[cmd.out, "Array size: %g\n", IO.int[size]]; IO.PutF1[cmd.out, "ForkSizeLimit: %g\n", IO.int[forkSizeLimit]]; IO.PutF1[cmd.out, "SimpleSizeLimit: %g\n", IO.int[simpleSizeLimit]]; IF seed =0 THEN IO.PutRope[cmd.out, "Seed: 0 to enforce balanced setup\n"] ELSE IO.PutF1[cmd.out, "Seed: %g\n", IO.int[seed]]; IO.PutF1[cmd.out, "Chain length: %g\n", IO.int[chainCnt]]; }; chainCnt: INT ¬ 1000; ChainedFORK: PROC [x: REF ANY ¬ NIL] = { counter: REF Pair ~ NARROW[x]; p: INT ¬ counter.high MOD 100; CountFork[counterLock]; IF counter.high>0 THEN TRUSTED { counter.high ¬ counter.high-1; FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP; Process.Detach[FORK ChainedFORK[counter] ]; FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP; } ELSE SetDone[counter] }; ChainedForkOps: PROC [x: REF ANY ¬ NIL] = { counter: REF Pair ~ NARROW[x]; p: INT ¬ counter.high MOD 100; CountFork[counterLock]; IF counter.high>0 THEN TRUSTED { counter.high ¬ counter.high-1; FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP; ForkOps.Fork[ChainedForkOps, counter]; FOR i: INT IN [0..20) DO array[i*p] ¬ i ENDLOOP; } ELSE SetDone[counter] }; ChainedForkOpsCommand: Commander.CommandProc = { chainPair: REF Pair ¬ NEW[Pair]; chainPair.high ¬ chainCnt; SetUp[TRUE]; ChainedForkOps[chainPair]; WaitDone[chainPair]; Report[cmd.out, "ChainedForkOps", TRUE]; }; ChainedFORKCommand: Commander.CommandProc = { chainPair: REF Pair ¬ NEW[Pair]; chainPair.high ¬ chainCnt; SetUp[TRUE]; ChainedFORK[chainPair]; WaitDone[chainPair]; Report[cmd.out, "ChainedFORK", TRUE]; }; MultiChainedFORKCommand: Commander.CommandProc = { chainPair1: REF Pair ¬ NEW[Pair]; chainPair2: REF Pair ¬ NEW[Pair]; chainPair1.high ¬ chainCnt/2; chainPair2.high ¬ chainCnt/2; SetUp[TRUE]; ForkOps.Fork[ChainedFORK, chainPair1]; ForkOps.Fork[ChainedFORK, chainPair2]; WaitDone[chainPair1]; WaitDone[chainPair2]; Report[cmd.out, "Multiple ChainedFORK", TRUE]; }; MultiChainedForkOpsCommand: Commander.CommandProc = { chainPair1: REF Pair ¬ NEW[Pair]; chainPair2: REF Pair ¬ NEW[Pair]; chainPair1.high ¬ chainCnt/2; chainPair2.high ¬ chainCnt/2; SetUp[TRUE]; ForkOps.Fork[ChainedForkOps, chainPair1]; ForkOps.Fork[ChainedForkOps, chainPair2]; WaitDone[chainPair1]; WaitDone[chainPair2]; Report[cmd.out, "Multiple ChainedForkOps", TRUE]; }; Commander.Register["ForkPerfTest-Sort1", SortCommand1, "Sequential"]; Commander.Register["ForkPerfTest-SortComp", SortCommandComp, "Sequential; use NEW for compensation"]; Commander.Register["ForkPerfTest-SortFORK", SortCommandFORK, "use FORK; MAY WEDGE"]; Commander.Register["ForkPerfTest-SortForkOps", SortCommandForkOps, "use ForkOps.Fork; MAY WEDGE"]; Commander.Register["ForkPerfTest-SortWorker2", SortCommandWorker2, "Worker-Threads 2%"]; Commander.Register["ForkPerfTest-SortWorker8", SortCommandWorker8, "Worker-Threads 8%"]; Commander.Register["ForkPerfTest-SortOptimum2", SortCommandOptimum2, "Optimal 2 threads"]; Commander.Register["ForkPerfTest-SortOptimum2Comp", SortCommandOptimum2Comp, "Optimal 2 threads, NEW for compensation"]; Commander.Register["ForkPerfTest-ChainedFORK", ChainedFORKCommand, "Basicly sequential FORK's"]; Commander.Register["ForkPerfTest-ChainedForkOps", ChainedForkOpsCommand, "Basicly sequential ForkOps.Fork"]; Commander.Register["ForkPerfTest-MultiChainedForkOps", MultiChainedForkOpsCommand, "2 Chains of sequential ForkOps.Fork"]; Commander.Register["ForkPerfTest-MultiChainedFORK", MultiChainedFORKCommand, "2 Chains of sequential FORK's"]; Commander.Register["ForkPerfTest-Check", CheckCommand, "Test sortedness of array"]; Commander.Register["ForkPerfTest-Parameters", PrintParametersCommand, "Print setup parameters"]; Commander.Register["ForkPerfTest-SetSize", SetSizeCommand, "Set size of array to be sorted"]; Commander.Register["ForkPerfTest-SetSeed", SetSeedCommand, "Set seed for random numbers"]; Commander.Register["ForkPerfTest-SetSimpleSizeLimit", SetSimpleSizeLimitCommand, "Set size for switch to simpler sort"]; Commander.Register["ForkPerfTest-SetForkSizeLimit", SetForkSizeLimitCommand, "Set size for inhibiting forks; MAY CAUSE WEDGE if too small"]; Commander.Register["ForkPerfTest-SetChainLength", SetChainLengthCommand, "Set number for chained operations"]; Commander.Register["ForkPerfTest-Free", FreeCommand, "Free array"]; END. ° ForkPerfTest.mesa Copyright Σ 1993 by Xerox Corporation. All rights reserved. Created by Christian Jacobi, May 13, 1993 Christian Jacobi, June 8, 1993 5:35 pm 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. --Comp means use NEW for compensation Usefull to free array before running another instance of this program Actual Measurements Setup Κ-•NewlineDelimiter ™code™Kšœ Οeœ1™Kšžœ˜—K˜—šžœžœ˜K˜K˜K˜—Kšžœžœžœ˜K˜—K˜ K˜—K˜K˜Kšœ žœžœžœ˜1K˜Kšœžœžœ˜%K˜šŸœžœžœ!žœ˜SKšœ žœ˜ K˜K˜—šŸœžœžœžœžœžœžœ˜dK˜Kšœ žœ˜K˜—K˜šŸœžœžœžœ˜&Kšœžœžœ˜Kšžœ žœ˜Bšžœ˜K˜Kšœžœ˜.šžœžœ˜Kšœžœžœ%˜7šžœ˜ Kšžœb˜fKšžœ˜—K˜—šžœžœ˜K˜K˜K˜—K˜—K˜K˜—šŸœžœžœ˜&Kšœ žœ˜K˜/Kšœžœ!˜4š žœžœžœGžœžœž˜iK˜Kšž˜—K˜K˜—šŸœžœžœžœ˜,Kšœ žœžœ˜Kšœžœžœ˜K˜K˜.šžœžœ˜Kšœžœžœ%˜7Kšœ žœ˜ K˜—šžœžœ˜K˜K˜K˜—Kš žœ žœžœžœžœ ˜/K˜K˜—šŸœžœ žœ˜,Kšœ žœžœ˜K˜K˜(šžœ žœ˜Kšœ žœ˜&K˜—Kšžœ žœ˜-Kš žœ žœžœžœžœ ˜/K˜K˜—šŸ œ˜'K˜K˜K˜K˜K˜—šŸœ˜*K˜Kšœžœ!˜2K˜K˜K˜—šŸœ˜*K˜Kšœžœ!˜2K˜K˜K˜—šŸœ˜-K˜Kšœžœ!˜2K˜K˜K˜—šŸœ˜-K˜K˜K˜K˜K˜—šŸœ˜-K˜K˜K˜K˜K˜—šŸœ˜2K˜Kšœžœ!˜:K˜$K˜K˜—šŸœ˜.K˜K˜(K˜ K˜K˜—šŸ œ˜&K™EKšœž˜ K˜K˜—šŸœ˜)Kšœžœ7˜=Kšžœžœžœ žœ˜;Kšžœ*žœ ˜:K˜K˜—šŸœ˜)Kšœžœ7˜=Kšžœžœžœ ˜.šžœ˜Kšžœžœ9˜@Kšžœžœ$žœ ˜9—K˜K˜—šŸœ˜4Kšœžœ7˜=Kšžœžœžœ˜AKšžœ/žœ˜JK˜K˜—šŸœ˜2Kšœžœ7˜=K˜Kšžœ-žœ˜FK˜K˜—šŸœ˜0Kšœžœ7˜=K˜ Kšžœ,žœ˜@K˜K˜—šŸ œžœ˜Kšœžœžœžœ˜šžœžœžœ˜Kšžœ'˜,K˜—šžœžœžœ ž˜šžœžœ˜Kšžœžœ#žœ ˜KK˜—K˜Kšžœ˜—K˜K˜—šŸ œ˜'J˜Kšžœ&˜(K˜K˜—šŸœ˜1Kšžœ9˜;KšžœA˜CKšžœ$žœ ˜4Kšžœ'žœ˜@Kšžœ)žœ˜Dšžœ ˜ Kšžœžœ9˜@Kšžœžœžœ ˜3—Kšžœ&žœ˜:K˜—K˜Kšœ žœ˜K˜š Ÿ œžœžœžœžœ˜(Kšœ žœžœ˜Kšœœžœžœ˜K˜šžœ˜šžœžœ˜K˜Kš žœžœžœ žœžœ˜0Kšœžœ˜+Kš žœžœžœ žœžœ˜0K˜—Kšžœ˜—K˜K˜—š Ÿœžœžœžœžœ˜+Kšœ žœžœ˜Kšœœžœžœ˜K˜šžœ˜šžœžœ˜K˜Kš žœžœžœ žœžœ˜0K˜&Kš žœžœžœ žœžœ˜0K˜—Kšžœ˜—K˜K˜—šŸœ˜0Kšœ žœœœžœ˜ K˜Kšœžœ˜ K˜K˜Kšœ"žœ˜(K˜K˜—šŸœ˜-Kšœ žœœœžœ˜ K˜Kšœžœ˜ K˜K˜Kšœžœ˜%K˜K˜—šŸŸœ˜2Kšœ žœžœ˜!Kšœ žœžœ˜!K˜K˜Kšœžœ˜ K˜&K˜&K˜K˜Kšœ(žœ˜.K˜K˜—šŸœ˜5Kšœ žœžœ˜!Kšœ žœžœ˜!K˜K˜Kšœžœ˜ K˜)K˜)K˜K˜Kšœ+žœ˜1K˜K˜—K˜KšΟb™K˜EKšœMžœ˜eKšœHΠbf œ˜TKšœV’ œ˜bK˜XK˜XK˜ZKšœažœ˜xK˜`K˜lK˜zK˜nKš‘™K˜SK˜`K˜]K˜ZK˜xKšœm’œ˜ŒK˜nK˜CKšžœ˜Kšœ˜J˜—…—3βEΏ