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

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

public final class UncheckedLockLoops {
    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 = 10000000;

        if (args.length > 0)
            maxThreads = Integer.parseInt(args[0]);

        rng.setSeed(3122688L);

        print = false;
        System.out.println("Warmup...");
        oneTest(1, 100000);
        Thread.sleep(1000);
        oneTest(3, 10000);
        Thread.sleep(1000);
        oneTest(2, 10000);
        Thread.sleep(100);
        oneTest(1, 100000);
        Thread.sleep(100);
        oneTest(1, 100000);
        Thread.sleep(1000);
        print = true;

        System.out.println("Threads:" + 1);
        oneTest(1, iters / 1);
        Thread.sleep(100);

        for (int i = 1; i <= maxThreads; i += (i+1) >>> 1) {
            System.out.println("Threads:" + i);
            oneTest(i, iters / i);
            Thread.sleep(100);
        }
    }

    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 (false) {
        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);
    }

    abstract static 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)
                new Thread(this).start();
            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");
                //                double secs = (double) time / 1000000000.0;
                //                System.out.print("\t " + secs + "s run time");
                System.out.println();
            }

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