src/loops/ALoops.java

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