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
#	Content
1	/*
2	* Written by Doug Lea and released to the public domain, as explained at
3	* http://creativecommons.org/publicdomain/zero/1.0/
4	*/
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	* Outputs, in nanoseconds:
15	* "Atomic CAS" AtomicInteger.compareAndSet
16	* "Updater CAS" CAS first comparing args
17	* "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	* 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	*/
28
29	import java.util.concurrent.CyclicBarrier;
30	import java.util.concurrent.atomic.AtomicInteger;
31	import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
32	import java.util.concurrent.atomic.AtomicLong;
33	import java.util.concurrent.locks.AbstractQueuedSynchronizer;
34
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	static int maxThreads = NCPUS;
41
42	static boolean includeLocks = false;
43
44	public static void main(String[] args) throws Exception {
45	if (args.length > 0)
46	maxThreads = Integer.parseInt(args[0]);
47
48	loopIters = new long[maxThreads+1];
49
50	if (args.length > 1)
51	includeLocks = true;
52
53	System.out.println("Warmup...");
54	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	for (int i = 1; i <= maxThreads; ++i)
61	loopIters[i] = 0;
62
63	for (int j = 0; j < 2; ++j) {
64	for (int i = 1; i <= maxThreads; ++i) {
65	runCalibration(i, 1000);
66	oneRun(i, loopIters[i] / 8, false);
67	System.out.print(".");
68	}
69	}
70
71	for (int i = 1; i <= maxThreads; ++i)
72	loopIters[i] = 0;
73
74	for (int j = 0; j < TRIALS; ++j) {
75	System.out.println("Trial " + j);
76	for (int i = 1; i <= maxThreads; ++i) {
77	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	static long[] loopIters;
90
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	static final class UpdaterAtomicInteger {
111	volatile int value;
112
113	static final AtomicIntegerFieldUpdater<UpdaterAtomicInteger>
114	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	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	void set(int val) {
192	lock();
193	try {
194	value = val;
195	} finally {
196	unlock();
197	}
198	}
199	}
200
201	// All these versions are copy-paste-hacked to avoid
202	// 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	barrier.await();
221	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	catch (Exception ie) {
239	return;
240	}
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	barrier.await();
258	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	catch (Exception ie) {
276	return;
277	}
278	}
279	}
280
281	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	barrier.await();
295	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	catch (Exception ie) {
313	return;
314	}
315	}
316	}
317
318	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	barrier.await();
332	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	catch (Exception ie) {
350	return;
351	}
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	barrier.await();
369	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	catch (Exception ie) {
387	return;
388	}
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	barrier.await();
406	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	catch (Exception ie) {
424	return;
425	}
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	barrier.await();
445	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	catch (Exception ie) {
468	return;
469	}
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	for (int j = 0; j < n; ++j)
480	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	for (int j = 0; j < n; ++j)
494	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	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	for (int j = 0; j < n; ++j)
506	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	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	for (int j = 0; j < n; ++j)
518	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	for (int j = 0; j < n; ++j)
530	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	for (int j = 0; j < n; ++j)
542	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	for (int j = 0; j < n; ++j)
554	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	static void report(String tag, long runtime, long basetime,
562	int nthreads, long iters) {
563	System.out.print(tag);
564	long t = (runtime - basetime) / iters;
565	if (nthreads > NCPUS)
566	t = t * NCPUS / nthreads;
567	System.out.print(LoopHelpers.rightJustify(t));
568	double secs = (double) runtime / 1000000000.0;
569	System.out.println("\t " + secs + "s run time");
570	}
571
572	static void oneRun(int i, long iters, boolean print) throws Exception {
573	if (print)
574	System.out.println("threads : " + i +
575	" base iters per thread per run : " +
576	LoopHelpers.rightJustify(loopIters[i]));
577	long ntime = runNonAtomic(i, iters);
578	if (print)
579	report("Base : ", ntime, ntime, i, iters);
580	Thread.sleep(100L);
581	long atime = runAtomic(i, iters);
582	if (print)
583	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	Thread.sleep(100L);
589	long vtime = runVolatile(i, iters);
590	if (print)
591	report("Volatile : ", vtime, ntime, i, iters);
592
593	Thread.sleep(100L);
594	if (!includeLocks) return;
595	long mtime = runLocked(i, iters);
596	if (print)
597	report("Mutex : ", mtime, ntime, i, iters);
598	Thread.sleep(100L);
599	long stime = runSynched(i, iters);
600	if (print)
601	report("Synchronized: ", stime, ntime, i, iters);
602	Thread.sleep(100L);
603	}
604	}