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]);

        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 final long[] loopIters = new long[maxThreads+1];

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