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.1
Committed:	Fri Apr 9 20:12:06 2004 UTC (20 years, 2 months ago) by jsr166
Branch:	MAIN
Log Message:	Add ALoops benchmark to src/loops, target 'loops' already in build.xml
#	User	Rev	Content
1	jsr166	1.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			}