--- jsr166/src/test/loops/CASLoops.java 2005/06/10 15:45:19 1.1 +++ jsr166/src/test/loops/CASLoops.java 2011/03/15 19:47:05 1.7 @@ -1,6 +1,6 @@ /* * Written by Doug Lea and released to the public domain, as explained at - * http://creativecommons.org/licenses/publicdomain + * http://creativecommons.org/publicdomain/zero/1.0/ */ /* @@ -11,18 +11,25 @@ * just compare and conditionally store (int) values, so are * not intended to measure the "raw" cost of a CAS. * - * Outputs, for runs using 1 ... #cpus threads are, in nanoseconds: + * Outputs, in nanoseconds: * "Atomic CAS" AtomicInteger.compareAndSet + * "Updater CAS" CAS first comparing args * "Volatile" pseudo-CAS using volatile store if comparison succeeds * "Mutex" emulated compare and set done under AQS-based mutex lock * "Synchronized" emulated compare and set done under a synchronized block. * - * The last two are done only if this program is called with (any) argument + * By default, these are printed for 1..#cpus threads, but you can + * change the upper bound number of threads by providing the + * first argument to this program. + * + * The last two kinds of runs (mutex and synchronized) are done only + * if this program is called with (any) second argument */ import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; +import java.util.concurrent.atomic.AtomicIntegerFieldUpdater; import java.util.concurrent.*; import java.util.concurrent.locks.*; @@ -31,27 +38,43 @@ public class CASLoops { static final int TRIALS = 2; static final long BASE_SECS_PER_RUN = 4; static final int NCPUS = Runtime.getRuntime().availableProcessors(); + static int maxThreads = NCPUS; static boolean includeLocks = false; public static void main(String[] args) throws Exception { if (args.length > 0) + maxThreads = Integer.parseInt(args[0]); + + loopIters = new long[maxThreads+1]; + + if (args.length > 1) includeLocks = true; System.out.println("Warmup..."); + for (int i = maxThreads; i > 0; --i) { + runCalibration(i, 10); + oneRun(i, loopIters[i] / 4, false); + System.out.print("."); + } + + for (int i = 1; i <= maxThreads; ++i) + loopIters[i] = 0; + for (int j = 0; j < 2; ++j) { - for (int i = 1; i <= NCPUS; ++i) { + for (int i = 1; i <= maxThreads; ++i) { runCalibration(i, 1000); oneRun(i, loopIters[i] / 8, false); + System.out.print("."); } } - for (int i = 1; i <= NCPUS; ++i) + for (int i = 1; i <= maxThreads; ++i) loopIters[i] = 0; for (int j = 0; j < TRIALS; ++j) { System.out.println("Trial " + j); - for (int i = 1; i <= NCPUS; ++i) { + for (int i = 1; i <= maxThreads; ++i) { runCalibration(i, BASE_SECS_PER_RUN * 1000L); oneRun(i, loopIters[i], true); } @@ -64,7 +87,7 @@ public class CASLoops { static final LoopHelpers.MarsagliaRandom rng = new LoopHelpers.MarsagliaRandom(); - static final long[] loopIters = new long[NCPUS+1]; + static long[] loopIters; static final class NonAtomicInteger { volatile int readBarrier; @@ -85,6 +108,25 @@ public class CASLoops { void set(int val) { value = val; } } + static final class UpdaterAtomicInteger { + volatile int value; + + static final AtomicIntegerFieldUpdater + valueUpdater = AtomicIntegerFieldUpdater.newUpdater + (UpdaterAtomicInteger.class, "value"); + + + UpdaterAtomicInteger() {} + int get() { + return value; + } + boolean compareAndSet(int cmp, int val) { + return valueUpdater.compareAndSet(this, cmp, val); + } + + void set(int val) { value = val; } + } + static final class VolatileInteger { volatile int value; @@ -149,17 +191,17 @@ public class CASLoops { unlock(); } } - void set(int val) { - lock(); + void set(int val) { + lock(); try { - value = val; + value = val; } finally { unlock(); } } } - // All these versions are copy-paste-hacked to avoid + // All these versions are copy-paste-hacked to avoid // contamination with virtual call resolution etc. // Use fixed-length unrollable inner loops to reduce safepoint checks @@ -178,7 +220,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long i = iters; int y = 0; int succ = 0; @@ -196,8 +238,8 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; } } } @@ -215,7 +257,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long i = iters; int y = 0; int succ = 0; @@ -233,8 +275,45 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; + } + } + } + + static final class UpdaterAtomicLoop implements Runnable { + final long iters; + final UpdaterAtomicInteger obj; + final CyclicBarrier barrier; + UpdaterAtomicLoop(long iters, UpdaterAtomicInteger obj, CyclicBarrier b) { + this.iters = iters; + this.obj = obj; + this.barrier = b; + obj.set(rng.next()); + } + + public void run() { + try { + barrier.await(); + long i = iters; + int y = 0; + int succ = 0; + while (i > 0) { + for (int k = 0; k < innerPerOuter; ++k) { + int x = obj.get(); + int z = y + LoopHelpers.compute6(x); + if (obj.compareAndSet(x, z)) + ++succ; + y = LoopHelpers.compute7(z); + } + i -= innerPerOuter; + } + sum.getAndAdd(obj.get()); + successes.getAndAdd(succ); + barrier.await(); + } + catch (Exception ie) { + return; } } } @@ -252,7 +331,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long i = iters; int y = 0; int succ = 0; @@ -270,8 +349,8 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; } } } @@ -289,7 +368,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long i = iters; int y = 0; int succ = 0; @@ -307,8 +386,8 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; } } } @@ -326,7 +405,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long i = iters; int y = 0; int succ = 0; @@ -344,8 +423,8 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; } } } @@ -365,7 +444,7 @@ public class CASLoops { public void run() { try { - barrier.await(); + barrier.await(); long iters = 0; int y = 0; int succ = 0; @@ -388,8 +467,8 @@ public class CASLoops { successes.getAndAdd(succ); barrier.await(); } - catch (Exception ie) { - return; + catch (Exception ie) { + return; } } } @@ -400,7 +479,7 @@ public class CASLoops { CyclicBarrier b = new CyclicBarrier(n+1); totalIters.set(0); NonAtomicInteger a = new NonAtomicInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new NACalibrationLoop(endTime, a, b)).start(); b.await(); b.await(); @@ -414,7 +493,7 @@ public class CASLoops { LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); CyclicBarrier b = new CyclicBarrier(n+1, timer); NonAtomicInteger a = new NonAtomicInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new NonAtomicLoop(iters, a, b)).start(); b.await(); b.await(); @@ -422,11 +501,23 @@ public class CASLoops { return timer.getTime(); } + static long runUpdaterAtomic(int n, long iters) throws Exception { + LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); + CyclicBarrier b = new CyclicBarrier(n+1, timer); + UpdaterAtomicInteger a = new UpdaterAtomicInteger(); + for (int j = 0; j < n; ++j) + new Thread(new UpdaterAtomicLoop(iters, a, b)).start(); + b.await(); + b.await(); + if (sum.get() == 0) System.out.print(" "); + return timer.getTime(); + } + static long runAtomic(int n, long iters) throws Exception { LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); CyclicBarrier b = new CyclicBarrier(n+1, timer); AtomicInteger a = new AtomicInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new AtomicLoop(iters, a, b)).start(); b.await(); b.await(); @@ -438,7 +529,7 @@ public class CASLoops { LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); CyclicBarrier b = new CyclicBarrier(n+1, timer); VolatileInteger a = new VolatileInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new VolatileLoop(iters, a, b)).start(); b.await(); b.await(); @@ -451,7 +542,7 @@ public class CASLoops { LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); CyclicBarrier b = new CyclicBarrier(n+1, timer); SynchedInteger a = new SynchedInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new SynchedLoop(iters, a, b)).start(); b.await(); b.await(); @@ -463,7 +554,7 @@ public class CASLoops { LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer(); CyclicBarrier b = new CyclicBarrier(n+1, timer); LockedInteger a = new LockedInteger(); - for (int j = 0; j < n; ++j) + for (int j = 0; j < n; ++j) new Thread(new LockedLoop(iters, a, b)).start(); b.await(); b.await(); @@ -471,39 +562,48 @@ public class CASLoops { return timer.getTime(); } - static void report(String tag, long runtime, long basetime, long iters) { + static void report(String tag, long runtime, long basetime, + int nthreads, long iters) { System.out.print(tag); - System.out.print(LoopHelpers.rightJustify((runtime - basetime) / iters) + " ns"); - double secs = (double)(runtime) / 1000000000.0; + long t = (runtime - basetime) / iters; + if (nthreads > NCPUS) + t = t * NCPUS / nthreads; + System.out.print(LoopHelpers.rightJustify(t)); + double secs = (double) runtime / 1000000000.0; System.out.println("\t " + secs + "s run time"); } - + static void oneRun(int i, long iters, boolean print) throws Exception { - System.out.println("threads : " + i + - " base iters per thread per run : " + - LoopHelpers.rightJustify(loopIters[i])); + if (print) + System.out.println("threads : " + i + + " base iters per thread per run : " + + LoopHelpers.rightJustify(loopIters[i])); long ntime = runNonAtomic(i, iters); if (print) - report("Base : ", ntime, ntime, iters); + report("Base : ", ntime, ntime, i, iters); Thread.sleep(100L); long atime = runAtomic(i, iters); if (print) - report("Atomic CAS : ", atime, ntime, iters); + report("Atomic CAS : ", atime, ntime, i, iters); + Thread.sleep(100L); + long gtime = runUpdaterAtomic(i, iters); + if (print) + report("Updater CAS : ", gtime, ntime, i, iters); Thread.sleep(100L); long vtime = runVolatile(i, iters); if (print) - report("Volatile : ", vtime, ntime, iters); + report("Volatile : ", vtime, ntime, i, iters); Thread.sleep(100L); if (!includeLocks) return; long mtime = runLocked(i, iters); if (print) - report("Mutex : ", mtime, ntime, iters); + report("Mutex : ", mtime, ntime, i, iters); Thread.sleep(100L); long stime = runSynched(i, iters); - if (print) - report("Synchronized: ", stime, ntime, iters); + if (print) + report("Synchronized: ", stime, ntime, i, iters); Thread.sleep(100L); }