test/loops/CheckedLockLoops.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/licenses/publicdomain
 */
/*
 * @test
 * @summary basic safety and liveness of ReentrantLocks, and other locks based on them
 */

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

public final class CheckedLockLoops {
    static final ExecutorService pool = Executors.newCachedThreadPool();
    static final LoopHelpers.SimpleRandom rng = new LoopHelpers.SimpleRandom();
    static boolean print = false;
    static boolean doBuiltin = true;

    public static void main(String[] args) throws Exception {
        int maxThreads = 100;
        int iters = 2000000;
        if (args.length > 0)
            maxThreads = Integer.parseInt(args[0]);
        rng.setSeed(3122688L);
        warmup(iters);
        runTest(maxThreads, iters);
        pool.shutdown();
    }

    static void runTest(int maxThreads, int iters) throws Exception {
        print = true;
        int k = 1;
        for (int i = 1; i <= maxThreads;) {
            System.out.println("Threads:" + i);
            oneTest(i, iters / i);
            if (i == k) {
                k = i << 1;
                i = i + (i >>> 1);
            }
            else
                i = k;
        }
    }

    static void warmup(int iters) throws Exception {
        print = false;
        System.out.println("Warmup...");
        oneTest(1, iters);
        oneTest(2, iters / 2);
    }

    static void oneTest(int nthreads, int iters) throws Exception {
        int fairIters = (nthreads <= 1)? iters : iters/20;
        int v = rng.next();

        if (print)
            System.out.print("NoLock (1 thread)     ");
        new NoLockLoop().test(v, 1, iters * nthreads);
        Thread.sleep(10);

        if (print)
            System.out.print("ReentrantLock         ");
        new ReentrantLockLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("FairReentrantLock     ");
        new FairReentrantLockLoop().test(v, nthreads, fairIters);
        Thread.sleep(10);

        if (doBuiltin) {
            if (print)
                System.out.print("builtin lock          ");
            new BuiltinLockLoop().test(v, nthreads, fairIters);
            Thread.sleep(10);
        }

        if (print)
            System.out.print("Mutex                 ");
        new MutexLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("LongMutex             ");
        new LongMutexLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("Semaphore             ");
        new SemaphoreLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("FairSemaphore         ");
        new FairSemaphoreLoop().test(v, nthreads, fairIters);
        Thread.sleep(10);

        if (print)
            System.out.print("ReentrantWriteLock    ");
        new ReentrantWriteLockLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("FairRWriteLock         ");
        new FairReentrantWriteLockLoop().test(v, nthreads, fairIters);
        Thread.sleep(10);

        if (print)
            System.out.print("ReentrantReadWriteLock");
        new ReentrantReadWriteLockLoop().test(v, nthreads, iters);
        Thread.sleep(10);

        if (print)
            System.out.print("FairRReadWriteLock     ");
        new FairReentrantReadWriteLockLoop().test(v, nthreads, fairIters);
        Thread.sleep(10);
    }

    static abstract class LockLoop implements Runnable {
        int value;
        int checkValue;
        int iters;
        volatile int result;
        volatile int failures;
        final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
        CyclicBarrier barrier;

        final int setValue(int v) {
            checkValue = v ^ 0x55555555;
            value = v;
            return v;
        }

        final int getValue() {
            int v = value;
            if (checkValue != ~(v ^ 0xAAAAAAAA))
                ++failures;
            return v;
        }

        final void test(int initialValue, int nthreads, int iters) throws Exception {
            setValue(initialValue);
            this.iters = iters;
            barrier = new CyclicBarrier(nthreads+1, timer);
            for (int i = 0; i < nthreads; ++i)
                pool.execute(this);
            barrier.await();
            barrier.await();
            long time = timer.getTime();
            if (print) {
                long tpi = time / (iters * nthreads);
                System.out.print("\t" + LoopHelpers.rightJustify(tpi) + " ns per update");
                System.out.println();
            }

            if (result == 0) // avoid overoptimization
                System.out.println("useless result: " + result);
            if (failures != 0)
                throw new Error("lock protection failure");
        }

