src/loops/ALoops.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

import java.util.concurrent.*;
import java.util.concurrent.locks.*;
import java.util.concurrent.atomic.*;
import java.util.*;

public final class ALoops {
    static final ExecutorService pool = Executors.newCachedThreadPool();
    static final LoopHelpers.SimpleRandom rng = new LoopHelpers.SimpleRandom();
    static boolean print = false;
    static int iters = 2000000;
    static int mask = 0;
    static long loopTime = Long.MAX_VALUE;
    static final long NCPU = Runtime.getRuntime().availableProcessors();

    public static void main(String[] args) throws Exception {
        int maxThreads = 100;
        if (args.length > 0)
            maxThreads = Integer.parseInt(args[0]);

        if (args.length > 1)
            mask = Integer.parseInt(args[1]);

                System.out.println("Running ALoops.main with these values:");
                System.out.println("Mask: " + mask + " CPUs: " + NCPU + " Iters: " + iters + " MaxThreads: " + maxThreads);
                System.out.println("\n");

        warmup();
        print = true;

        for (int m = 1; m <= 256; m <<= 1) {
            mask = m - 1;
            System.out.println("Mask: " + mask + " CPUs: " + NCPU + " Iters: " + iters + " MaxThreads: " + maxThreads);


            int k = 1;
            for (int i = 1; i <= maxThreads;) {
                System.out.println("Threads: " + i);
                new Loop(1).test();
                if (i <= 4)
                    new CASLoop(i).test();
                new ReentrantLockLoop(i).test();
                new LockLoop(i).test();
                new MutexLoop(i).test();
                if (i == k) {
                    k = i << 1;
                    i = i + (i >>> 1);
                }
                else
                    i = k;
            }
        }

        pool.shutdown();
    }

    static void warmup() throws Exception {
        for (int i = 0; i < 30; ++i)
            new Loop(1).test();

        for (int i = 0; i < 30; ++i)
            new CASLoop(1).test();

        for (int i = 0; i < 30; ++i)
            new MutexLoop(1).test();

        for (int i = 0; i < 30; ++i)
            new ReentrantLockLoop(1).test();

        for (int i = 0; i < 30; ++i)
            new LockLoop(1).test();

        for (int i = 0; i < 30; ++i)
            new Loop(1).test();
    }

    private static int nextRandom(int x) {
        int t = (x % 127773) * 16807 - (x / 127773) * 2836;
        return (t > 0) ? t : t + 0x7fffffff;
    }


    private static double ratio(int n, long t) {
        double s = 1.0 / (1.0 + (double) mask);
        double ns = 1.0 - s;
        double seq = loopTime * s * n;
        double ideal;
        if (n <= NCPU)
            ideal = seq + loopTime * ns;
        else
            ideal = seq + loopTime * ns * n / NCPU;
        return (double)t / ideal;
    }

    private static void printTimes(String label, long tpi, double ratio) {
        if (print) {
            System.out.println(label + "\t" +
                               LoopHelpers.rightJustify(tpi) +
                               " \t" + ratio);
        }
    }

    private static void useResult(int r) {
        if (r == 0) // avoid overoptimization
            System.out.println("useless result: " + r);
        try {
            Thread.sleep(100);
        } catch (InterruptedException ex) {}

    }


