<<>> <> <> <> <> <<>> <> <<>> <> <<>> <> <<>> 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> IF rp.high-rp.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 hBound> array ¬ NIL }; SetSizeCommand: Commander.CommandProc = { i: INT ¬ Convert.IntFromRope[CommanderOps.NextArgument[cmd]]; IF i>0 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.