test/loops/CASLoops.java

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

/*
 * 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.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
import java.util.concurrent.*;
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.4
Committed:	Thu Oct 29 23:09:07 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+42 -42 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea and released to the public domain, as explained at
3			* http://creativecommons.org/licenses/publicdomain
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	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
30			import java.util.concurrent.atomic.AtomicInteger;
31			import java.util.concurrent.atomic.AtomicLong;
32	dl	1.2	import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
33	dl	1.1	import java.util.concurrent.*;
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	dl	1.2	static int maxThreads = NCPUS;
42	dl	1.1
43			static boolean includeLocks = false;
44
45			public static void main(String[] args) throws Exception {
46	jsr166	1.4	if (args.length > 0)
47	dl	1.2	maxThreads = Integer.parseInt(args[0]);
48
49	jsr166	1.3	loopIters = new long[maxThreads+1];
50
51	dl	1.2	if (args.length > 1)
52	dl	1.1	includeLocks = true;
53
54			System.out.println("Warmup...");
55	dl	1.2	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	jsr166	1.4	for (int i = 1; i <= maxThreads; ++i)
62	dl	1.2	loopIters[i] = 0;
63
64	dl	1.1	for (int j = 0; j < 2; ++j) {
65	dl	1.2	for (int i = 1; i <= maxThreads; ++i) {
66	dl	1.1	runCalibration(i, 1000);
67			oneRun(i, loopIters[i] / 8, false);
68	dl	1.2	System.out.print(".");
69	dl	1.1	}
70			}
71
72	jsr166	1.4	for (int i = 1; i <= maxThreads; ++i)
73	dl	1.1	loopIters[i] = 0;
74
75			for (int j = 0; j < TRIALS; ++j) {
76			System.out.println("Trial " + j);
77	dl	1.2	for (int i = 1; i <= maxThreads; ++i) {
78	dl	1.1	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	jsr166	1.3	static long[] loopIters;
91	dl	1.1
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	dl	1.2	static final class UpdaterAtomicInteger {
112			volatile int value;
113
114	jsr166	1.4	static final AtomicIntegerFieldUpdater<UpdaterAtomicInteger>
115	dl	1.2	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	dl	1.1	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	jsr166	1.4	void set(int val) {
195			lock();
196	dl	1.1	try {
197	jsr166	1.4	value = val;
198	dl	1.1	} finally {
199			unlock();
200			}
201			}
202			}
203
204	jsr166	1.4	// All these versions are copy-paste-hacked to avoid
205	dl	1.1	// 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	jsr166	1.4	barrier.await();
224	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
242			return;
243	dl	1.1	}
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	jsr166	1.4	barrier.await();
261	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
279			return;
280	dl	1.1	}
281			}
282			}
283
284	dl	1.2	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	jsr166	1.4	barrier.await();
298	dl	1.2	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	jsr166	1.4	catch (Exception ie) {
316			return;
317	dl	1.2	}
318			}
319			}
320
321	dl	1.1	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	jsr166	1.4	barrier.await();
335	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
353			return;
354	dl	1.1	}
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	jsr166	1.4	barrier.await();
372	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
390			return;
391	dl	1.1	}
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	jsr166	1.4	barrier.await();
409	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
427			return;
428	dl	1.1	}
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	jsr166	1.4	barrier.await();
448	dl	1.1	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	jsr166	1.4	catch (Exception ie) {
471			return;
472	dl	1.1	}
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	jsr166	1.4	for (int j = 0; j < n; ++j)
483	dl	1.1	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	jsr166	1.4	for (int j = 0; j < n; ++j)
497	dl	1.1	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	dl	1.2	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	jsr166	1.4	for (int j = 0; j < n; ++j)
509	dl	1.2	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	dl	1.1	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	jsr166	1.4	for (int j = 0; j < n; ++j)
521	dl	1.1	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	jsr166	1.4	for (int j = 0; j < n; ++j)
533	dl	1.1	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	jsr166	1.4	for (int j = 0; j < n; ++j)
546	dl	1.1	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	jsr166	1.4	for (int j = 0; j < n; ++j)
558	dl	1.1	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	jsr166	1.4	static void report(String tag, long runtime, long basetime,
566	dl	1.2	int nthreads, long iters) {
567	dl	1.1	System.out.print(tag);
568	dl	1.2	long t = (runtime - basetime) / iters;
569			if (nthreads > NCPUS)
570			t = t * NCPUS / nthreads;
571			System.out.print(LoopHelpers.rightJustify(t));
572	dl	1.1	double secs = (double)(runtime) / 1000000000.0;
573			System.out.println("\t " + secs + "s run time");
574			}
575	jsr166	1.4
576	dl	1.1
577			static void oneRun(int i, long iters, boolean print) throws Exception {
578	jsr166	1.4	if (print)
579			System.out.println("threads : " + i +
580			" base iters per thread per run : " +
581	dl	1.2	LoopHelpers.rightJustify(loopIters[i]));
582	dl	1.1	long ntime = runNonAtomic(i, iters);
583			if (print)
584	dl	1.2	report("Base : ", ntime, ntime, i, iters);
585	dl	1.1	Thread.sleep(100L);
586			long atime = runAtomic(i, iters);
587			if (print)
588	dl	1.2	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	dl	1.1	Thread.sleep(100L);
594			long vtime = runVolatile(i, iters);
595			if (print)
596	dl	1.2	report("Volatile : ", vtime, ntime, i, iters);
597	dl	1.1
598			Thread.sleep(100L);
599			if (!includeLocks) return;
600			long mtime = runLocked(i, iters);
601			if (print)
602	dl	1.2	report("Mutex : ", mtime, ntime, i, iters);
603	dl	1.1	Thread.sleep(100L);
604			long stime = runSynched(i, iters);
605	jsr166	1.4	if (print)
606	dl	1.2	report("Synchronized: ", stime, ntime, i, iters);
607	dl	1.1	Thread.sleep(100L);
608			}
609
610
611			}