        abstract int loop(int n);
        public final void run() {
            try {
                barrier.await();
                result += loop(iters);
                barrier.await();
            }
            catch (Exception ie) {
                return;
            }
        }

    }

    private static class NoLockLoop extends LockLoop {
        private volatile int readBarrier;
        final int loop(int n) {
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                int r1 = readBarrier;
                x = setValue(LoopHelpers.compute1(getValue()));
                int r2 = readBarrier;
                if (r1 == r2 && x == r1)
                    ++readBarrier;
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class BuiltinLockLoop extends LockLoop {
        final int loop(int n) {
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                synchronized(this) {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class ReentrantLockLoop extends LockLoop {
        final private ReentrantLock lock = new ReentrantLock();
        final int loop(int n) {
            final ReentrantLock lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class MutexLoop extends LockLoop {
        final private Mutex lock = new Mutex();
        final int loop(int n) {
            final Mutex lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class LongMutexLoop extends LockLoop {
        final private LongMutex lock = new LongMutex();
        final int loop(int n) {
            final LongMutex lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class FairReentrantLockLoop extends LockLoop {
        final private ReentrantLock lock = new ReentrantLock(true);
        final int loop(int n) {
            final ReentrantLock lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class ReentrantWriteLockLoop extends LockLoop {
        final private Lock lock = new ReentrantReadWriteLock().writeLock();
        final int loop(int n) {
            final Lock lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class FairReentrantWriteLockLoop extends LockLoop {
        final Lock lock = new ReentrantReadWriteLock(true).writeLock();
        final int loop(int n) {
            final Lock lock = this.lock;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                lock.lock();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    lock.unlock();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class SemaphoreLoop extends LockLoop {
        final private Semaphore sem = new Semaphore(1, false);
        final int loop(int n) {
            final Semaphore sem = this.sem;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                sem.acquireUninterruptibly();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    sem.release();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }
    private static class FairSemaphoreLoop extends LockLoop {
        final private Semaphore sem = new Semaphore(1, true);
        final int loop(int n) {
            final Semaphore sem = this.sem;
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                sem.acquireUninterruptibly();
                try {
                    x = setValue(LoopHelpers.compute1(getValue()));
                }
                finally {
                    sem.release();
                }
                sum += LoopHelpers.compute2(x);
            }
            return sum;
        }
    }

    private static class ReentrantReadWriteLockLoop extends LockLoop {
        final private ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
        final int loop(int n) {
            final Lock rlock = lock.readLock();
            final Lock wlock = lock.writeLock();
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                if ((n & 16) != 0) {
                    rlock.lock();
                    try {
                        x = LoopHelpers.compute1(getValue());
                        x = LoopHelpers.compute2(x);
                    }
                    finally {
                        rlock.unlock();
                    }
                }
                else {
                    wlock.lock();
                    try {
                        setValue(x);
                    }
                    finally {
                        wlock.unlock();
                    }
                    sum += LoopHelpers.compute2(x);
                }
            }
            return sum;
        }

    }


    private static class FairReentrantReadWriteLockLoop extends LockLoop {
        final private ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
        final int loop(int n) {
            final Lock rlock = lock.readLock();
            final Lock wlock = lock.writeLock();
            int sum = 0;
            int x = 0;
            while (n-- > 0) {
                if ((n & 16) != 0) {
                    rlock.lock();
                    try {
                        x = LoopHelpers.compute1(getValue());
                        x = LoopHelpers.compute2(x);
                    }
                    finally {
                        rlock.unlock();
                    }
                }
                else {
                    wlock.lock();
                    try {
                        setValue(x);
                    }
                    finally {
                        wlock.unlock();
                    }
                    sum += LoopHelpers.compute2(x);
                }
            }
            return sum;
        }

    }
}
Revision:	1.4
Committed:	Thu Oct 29 23:09:07 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.3:	+13 -13 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.1	/*
2	dl	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/licenses/publicdomain
5			*/
6			/*
7	dl	1.1	* @test
8			* @summary basic safety and liveness of ReentrantLocks, and other locks based on them
9			*/
10
11			import java.util.concurrent.*;
12			import java.util.concurrent.locks.*;
13			import java.util.*;
14
15			public final class CheckedLockLoops {
16			static final ExecutorService pool = Executors.newCachedThreadPool();
17			static final LoopHelpers.SimpleRandom rng = new LoopHelpers.SimpleRandom();
18			static boolean print = false;
19			static boolean doBuiltin = true;
20
21			public static void main(String[] args) throws Exception {
22			int maxThreads = 100;
23			int iters = 2000000;
24	jsr166	1.4	if (args.length > 0)
25	dl	1.1	maxThreads = Integer.parseInt(args[0]);
26			rng.setSeed(3122688L);
27			warmup(iters);
28			runTest(maxThreads, iters);
29			pool.shutdown();
30			}
31
32			static void runTest(int maxThreads, int iters) throws Exception {
33			print = true;
34			int k = 1;
35			for (int i = 1; i <= maxThreads;) {
36			System.out.println("Threads:" + i);
37			oneTest(i, iters / i);
38			if (i == k) {
39			k = i << 1;
40			i = i + (i >>> 1);
41	jsr166	1.4	}
42			else
43	dl	1.1	i = k;
44			}
45	jsr166	1.4	}
46	dl	1.1
47			static void warmup(int iters) throws Exception {
48			print = false;
49			System.out.println("Warmup...");
50			oneTest(1, iters);
51			oneTest(2, iters / 2);
52			}
53
54			static void oneTest(int nthreads, int iters) throws Exception {
55			int fairIters = (nthreads <= 1)? iters : iters/20;
56			int v = rng.next();
57
58			if (print)
59			System.out.print("NoLock (1 thread) ");
60			new NoLockLoop().test(v, 1, iters * nthreads);
61			Thread.sleep(10);
62	jsr166	1.4
63	dl	1.1	if (print)
64			System.out.print("ReentrantLock ");
65			new ReentrantLockLoop().test(v, nthreads, iters);
66			Thread.sleep(10);
67
68			if (print)
69			System.out.print("FairReentrantLock ");
70			new FairReentrantLockLoop().test(v, nthreads, fairIters);
71			Thread.sleep(10);
72
73			if (doBuiltin) {
74			if (print)
75			System.out.print("builtin lock ");
76			new BuiltinLockLoop().test(v, nthreads, fairIters);
77			Thread.sleep(10);
78			}
79
80			if (print)
81			System.out.print("Mutex ");
82			new MutexLoop().test(v, nthreads, iters);
83			Thread.sleep(10);
84
85			if (print)
86			System.out.print("LongMutex ");
87			new LongMutexLoop().test(v, nthreads, iters);
88			Thread.sleep(10);
89
90			if (print)
91			System.out.print("Semaphore ");
92			new SemaphoreLoop().test(v, nthreads, iters);
93			Thread.sleep(10);
94	jsr166	1.4
95	dl	1.1	if (print)
96			System.out.print("FairSemaphore ");
97			new FairSemaphoreLoop().test(v, nthreads, fairIters);
98			Thread.sleep(10);
99
100			if (print)
101			System.out.print("ReentrantWriteLock ");
102			new ReentrantWriteLockLoop().test(v, nthreads, iters);
103			Thread.sleep(10);
104
105			if (print)
106			System.out.print("FairRWriteLock ");
107			new FairReentrantWriteLockLoop().test(v, nthreads, fairIters);
108			Thread.sleep(10);
109	jsr166	1.4
110	dl	1.1	if (print)
111			System.out.print("ReentrantReadWriteLock");
112			new ReentrantReadWriteLockLoop().test(v, nthreads, iters);
113			Thread.sleep(10);
114	jsr166	1.4
115	dl	1.1	if (print)
116			System.out.print("FairRReadWriteLock ");
117			new FairReentrantReadWriteLockLoop().test(v, nthreads, fairIters);
118			Thread.sleep(10);
119			}
120
121			static abstract class LockLoop implements Runnable {
122			int value;
123			int checkValue;
124			int iters;
125			volatile int result;
126			volatile int failures;
127			final LoopHelpers.BarrierTimer timer = new LoopHelpers.BarrierTimer();
128			CyclicBarrier barrier;
129
130			final int setValue(int v) {
131			checkValue = v ^ 0x55555555;
132			value = v;
133			return v;
134			}
135
136			final int getValue() {
137			int v = value;
138	jsr166	1.4	if (checkValue != ~(v ^ 0xAAAAAAAA))
139	dl	1.1	++failures;
140			return v;
141			}
142
143			final void test(int initialValue, int nthreads, int iters) throws Exception {
144			setValue(initialValue);
145			this.iters = iters;
146			barrier = new CyclicBarrier(nthreads+1, timer);
147	jsr166	1.4	for (int i = 0; i < nthreads; ++i)
148	dl	1.1	pool.execute(this);
149			barrier.await();
150			barrier.await();
151			long time = timer.getTime();
152			if (print) {
153			long tpi = time / (iters * nthreads);
154			System.out.print("\t" + LoopHelpers.rightJustify(tpi) + " ns per update");
155			System.out.println();
156			}
157
158			if (result == 0) // avoid overoptimization
159			System.out.println("useless result: " + result);
160			if (failures != 0)
161			throw new Error("lock protection failure");
162			}
163
164			abstract int loop(int n);
165			public final void run() {
166			try {
167	jsr166	1.4	barrier.await();
168	dl	1.1	result += loop(iters);
169			barrier.await();
170			}
171	jsr166	1.4	catch (Exception ie) {
172			return;
173	dl	1.1	}
174			}
175
176			}
177
178			private static class NoLockLoop extends LockLoop {
179			private volatile int readBarrier;
180			final int loop(int n) {
181			int sum = 0;
182	jsr166	1.3	int x = 0;
183	dl	1.1	while (n-- > 0) {
184			int r1 = readBarrier;
185			x = setValue(LoopHelpers.compute1(getValue()));
186			int r2 = readBarrier;
187			if (r1 == r2 && x == r1)
188			++readBarrier;
189			sum += LoopHelpers.compute2(x);
190			}
191			return sum;
192			}
193			}
194
195			private static class BuiltinLockLoop extends LockLoop {
196			final int loop(int n) {
197			int sum = 0;
198	jsr166	1.3	int x = 0;
199	dl	1.1	while (n-- > 0) {
200			synchronized(this) {
201			x = setValue(LoopHelpers.compute1(getValue()));
202			}
203			sum += LoopHelpers.compute2(x);
204			}
205			return sum;
206			}
207			}
208
209			private static class ReentrantLockLoop extends LockLoop {
210			final private ReentrantLock lock = new ReentrantLock();
211			final int loop(int n) {
212			final ReentrantLock lock = this.lock;
213			int sum = 0;
214			int x = 0;
215			while (n-- > 0) {
216			lock.lock();
217			try {
218			x = setValue(LoopHelpers.compute1(getValue()));
219			}
220			finally {
221			lock.unlock();
222			}
223			sum += LoopHelpers.compute2(x);
224			}
225			return sum;
226			}
227			}
228
229			private static class MutexLoop extends LockLoop {
230			final private Mutex lock = new Mutex();
231			final int loop(int n) {
232			final Mutex lock = this.lock;
233			int sum = 0;
234			int x = 0;
235			while (n-- > 0) {
236			lock.lock();
237			try {
238			x = setValue(LoopHelpers.compute1(getValue()));
239			}
240			finally {
241			lock.unlock();
242			}
243			sum += LoopHelpers.compute2(x);
244			}
245			return sum;
246			}
247			}
248
249			private static class LongMutexLoop extends LockLoop {
250			final private LongMutex lock = new LongMutex();
251			final int loop(int n) {
252			final LongMutex lock = this.lock;
253			int sum = 0;
254			int x = 0;
255			while (n-- > 0) {
256			lock.lock();
257			try {
258			x = setValue(LoopHelpers.compute1(getValue()));
259			}
260			finally {
261			lock.unlock();
262			}
263			sum += LoopHelpers.compute2(x);
264			}
265			return sum;
266			}
267			}
268
269			private static class FairReentrantLockLoop extends LockLoop {
270			final private ReentrantLock lock = new ReentrantLock(true);
271			final int loop(int n) {
272			final ReentrantLock lock = this.lock;
273			int sum = 0;
274			int x = 0;
275			while (n-- > 0) {
276			lock.lock();
277			try {
278			x = setValue(LoopHelpers.compute1(getValue()));
279			}
280			finally {
281			lock.unlock();
282			}
283			sum += LoopHelpers.compute2(x);
284			}
285			return sum;
286			}
287			}
288
289			private static class ReentrantWriteLockLoop extends LockLoop {
290			final private Lock lock = new ReentrantReadWriteLock().writeLock();
291			final int loop(int n) {
292			final Lock lock = this.lock;
293			int sum = 0;
294			int x = 0;
295			while (n-- > 0) {
296			lock.lock();
297			try {
298			x = setValue(LoopHelpers.compute1(getValue()));
299			}
300			finally {
301			lock.unlock();
302			}
303			sum += LoopHelpers.compute2(x);
304			}
305			return sum;
306			}
307			}
308
309			private static class FairReentrantWriteLockLoop extends LockLoop {
310			final Lock lock = new ReentrantReadWriteLock(true).writeLock();
311			final int loop(int n) {
312			final Lock lock = this.lock;
313			int sum = 0;
314			int x = 0;
315			while (n-- > 0) {
316			lock.lock();
317			try {
318			x = setValue(LoopHelpers.compute1(getValue()));
319			}
320			finally {
321			lock.unlock();
322			}
323			sum += LoopHelpers.compute2(x);
324			}
325			return sum;
326			}
327			}
328
329			private static class SemaphoreLoop extends LockLoop {
330			final private Semaphore sem = new Semaphore(1, false);
331			final int loop(int n) {
332			final Semaphore sem = this.sem;
333			int sum = 0;
334			int x = 0;
335			while (n-- > 0) {
336			sem.acquireUninterruptibly();
337			try {
338			x = setValue(LoopHelpers.compute1(getValue()));
339			}
340			finally {
341			sem.release();
342			}
343			sum += LoopHelpers.compute2(x);
344			}
345			return sum;
346			}
347			}
348			private static class FairSemaphoreLoop extends LockLoop {
349			final private Semaphore sem = new Semaphore(1, true);
350			final int loop(int n) {
351			final Semaphore sem = this.sem;
352			int sum = 0;
353			int x = 0;
354			while (n-- > 0) {
355			sem.acquireUninterruptibly();
356			try {
357			x = setValue(LoopHelpers.compute1(getValue()));
358			}
359			finally {
360			sem.release();
361			}
362			sum += LoopHelpers.compute2(x);
363			}
364			return sum;
365			}
366			}
367
368			private static class ReentrantReadWriteLockLoop extends LockLoop {
369			final private ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
370			final int loop(int n) {
371			final Lock rlock = lock.readLock();
372			final Lock wlock = lock.writeLock();
373			int sum = 0;
374			int x = 0;
375			while (n-- > 0) {
376			if ((n & 16) != 0) {
377			rlock.lock();
378			try {
379			x = LoopHelpers.compute1(getValue());
380			x = LoopHelpers.compute2(x);
381			}
382			finally {
383			rlock.unlock();
384			}
385			}
386			else {
387			wlock.lock();
388			try {
389			setValue(x);
390			}
391			finally {
392			wlock.unlock();
393			}
394			sum += LoopHelpers.compute2(x);
395			}
396			}
397			return sum;
398			}
399
400			}
401
402
403			private static class FairReentrantReadWriteLockLoop extends LockLoop {
404			final private ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
405			final int loop(int n) {
406			final Lock rlock = lock.readLock();
407			final Lock wlock = lock.writeLock();
408			int sum = 0;
409			int x = 0;
410			while (n-- > 0) {
411			if ((n & 16) != 0) {
412			rlock.lock();
413			try {
414			x = LoopHelpers.compute1(getValue());
415			x = LoopHelpers.compute2(x);
416			}
417			finally {
418			rlock.unlock();
419			}
420			}
421			else {
422			wlock.lock();
423			try {
424			setValue(x);
425			}
426			finally {
427			wlock.unlock();
428			}
429			sum += LoopHelpers.compute2(x);
430			}
431			}
432			return sum;
433			}
434
435			}
436			}