    static final class Loop implements Runnable {
        private int v = rng.next();
        private volatile int result = 17;
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        Loop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            if (nthreads == 1 && time < loopTime) loopTime = time;
            long tpi = time / ((long)iters * nthreads);
            printTimes("Loop", tpi, 0.0);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v;
                int n = iters;
                while (n-- > 0) {
                    if ((x & mask) == 0) {
                        v = x = nextRandom(v);
                    }
                    else
                        x = nextRandom(x);
                }
                barrier.await();
                result += x + v;
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static final class ReentrantLockLoop implements Runnable {
        private int v = rng.next();
        private volatile int result = 17;
        private final ReentrantLock lock = new ReentrantLock();
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        ReentrantLockLoop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            long tpi = (time - loopTime) / ((long)iters * nthreads);
            double ratio = ratio(nthreads, time);
            printTimes("RL", tpi, ratio);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v;
                final ReentrantLock lock = this.lock;
                int n = iters;
                int m = mask;
                while (n-- > 0) {
                    if ((x & m) == 0) {
                        lock.lock();
                        v = x = nextRandom(v);
                        lock.unlock();
                    }
                    else
                        x = nextRandom(x);
                }
                barrier.await();
                result += x + v;
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static final class LockLoop implements Runnable {
        private int v = rng.next();
        private volatile int result = 17;
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        LockLoop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            long tpi = (time - loopTime) / (((long)iters) * nthreads);
            double ratio = ratio(nthreads, time);
            printTimes("Sync", tpi, ratio);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v;
                int n = iters;
                int m = mask;
                while (n-- > 0) {
                    if ((x & m) == 0) {
                        synchronized (this) {
                            v = x = nextRandom(v);
                        }
                    }
                    else
                        x = nextRandom(x);
                }
                barrier.await();
                result += x + v;
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static final class MutexLoop implements Runnable {
        private int v = rng.next();
        private volatile int result = 17;
        private final Mutex lock = new Mutex();
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        MutexLoop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            long tpi = (time - loopTime) / ((long)iters * nthreads);
            double ratio = ratio(nthreads, time);
            printTimes("Mutex", tpi, ratio);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v;
                final Mutex lock = this.lock;
                int n = iters;
                int m = mask;
                while (n-- > 0) {
                    if ((x & m) == 0) {
                        lock.lock();
                        v = x = nextRandom(v);
                        lock.unlock();
                    }
                    else
                        x = nextRandom(x);
                }
                barrier.await();
                result += x + v;
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static final class FairReentrantLockLoop implements Runnable {
        private int v = rng.next();
        private volatile int result = 17;
        private final ReentrantLock lock = new ReentrantLock(true);
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        FairReentrantLockLoop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            long tpi = (time - loopTime) / (((long)iters) * nthreads);
            double ratio = ratio(nthreads, time);
            printTimes("FairRL", tpi, ratio);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v;
                final ReentrantLock lock = this.lock;
                int n = iters;
                int m = mask;
                while (n-- > 0) {
                    if ((x & m) == 0) {
                        lock.lock();
                        v = x = nextRandom(v);
                        lock.unlock();
                    }
                    else
                        x = nextRandom(x);
                }
                barrier.await();
                result += x + v;
            }
            catch (Exception ie) {
                return;
            }
        }
    }

    static final class CASLoop implements Runnable {
        private final AtomicInteger v = new AtomicInteger(rng.next());
        private volatile int result = 17;
        private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        private final CyclicBarrier barrier;
        private final int nthreads;
        private volatile int readBarrier;
        CASLoop(int nthreads) {
            this.nthreads = nthreads;
            barrier = new CyclicBarrier(nthreads+1, timer);
        }

        final void test() throws Exception {
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            long tpi = (time - loopTime) / ((long)iters * nthreads);
            double ratio = ratio(nthreads, time);
            printTimes("CAS", tpi, ratio);
            useResult(result);
        }

        public final void run() {
            try {
                barrier.await();
                int x = v.get();
                int n = iters;
                int m = mask;
                while (n > 0) {
                    if ((x & m) == 0) {
                        int oldx = v.get();
                        int newx = nextRandom(oldx);
                        if (v.compareAndSet(oldx, newx)) {
                            x = newx;
                            --n;
                        }
                    }
                    else {
                        x = nextRandom(x);
                        --n;
                    }
                }
                barrier.await();
                result += x + v.get();
            }
            catch (Exception ie) {
                return;
            }
        }
    }

}
Revision:	1.6
Committed:	Sat Feb 16 21:37:44 2013 UTC (11 years, 3 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.5:	+6 -0 lines
Log Message:	add missing public domain notices
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/publicdomain/zero/1.0/
5	*/
6
7	import java.util.concurrent.*;
8	import java.util.concurrent.locks.*;
9	import java.util.concurrent.atomic.*;
10	import java.util.*;
11
12	public final class ALoops {
13	static final ExecutorService pool = Executors.newCachedThreadPool();
14	static final LoopHelpers.SimpleRandom rng = new LoopHelpers.SimpleRandom();
15	static boolean print = false;
16	static int iters = 2000000;
17	static int mask = 0;
18	static long loopTime = Long.MAX_VALUE;
19	static final long NCPU = Runtime.getRuntime().availableProcessors();
20
21	public static void main(String[] args) throws Exception {
22	int maxThreads = 100;
23	if (args.length > 0)
24	maxThreads = Integer.parseInt(args[0]);
25
26	if (args.length > 1)
27	mask = Integer.parseInt(args[1]);
28
29	System.out.println("Running ALoops.main with these values:");
30	System.out.println("Mask: " + mask + " CPUs: " + NCPU + " Iters: " + iters + " MaxThreads: " + maxThreads);
31	System.out.println("\n");
32
33	warmup();
34	print = true;
35
36	for (int m = 1; m <= 256; m <<= 1) {
37	mask = m - 1;
38	System.out.println("Mask: " + mask + " CPUs: " + NCPU + " Iters: " + iters + " MaxThreads: " + maxThreads);
39
40
41	int k = 1;
42	for (int i = 1; i <= maxThreads;) {
43	System.out.println("Threads: " + i);
44	new Loop(1).test();
45	if (i <= 4)
46	new CASLoop(i).test();
47	new ReentrantLockLoop(i).test();
48	new LockLoop(i).test();
49	new MutexLoop(i).test();
50	if (i == k) {
51	k = i << 1;
52	i = i + (i >>> 1);
53	}
54	else
55	i = k;
56	}
57	}
58
59	pool.shutdown();
60	}
61
62	static void warmup() throws Exception {
63	for (int i = 0; i < 30; ++i)
64	new Loop(1).test();
65
66	for (int i = 0; i < 30; ++i)
67	new CASLoop(1).test();
68
69	for (int i = 0; i < 30; ++i)
70	new MutexLoop(1).test();
71
72	for (int i = 0; i < 30; ++i)
73	new ReentrantLockLoop(1).test();
74
75	for (int i = 0; i < 30; ++i)
76	new LockLoop(1).test();
77
78	for (int i = 0; i < 30; ++i)
79	new Loop(1).test();
80	}
81
82	private static int nextRandom(int x) {
83	int t = (x % 127773) * 16807 - (x / 127773) * 2836;
84	return (t > 0) ? t : t + 0x7fffffff;
85	}
86
87
88
89	private static double ratio(int n, long t) {
90	double s = 1.0 / (1.0 + (double) mask);
91	double ns = 1.0 - s;
92	double seq = loopTime * s * n;
93	double ideal;
94	if (n <= NCPU)
95	ideal = seq + loopTime * ns;
96	else
97	ideal = seq + loopTime * ns * n / NCPU;
98	return (double)t / ideal;
99	}
100
101	private static void printTimes(String label, long tpi, double ratio) {
102	if (print) {
103	System.out.println(label + "\t" +
104	LoopHelpers.rightJustify(tpi) +
105	" \t" + ratio);
106	}
107	}
108
109	private static void useResult(int r) {
110	if (r == 0) // avoid overoptimization
111	System.out.println("useless result: " + r);
112	try {
113	Thread.sleep(100);
114	} catch (InterruptedException ex) {}
115
116	}
117
118
119	static final class Loop implements Runnable {
120	private int v = rng.next();
121	private volatile int result = 17;
122	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
123	private final CyclicBarrier barrier;
124	private final int nthreads;
125	private volatile int readBarrier;
126	Loop(int nthreads) {
127	this.nthreads = nthreads;
128	barrier = new CyclicBarrier(nthreads+1, timer);
129	}
130
131	final void test() throws Exception {
132	for (int i = 0; i < nthreads; ++i)
133	pool.execute(this);
134	barrier.await();
135	barrier.await();
136	long time = timer.getTime();
137	if (nthreads == 1 && time < loopTime) loopTime = time;
138	long tpi = time / ((long)iters * nthreads);
139	printTimes("Loop", tpi, 0.0);
140	useResult(result);
141	}
142
143	public final void run() {
144	try {
145	barrier.await();
146	int x = v;
147	int n = iters;
148	while (n-- > 0) {
149	if ((x & mask) == 0) {
150	v = x = nextRandom(v);
151	}
152	else
153	x = nextRandom(x);
154	}
155	barrier.await();
156	result += x + v;
157	}
158	catch (Exception ie) {
159	return;
160	}
161	}
162	}
163
164	static final class ReentrantLockLoop implements Runnable {
165	private int v = rng.next();
166	private volatile int result = 17;
167	private final ReentrantLock lock = new ReentrantLock();
168	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
169	private final CyclicBarrier barrier;
170	private final int nthreads;
171	private volatile int readBarrier;
172	ReentrantLockLoop(int nthreads) {
173	this.nthreads = nthreads;
174	barrier = new CyclicBarrier(nthreads+1, timer);
175	}
176
177	final void test() throws Exception {
178	for (int i = 0; i < nthreads; ++i)
179	pool.execute(this);
180	barrier.await();
181	barrier.await();
182	long time = timer.getTime();
183	long tpi = (time - loopTime) / ((long)iters * nthreads);
184	double ratio = ratio(nthreads, time);
185	printTimes("RL", tpi, ratio);
186	useResult(result);
187	}
188
189	public final void run() {
190	try {
191	barrier.await();
192	int x = v;
193	final ReentrantLock lock = this.lock;
194	int n = iters;
195	int m = mask;
196	while (n-- > 0) {
197	if ((x & m) == 0) {
198	lock.lock();
199	v = x = nextRandom(v);
200	lock.unlock();
201	}
202	else
203	x = nextRandom(x);
204	}
205	barrier.await();
206	result += x + v;
207	}
208	catch (Exception ie) {
209	return;
210	}
211	}
212	}
213
214	static final class LockLoop implements Runnable {
215	private int v = rng.next();
216	private volatile int result = 17;
217	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
218	private final CyclicBarrier barrier;
219	private final int nthreads;
220	private volatile int readBarrier;
221	LockLoop(int nthreads) {
222	this.nthreads = nthreads;
223	barrier = new CyclicBarrier(nthreads+1, timer);
224	}
225
226	final void test() throws Exception {
227	for (int i = 0; i < nthreads; ++i)
228	pool.execute(this);
229	barrier.await();
230	barrier.await();
231	long time = timer.getTime();
232	long tpi = (time - loopTime) / (((long)iters) * nthreads);
233	double ratio = ratio(nthreads, time);
234	printTimes("Sync", tpi, ratio);
235	useResult(result);
236	}
237
238	public final void run() {
239	try {
240	barrier.await();
241	int x = v;
242	int n = iters;
243	int m = mask;
244	while (n-- > 0) {
245	if ((x & m) == 0) {
246	synchronized (this) {
247	v = x = nextRandom(v);
248	}
249	}
250	else
251	x = nextRandom(x);
252	}
253	barrier.await();
254	result += x + v;
255	}
256	catch (Exception ie) {
257	return;
258	}
259	}
260	}
261
262	static final class MutexLoop implements Runnable {
263	private int v = rng.next();
264	private volatile int result = 17;
265	private final Mutex lock = new Mutex();
266	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
267	private final CyclicBarrier barrier;
268	private final int nthreads;
269	private volatile int readBarrier;
270	MutexLoop(int nthreads) {
271	this.nthreads = nthreads;
272	barrier = new CyclicBarrier(nthreads+1, timer);
273	}
274
275	final void test() throws Exception {
276	for (int i = 0; i < nthreads; ++i)
277	pool.execute(this);
278	barrier.await();
279	barrier.await();
280	long time = timer.getTime();
281	long tpi = (time - loopTime) / ((long)iters * nthreads);
282	double ratio = ratio(nthreads, time);
283	printTimes("Mutex", tpi, ratio);
284	useResult(result);
285	}
286
287	public final void run() {
288	try {
289	barrier.await();
290	int x = v;
291	final Mutex lock = this.lock;
292	int n = iters;
293	int m = mask;
294	while (n-- > 0) {
295	if ((x & m) == 0) {
296	lock.lock();
297	v = x = nextRandom(v);
298	lock.unlock();
299	}
300	else
301	x = nextRandom(x);
302	}
303	barrier.await();
304	result += x + v;
305	}
306	catch (Exception ie) {
307	return;
308	}
309	}
310	}
311
312	static final class FairReentrantLockLoop implements Runnable {
313	private int v = rng.next();
314	private volatile int result = 17;
315	private final ReentrantLock lock = new ReentrantLock(true);
316	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
317	private final CyclicBarrier barrier;
318	private final int nthreads;
319	private volatile int readBarrier;
320	FairReentrantLockLoop(int nthreads) {
321	this.nthreads = nthreads;
322	barrier = new CyclicBarrier(nthreads+1, timer);
323	}
324
325	final void test() throws Exception {
326	for (int i = 0; i < nthreads; ++i)
327	pool.execute(this);
328	barrier.await();
329	barrier.await();
330	long time = timer.getTime();
331	long tpi = (time - loopTime) / (((long)iters) * nthreads);
332	double ratio = ratio(nthreads, time);
333	printTimes("FairRL", tpi, ratio);
334	useResult(result);
335	}
336
337	public final void run() {
338	try {
339	barrier.await();
340	int x = v;
341	final ReentrantLock lock = this.lock;
342	int n = iters;
343	int m = mask;
344	while (n-- > 0) {
345	if ((x & m) == 0) {
346	lock.lock();
347	v = x = nextRandom(v);
348	lock.unlock();
349	}
350	else
351	x = nextRandom(x);
352	}
353	barrier.await();
354	result += x + v;
355	}
356	catch (Exception ie) {
357	return;
358	}
359	}
360	}
361
362	static final class CASLoop implements Runnable {
363	private final AtomicInteger v = new AtomicInteger(rng.next());
364	private volatile int result = 17;
365	private final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
366	private final CyclicBarrier barrier;
367	private final int nthreads;
368	private volatile int readBarrier;
369	CASLoop(int nthreads) {
370	this.nthreads = nthreads;
371	barrier = new CyclicBarrier(nthreads+1, timer);
372	}
373
374	final void test() throws Exception {
375	for (int i = 0; i < nthreads; ++i)
376	pool.execute(this);
377	barrier.await();
378	barrier.await();
379	long time = timer.getTime();
380	long tpi = (time - loopTime) / ((long)iters * nthreads);
381	double ratio = ratio(nthreads, time);
382	printTimes("CAS", tpi, ratio);
383	useResult(result);
384	}
385
386	public final void run() {
387	try {
388	barrier.await();
389	int x = v.get();
390	int n = iters;
391	int m = mask;
392	while (n > 0) {
393	if ((x & m) == 0) {
394	int oldx = v.get();
395	int newx = nextRandom(oldx);
396	if (v.compareAndSet(oldx, newx)) {
397	x = newx;
398	--n;
399	}
400	}
401	else {
402	x = nextRandom(x);
403	--n;
404	}
405	}
406	barrier.await();
407	result += x + v.get();
408	}
409	catch (Exception ie) {
410	return;
411	}
412	}
413	}
414
415	}