test/loops/CASLoops.java

/*
 * Written by Doug Lea and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

/*
 * Estimates the difference in time for compareAndSet and CAS-like
 * operations versus unsynchronized, non-volatile pseudo-CAS when
 * updating random numbers. These estimates thus give the cost
 * of atomicity/barriers/exclusion over and above the time to
 * just compare and conditionally store (int) values, so are
 * not intended to measure the "raw" cost of a CAS.
 *
 * 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.
 *
 * 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.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;

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 <= maxThreads; ++i) {
                runCalibration(i, 1000);
                oneRun(i, loopIters[i] / 8, false);
                System.out.print(".");
            }
        }

        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 <= maxThreads; ++i) {
                runCalibration(i, BASE_SECS_PER_RUN * 1000L);
                oneRun(i, loopIters[i], true);
            }
        }
    }

    static final AtomicLong totalIters = new AtomicLong(0);
    static final AtomicLong successes = new AtomicLong(0);
    static final AtomicInteger sum = new AtomicInteger(0);

    static final LoopHelpers.MarsagliaRandom rng = new LoopHelpers.MarsagliaRandom();

    static long[] loopIters;

    static final class NonAtomicInteger {
        volatile int readBarrier;
        int value;

        NonAtomicInteger() {}
        int get() {
            int junk = readBarrier;
            return value;
        }
        boolean compareAndSet(int cmp, int val) {
            if (value == cmp) {
                value = val;
                return true;
            }
            return false;
        }
        void set(int val) { value = val; }
    }

    static final class UpdaterAtomicInteger {
        volatile int value;

        static final AtomicIntegerFieldUpdater<UpdaterAtomicInteger>
                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;

        VolatileInteger() {}
        int get() {
            return value;
        }
        boolean compareAndSet(int cmp, int val) {
            if (value == cmp) {
                value = val;
                return true;
            }
            return false;
        }
        void set(int val) { value = val; }
    }

    static final class SynchedInteger {
        int value;

        SynchedInteger() {}
        int get() {
            return value;
        }
        synchronized boolean compareAndSet(int cmp, int val) {
            if (value == cmp) {
                value = val;
                return true;
            }
            return false;
        }
        synchronized void set(int val) { value = val; }
    }

    static final class LockedInteger extends AbstractQueuedSynchronizer {
        int value;
        LockedInteger() {}

        public boolean tryAcquire(int acquires) {
            return compareAndSetState(0, 1);
        }
        public boolean tryRelease(int releases) {
            setState(0);
            return true;
        }
        void lock() { acquire(1); }
        void unlock() { release(1); }

        int get() {
            return value;
        }
        boolean compareAndSet(int cmp, int val) {
            lock();
            try {
                if (value == cmp) {
                    value = val;
                    return true;
                }
                return false;
            } finally {
                unlock();
            }
        }
        void set(int val) {
            lock();
            try {
                value = val;
            } finally {
                unlock();
            }
        }
    }

    // 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
    static final int innerPerOuter = 16;

    static final class NonAtomicLoop implements Runnable {
        final long iters;
        final NonAtomicInteger obj;
        final CyclicBarrier barrier;
        NonAtomicLoop(long iters, NonAtomicInteger 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;
            }
        }
    }

    static final class AtomicLoop implements Runnable {
        final long iters;
        final AtomicInteger obj;
        final CyclicBarrier barrier;
        AtomicLoop(long iters, AtomicInteger 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;
            }
        }
    }

    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;
            }
        }
    }

    static final class VolatileLoop implements Runnable {
        final long iters;
        final VolatileInteger obj;
        final CyclicBarrier barrier;
        VolatileLoop(long iters, VolatileInteger 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;
            }
        }
    }

    static final class SynchedLoop implements Runnable {
        final long iters;
        final SynchedInteger obj;
        final CyclicBarrier barrier;
        SynchedLoop(long iters, SynchedInteger 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;
            }
        }
    }

    static final class LockedLoop implements Runnable {
        final long iters;
        final LockedInteger obj;
        final CyclicBarrier barrier;
        LockedLoop(long iters, LockedInteger 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;
            }
        }
    }

    static final int loopsPerTimeCheck = 2048;

    static final class NACalibrationLoop implements Runnable {
        final long endTime;
        final NonAtomicInteger obj;
        final CyclicBarrier barrier;
        NACalibrationLoop(long endTime, NonAtomicInteger obj, CyclicBarrier b) {
            this.endTime = endTime;
            this.obj = obj;
            this.barrier = b;
            obj.set(rng.next());
        }

        public void run() {
            try {
                barrier.await();
                long iters = 0;
                int y = 0;
                int succ = 0;
                do {
                    int i = loopsPerTimeCheck;
                    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;
                    }
                    iters += loopsPerTimeCheck;
                } while (System.currentTimeMillis() < endTime);
                totalIters.getAndAdd(iters);
                sum.getAndAdd(obj.get());
                successes.getAndAdd(succ);
                barrier.await();
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static void runCalibration(int n, long nms) throws Exception {
        long now = System.currentTimeMillis();
        long endTime = now + nms;
        CyclicBarrier b = new CyclicBarrier(n+1);
        totalIters.set(0);
        NonAtomicInteger a = new NonAtomicInteger();
        for (int j = 0; j < n; ++j)
            new Thread(new NACalibrationLoop(endTime, a, b)).start();
        b.await();
        b.await();
        long ipt = totalIters.get() / n;
        if (ipt > loopIters[n])
            loopIters[n] = ipt;
        if (sum.get() == 0) System.out.print(" ");
    }

    static long runNonAtomic(int n, long iters) throws Exception {
        LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        CyclicBarrier b = new CyclicBarrier(n+1, timer);
        NonAtomicInteger a = new NonAtomicInteger();
        for (int j = 0; j < n; ++j)
            new Thread(new NonAtomicLoop(iters, a, b)).start();
        b.await();
        b.await();
        if (sum.get() == 0) System.out.print(" ");
        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)
            new Thread(new AtomicLoop(iters, a, b)).start();
        b.await();
        b.await();
        if (sum.get() == 0) System.out.print(" ");
        return timer.getTime();
    }

    static long runVolatile(int n, long iters) throws Exception {
        LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        CyclicBarrier b = new CyclicBarrier(n+1, timer);
        VolatileInteger a = new VolatileInteger();
        for (int j = 0; j < n; ++j)
            new Thread(new VolatileLoop(iters, a, b)).start();
        b.await();
        b.await();
        if (sum.get() == 0) System.out.print(" ");
        return timer.getTime();
    }

    static long runSynched(int n, long iters) throws Exception {
        LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        CyclicBarrier b = new CyclicBarrier(n+1, timer);
        SynchedInteger a = new SynchedInteger();
        for (int j = 0; j < n; ++j)
            new Thread(new SynchedLoop(iters, a, b)).start();
        b.await();
        b.await();
        if (sum.get() == 0) System.out.print(" ");
        return timer.getTime();
    }

    static long runLocked(int n, long iters) throws Exception {
        LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        CyclicBarrier b = new CyclicBarrier(n+1, timer);
        LockedInteger a = new LockedInteger();
        for (int j = 0; j < n; ++j)
            new Thread(new LockedLoop(iters, a, b)).start();
        b.await();
        b.await();
        if (sum.get() == 0) System.out.print(" ");
        return timer.getTime();
    }

    static void report(String tag, long runtime, long basetime,
                       int nthreads, long iters) {
        System.out.print(tag);
        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 {
        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, i, iters);
        Thread.sleep(100L);
        long atime = runAtomic(i, iters);
        if (print)
            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, i, iters);

        Thread.sleep(100L);
        if (!includeLocks) return;
        long mtime = runLocked(i, iters);
        if (print)
            report("Mutex       : ", mtime, ntime, i, iters);
        Thread.sleep(100L);
        long stime = runSynched(i, iters);
        if (print)
            report("Synchronized: ", stime, ntime, i, iters);
        Thread.sleep(100L);
    }
}
Revision:	1.11
Committed:	Sat Dec 31 19:10:25 2016 UTC (7 years, 4 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.10:	+2 -2 lines
Log Message:	organize imports
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea and released to the public domain, as explained at
3	jsr166	1.7	* http://creativecommons.org/publicdomain/zero/1.0/
4	dl	1.1	*/
5
6			/*
7			* Estimates the difference in time for compareAndSet and CAS-like
8			* operations versus unsynchronized, non-volatile pseudo-CAS when
9			* updating random numbers. These estimates thus give the cost
10			* of atomicity/barriers/exclusion over and above the time to
11			* just compare and conditionally store (int) values, so are
12			* not intended to measure the "raw" cost of a CAS.
13			*
14	dl	1.2	* Outputs, in nanoseconds:
15	dl	1.1	* "Atomic CAS" AtomicInteger.compareAndSet
16	dl	1.2	* "Updater CAS" CAS first comparing args
17	dl	1.1	* "Volatile" pseudo-CAS using volatile store if comparison succeeds
18			* "Mutex" emulated compare and set done under AQS-based mutex lock
19			* "Synchronized" emulated compare and set done under a synchronized block.
20			*
21	dl	1.2	* By default, these are printed for 1..#cpus threads, but you can
22			* change the upper bound number of threads by providing the
23			* first argument to this program.
24			*
25			* The last two kinds of runs (mutex and synchronized) are done only
26			* if this program is called with (any) second argument
27	dl	1.1	*/
28
29	jsr166	1.11	import java.util.concurrent.CyclicBarrier;
30	dl	1.1	import java.util.concurrent.atomic.AtomicInteger;
31	jsr166	1.9	import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
32	dl	1.1	import java.util.concurrent.atomic.AtomicLong;
33	jsr166	1.11	import java.util.concurrent.locks.AbstractQueuedSynchronizer;
34	dl	1.1
35			public class CASLoops {
36
37			static final int TRIALS = 2;
38			static final long BASE_SECS_PER_RUN = 4;
39			static final int NCPUS = Runtime.getRuntime().availableProcessors();
40	dl	1.2	static int maxThreads = NCPUS;
41	dl	1.1
42			static boolean includeLocks = false;
43
44			public static void main(String[] args) throws Exception {
45	jsr166	1.4	if (args.length > 0)
46	dl	1.2	maxThreads = Integer.parseInt(args[0]);
47
48	jsr166	1.6	loopIters = new long[maxThreads+1];
49	jsr166	1.3
50	dl	1.2	if (args.length > 1)
51	dl	1.1	includeLocks = true;
52
53			System.out.println("Warmup...");
54	dl	1.2	for (int i = maxThreads; i > 0; --i) {
55			runCalibration(i, 10);
56			oneRun(i, loopIters[i] / 4, false);
57			System.out.print(".");
58			}
59
60	jsr166	1.4	for (int i = 1; i <= maxThreads; ++i)
61	dl	1.2	loopIters[i] = 0;
62
63	dl	1.1	for (int j = 0; j < 2; ++j) {
64	dl	1.2	for (int i = 1; i <= maxThreads; ++i) {
65	dl	1.1	runCalibration(i, 1000);
66			oneRun(i, loopIters[i] / 8, false);
67	dl	1.2	System.out.print(".");
68	dl	1.1	}
69			}
70
71	jsr166	1.4	for (int i = 1; i <= maxThreads; ++i)
72	dl	1.1	loopIters[i] = 0;
73
74			for (int j = 0; j < TRIALS; ++j) {
75			System.out.println("Trial " + j);
76	dl	1.2	for (int i = 1; i <= maxThreads; ++i) {
77	dl	1.1	runCalibration(i, BASE_SECS_PER_RUN * 1000L);
78			oneRun(i, loopIters[i], true);
79			}
80			}
81			}
82
83			static final AtomicLong totalIters = new AtomicLong(0);
84			static final AtomicLong successes = new AtomicLong(0);
85			static final AtomicInteger sum = new AtomicInteger(0);
86
87			static final LoopHelpers.MarsagliaRandom rng = new LoopHelpers.MarsagliaRandom();
88
89	jsr166	1.3	static long[] loopIters;
90	dl	1.1
91			static final class NonAtomicInteger {
92			volatile int readBarrier;
93			int value;
94
95			NonAtomicInteger() {}
96			int get() {
97			int junk = readBarrier;
98			return value;
99			}
100			boolean compareAndSet(int cmp, int val) {
101			if (value == cmp) {
102			value = val;
103			return true;
104			}
105			return false;
106			}
107			void set(int val) { value = val; }
108			}
109
110	dl	1.2	static final class UpdaterAtomicInteger {
111			volatile int value;
112
113	jsr166	1.4	static final AtomicIntegerFieldUpdater<UpdaterAtomicInteger>
114	dl	1.2	valueUpdater = AtomicIntegerFieldUpdater.newUpdater
115			(UpdaterAtomicInteger.class, "value");
116
117			UpdaterAtomicInteger() {}
118			int get() {
119			return value;
120			}
121			boolean compareAndSet(int cmp, int val) {
122			return valueUpdater.compareAndSet(this, cmp, val);
123			}
124
125			void set(int val) { value = val; }
126			}
127
128	dl	1.1	static final class VolatileInteger {
129			volatile int value;
130
131			VolatileInteger() {}
132			int get() {
133			return value;
134			}
135			boolean compareAndSet(int cmp, int val) {
136			if (value == cmp) {
137			value = val;
138			return true;
139			}
140			return false;
141			}
142			void set(int val) { value = val; }
143			}
144
145			static final class SynchedInteger {
146			int value;
147
148			SynchedInteger() {}
149			int get() {
150			return value;
151			}
152			synchronized boolean compareAndSet(int cmp, int val) {
153			if (value == cmp) {
154			value = val;
155			return true;
156			}
157			return false;
158			}
159			synchronized void set(int val) { value = val; }
160			}
161
162			static final class LockedInteger extends AbstractQueuedSynchronizer {
163			int value;
164			LockedInteger() {}
165
166			public boolean tryAcquire(int acquires) {
167			return compareAndSetState(0, 1);
168			}
169			public boolean tryRelease(int releases) {
170			setState(0);
171			return true;
172			}
173			void lock() { acquire(1); }
174			void unlock() { release(1); }
175
176			int get() {
177			return value;
178			}
179			boolean compareAndSet(int cmp, int val) {
180			lock();
181			try {
182			if (value == cmp) {
183			value = val;
184			return true;
185			}
186			return false;
187			} finally {
188			unlock();
189			}
190			}
191	jsr166	1.4	void set(int val) {
192			lock();
193	dl	1.1	try {
194	jsr166	1.4	value = val;
195	dl	1.1	} finally {
196			unlock();
197			}
198			}
199			}
200
201	jsr166	1.4	// All these versions are copy-paste-hacked to avoid
202	dl	1.1	// contamination with virtual call resolution etc.
203
204			// Use fixed-length unrollable inner loops to reduce safepoint checks
205			static final int innerPerOuter = 16;
206
207			static final class NonAtomicLoop implements Runnable {
208			final long iters;
209			final NonAtomicInteger obj;
210			final CyclicBarrier barrier;
211			NonAtomicLoop(long iters, NonAtomicInteger obj, CyclicBarrier b) {
212			this.iters = iters;
213			this.obj = obj;
214			this.barrier = b;
215			obj.set(rng.next());
216			}
217
218			public void run() {
219			try {
220	jsr166	1.4	barrier.await();
221	dl	1.1	long i = iters;
222			int y = 0;
223			int succ = 0;
224			while (i > 0) {
225			for (int k = 0; k < innerPerOuter; ++k) {
226			int x = obj.get();
227			int z = y + LoopHelpers.compute6(x);
228			if (obj.compareAndSet(x, z))
229			++succ;
230			y = LoopHelpers.compute7(z);
231			}
232			i -= innerPerOuter;
233			}
234			sum.getAndAdd(obj.get());
235			successes.getAndAdd(succ);
236			barrier.await();
237			}
238	jsr166	1.4	catch (Exception ie) {
239			return;
240	dl	1.1	}
241			}
242			}
243
244			static final class AtomicLoop implements Runnable {
245			final long iters;
246			final AtomicInteger obj;
247			final CyclicBarrier barrier;
248			AtomicLoop(long iters, AtomicInteger obj, CyclicBarrier b) {
249			this.iters = iters;
250			this.obj = obj;
251			this.barrier = b;
252			obj.set(rng.next());
253			}
254
255			public void run() {
256			try {
257	jsr166	1.4	barrier.await();
258	dl	1.1	long i = iters;
259			int y = 0;
260			int succ = 0;
261			while (i > 0) {
262			for (int k = 0; k < innerPerOuter; ++k) {
263			int x = obj.get();
264			int z = y + LoopHelpers.compute6(x);
265			if (obj.compareAndSet(x, z))
266			++succ;
267			y = LoopHelpers.compute7(z);
268			}
269			i -= innerPerOuter;
270			}
271			sum.getAndAdd(obj.get());
272			successes.getAndAdd(succ);
273			barrier.await();
274			}
275	jsr166	1.4	catch (Exception ie) {
276			return;
277	dl	1.1	}
278			}
279			}
280
281	dl	1.2	static final class UpdaterAtomicLoop implements Runnable {
282			final long iters;
283			final UpdaterAtomicInteger obj;
284			final CyclicBarrier barrier;
285			UpdaterAtomicLoop(long iters, UpdaterAtomicInteger obj, CyclicBarrier b) {
286			this.iters = iters;
287			this.obj = obj;
288			this.barrier = b;
289			obj.set(rng.next());
290			}
291
292			public void run() {
293			try {
294	jsr166	1.4	barrier.await();
295	dl	1.2	long i = iters;
296			int y = 0;
297			int succ = 0;
298			while (i > 0) {
299			for (int k = 0; k < innerPerOuter; ++k) {
300			int x = obj.get();
301			int z = y + LoopHelpers.compute6(x);
302			if (obj.compareAndSet(x, z))
303			++succ;
304			y = LoopHelpers.compute7(z);
305			}
306			i -= innerPerOuter;
307			}
308			sum.getAndAdd(obj.get());
309			successes.getAndAdd(succ);
310			barrier.await();
311			}
312	jsr166	1.4	catch (Exception ie) {
313			return;
314	dl	1.2	}
315			}
316			}
317
318	dl	1.1	static final class VolatileLoop implements Runnable {
319			final long iters;
320			final VolatileInteger obj;
321			final CyclicBarrier barrier;
322			VolatileLoop(long iters, VolatileInteger obj, CyclicBarrier b) {
323			this.iters = iters;
324			this.obj = obj;
325			this.barrier = b;
326			obj.set(rng.next());
327			}
328
329			public void run() {
330			try {
331	jsr166	1.4	barrier.await();
332	dl	1.1	long i = iters;
333			int y = 0;
334			int succ = 0;
335			while (i > 0) {
336			for (int k = 0; k < innerPerOuter; ++k) {
337			int x = obj.get();
338			int z = y + LoopHelpers.compute6(x);
339			if (obj.compareAndSet(x, z))
340			++succ;
341			y = LoopHelpers.compute7(z);
342			}
343			i -= innerPerOuter;
344			}
345			sum.getAndAdd(obj.get());
346			successes.getAndAdd(succ);
347			barrier.await();
348			}
349	jsr166	1.4	catch (Exception ie) {
350			return;
351	dl	1.1	}
352			}
353			}
354
355			static final class SynchedLoop implements Runnable {
356			final long iters;
357			final SynchedInteger obj;
358			final CyclicBarrier barrier;
359			SynchedLoop(long iters, SynchedInteger obj, CyclicBarrier b) {
360			this.iters = iters;
361			this.obj = obj;
362			this.barrier = b;
363			obj.set(rng.next());
364			}
365
366			public void run() {
367			try {
368	jsr166	1.4	barrier.await();
369	dl	1.1	long i = iters;
370			int y = 0;
371			int succ = 0;
372			while (i > 0) {
373			for (int k = 0; k < innerPerOuter; ++k) {
374			int x = obj.get();
375			int z = y + LoopHelpers.compute6(x);
376			if (obj.compareAndSet(x, z))
377			++succ;
378			y = LoopHelpers.compute7(z);
379			}
380			i -= innerPerOuter;
381			}
382			sum.getAndAdd(obj.get());
383			successes.getAndAdd(succ);
384			barrier.await();
385			}
386	jsr166	1.4	catch (Exception ie) {
387			return;
388	dl	1.1	}
389			}
390			}
391
392			static final class LockedLoop implements Runnable {
393			final long iters;
394			final LockedInteger obj;
395			final CyclicBarrier barrier;
396			LockedLoop(long iters, LockedInteger obj, CyclicBarrier b) {
397			this.iters = iters;
398			this.obj = obj;
399			this.barrier = b;
400			obj.set(rng.next());
401			}
402
403			public void run() {
404			try {
405	jsr166	1.4	barrier.await();
406	dl	1.1	long i = iters;
407			int y = 0;
408			int succ = 0;
409			while (i > 0) {
410			for (int k = 0; k < innerPerOuter; ++k) {
411			int x = obj.get();
412			int z = y + LoopHelpers.compute6(x);
413			if (obj.compareAndSet(x, z))
414			++succ;
415			y = LoopHelpers.compute7(z);
416			}
417			i -= innerPerOuter;
418			}
419			sum.getAndAdd(obj.get());
420			successes.getAndAdd(succ);
421			barrier.await();
422			}
423	jsr166	1.4	catch (Exception ie) {
424			return;
425	dl	1.1	}
426			}
427			}
428
429			static final int loopsPerTimeCheck = 2048;
430
431			static final class NACalibrationLoop implements Runnable {
432			final long endTime;
433			final NonAtomicInteger obj;
434			final CyclicBarrier barrier;
435			NACalibrationLoop(long endTime, NonAtomicInteger obj, CyclicBarrier b) {
436			this.endTime = endTime;
437			this.obj = obj;
438			this.barrier = b;
439			obj.set(rng.next());
440			}
441
442			public void run() {
443			try {
444	jsr166	1.4	barrier.await();
445	dl	1.1	long iters = 0;
446			int y = 0;
447			int succ = 0;
448			do {
449			int i = loopsPerTimeCheck;
450			while (i > 0) {
451			for (int k = 0; k < innerPerOuter; ++k) {
452			int x = obj.get();
453			int z = y + LoopHelpers.compute6(x);
454			if (obj.compareAndSet(x, z))
455			++succ;
456			y = LoopHelpers.compute7(z);
457			}
458			i -= innerPerOuter;
459			}
460			iters += loopsPerTimeCheck;
461			} while (System.currentTimeMillis() < endTime);
462			totalIters.getAndAdd(iters);
463			sum.getAndAdd(obj.get());
464			successes.getAndAdd(succ);
465			barrier.await();
466			}
467	jsr166	1.4	catch (Exception ie) {
468			return;
469	dl	1.1	}
470			}
471			}
472
473			static void runCalibration(int n, long nms) throws Exception {
474			long now = System.currentTimeMillis();
475			long endTime = now + nms;
476			CyclicBarrier b = new CyclicBarrier(n+1);
477			totalIters.set(0);
478			NonAtomicInteger a = new NonAtomicInteger();
479	jsr166	1.4	for (int j = 0; j < n; ++j)
480	dl	1.1	new Thread(new NACalibrationLoop(endTime, a, b)).start();
481			b.await();
482			b.await();
483			long ipt = totalIters.get() / n;
484			if (ipt > loopIters[n])
485			loopIters[n] = ipt;
486			if (sum.get() == 0) System.out.print(" ");
487			}
488
489			static long runNonAtomic(int n, long iters) throws Exception {
490			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
491			CyclicBarrier b = new CyclicBarrier(n+1, timer);
492			NonAtomicInteger a = new NonAtomicInteger();
493	jsr166	1.4	for (int j = 0; j < n; ++j)
494	dl	1.1	new Thread(new NonAtomicLoop(iters, a, b)).start();
495			b.await();
496			b.await();
497			if (sum.get() == 0) System.out.print(" ");
498			return timer.getTime();
499			}
500
501	dl	1.2	static long runUpdaterAtomic(int n, long iters) throws Exception {
502			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
503			CyclicBarrier b = new CyclicBarrier(n+1, timer);
504			UpdaterAtomicInteger a = new UpdaterAtomicInteger();
505	jsr166	1.4	for (int j = 0; j < n; ++j)
506	dl	1.2	new Thread(new UpdaterAtomicLoop(iters, a, b)).start();
507			b.await();
508			b.await();
509			if (sum.get() == 0) System.out.print(" ");
510			return timer.getTime();
511			}
512
513	dl	1.1	static long runAtomic(int n, long iters) throws Exception {
514			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
515			CyclicBarrier b = new CyclicBarrier(n+1, timer);
516			AtomicInteger a = new AtomicInteger();
517	jsr166	1.4	for (int j = 0; j < n; ++j)
518	dl	1.1	new Thread(new AtomicLoop(iters, a, b)).start();
519			b.await();
520			b.await();
521			if (sum.get() == 0) System.out.print(" ");
522			return timer.getTime();
523			}
524
525			static long runVolatile(int n, long iters) throws Exception {
526			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
527			CyclicBarrier b = new CyclicBarrier(n+1, timer);
528			VolatileInteger a = new VolatileInteger();
529	jsr166	1.4	for (int j = 0; j < n; ++j)
530	dl	1.1	new Thread(new VolatileLoop(iters, a, b)).start();
531			b.await();
532			b.await();
533			if (sum.get() == 0) System.out.print(" ");
534			return timer.getTime();
535			}
536
537			static long runSynched(int n, long iters) throws Exception {
538			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
539			CyclicBarrier b = new CyclicBarrier(n+1, timer);
540			SynchedInteger a = new SynchedInteger();
541	jsr166	1.4	for (int j = 0; j < n; ++j)
542	dl	1.1	new Thread(new SynchedLoop(iters, a, b)).start();
543			b.await();
544			b.await();
545			if (sum.get() == 0) System.out.print(" ");
546			return timer.getTime();
547			}
548
549			static long runLocked(int n, long iters) throws Exception {
550			LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
551			CyclicBarrier b = new CyclicBarrier(n+1, timer);
552			LockedInteger a = new LockedInteger();
553	jsr166	1.4	for (int j = 0; j < n; ++j)
554	dl	1.1	new Thread(new LockedLoop(iters, a, b)).start();
555			b.await();
556			b.await();
557			if (sum.get() == 0) System.out.print(" ");
558			return timer.getTime();
559			}
560
561	jsr166	1.4	static void report(String tag, long runtime, long basetime,
562	dl	1.2	int nthreads, long iters) {
563	dl	1.1	System.out.print(tag);
564	dl	1.2	long t = (runtime - basetime) / iters;
565			if (nthreads > NCPUS)
566			t = t * NCPUS / nthreads;
567			System.out.print(LoopHelpers.rightJustify(t));
568	jsr166	1.5	double secs = (double) runtime / 1000000000.0;
569	dl	1.1	System.out.println("\t " + secs + "s run time");
570			}
571	jsr166	1.4
572	dl	1.1	static void oneRun(int i, long iters, boolean print) throws Exception {
573	jsr166	1.4	if (print)
574			System.out.println("threads : " + i +
575			" base iters per thread per run : " +
576	dl	1.2	LoopHelpers.rightJustify(loopIters[i]));
577	jsr166	1.8	long ntime = runNonAtomic(i, iters);
578	dl	1.1	if (print)
579	dl	1.2	report("Base : ", ntime, ntime, i, iters);
580	dl	1.1	Thread.sleep(100L);
581			long atime = runAtomic(i, iters);
582			if (print)
583	dl	1.2	report("Atomic CAS : ", atime, ntime, i, iters);
584			Thread.sleep(100L);
585			long gtime = runUpdaterAtomic(i, iters);
586			if (print)
587			report("Updater CAS : ", gtime, ntime, i, iters);
588	dl	1.1	Thread.sleep(100L);
589			long vtime = runVolatile(i, iters);
590			if (print)
591	dl	1.2	report("Volatile : ", vtime, ntime, i, iters);
592	dl	1.1
593			Thread.sleep(100L);
594			if (!includeLocks) return;
595			long mtime = runLocked(i, iters);
596			if (print)
597	dl	1.2	report("Mutex : ", mtime, ntime, i, iters);
598	dl	1.1	Thread.sleep(100L);
599			long stime = runSynched(i, iters);
600	jsr166	1.4	if (print)
601	dl	1.2	report("Synchronized: ", stime, ntime, i, iters);
602	dl	1.1	Thread.sleep(100L);
603			}
604			}