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.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.*;

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