test/loops/IntegerMax.java

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

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

public class IntegerMax {
    static final int SIZE = 1000000;
    static final AtomicInteger checksum = new AtomicInteger();
    static boolean print;
    static boolean allClasses = false; // true if also test dumb/default classes
    static final BinaryOperator<Integer> MAX =
        (Integer x, Integer y) -> x >= y ? x : y;

    public static void main(String[] args) throws Exception {
        if (args.length > 0)
            allClasses = true;
        print = false;
        System.out.println("warmup...");
        allTests(10000, 100);
        System.out.println("...");
        print = true;
        int step = 10;
        //        int step = 100;
        for (int reps = 0; reps < 2; ++reps) {
            int trials = SIZE;
            for (int size = 1; size <= SIZE; size *= step) {
                allTests(size, trials);
                trials /= (step / 2);
            }
        }
    }

    static String sep() { return print ? "\n" : " "; }

    static void allTests(int size, int trials) throws Exception {
        System.out.println("---------------------------------------------");
        System.out.println("size: " + size + " trials: " + trials);
        Integer[] keys = new Integer[size];
        for (int i = 0; i < size; ++i)
            keys[i] = Integer.valueOf(i);
        Integer[] vals = Arrays.copyOf(keys, size);
        shuffle(keys);
        shuffle(vals);
        List<Integer> klist = Arrays.asList(keys);
        List<Integer> vlist = Arrays.asList(vals);
        int kmax = size - 1;
        int vmax = size - 1;

        isptest(klist, kmax, size, trials);
        System.out.print("Arrays.asList.keys" + sep());
        isptest(vlist, vmax, size, trials);
        System.out.print("Arrays.asList.values" + sep());

        ctest(new ArrayList<Integer>(), klist, kmax, size, trials);
        ctest(new ArrayList<Integer>(), vlist, vmax, size, trials);
        ctest(new Vector<Integer>(), klist, kmax, size, trials);
        ctest(new Vector<Integer>(), vlist, vmax, size, trials);
        ctest(new ArrayDeque<Integer>(), klist, kmax, size, trials);
        ctest(new ArrayDeque<Integer>(), vlist, vmax, size, trials);
        ctest(new CopyOnWriteArrayList<Integer>(), klist, kmax, size, trials);
        ctest(new CopyOnWriteArrayList<Integer>(), vlist, vmax, size, trials);
        ctest(new PriorityQueue<Integer>(), klist, kmax, size, trials);
        ctest(new PriorityQueue<Integer>(), vlist, vmax, size, trials);

        ctest(new HashSet<Integer>(), klist, kmax, size, trials);
        ctest(new HashSet<Integer>(), vlist, vmax, size, trials);
        ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, kmax, size, trials);
        ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vmax, size, trials);
        ctest(new TreeSet<Integer>(), klist, kmax, size, trials);
        ctest(new TreeSet<Integer>(), vlist, vmax, size, trials);
        ctest(new ConcurrentSkipListSet<Integer>(), klist, kmax, size, trials);
        ctest(new ConcurrentSkipListSet<Integer>(), vlist, vmax, size, trials);
        
        mtest(new HashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
        mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
        mtest(new WeakHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
        mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
        
        mtest(new TreeMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
        mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
    
        if (allClasses) {
            mtest(new Hashtable<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
            mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
            ctest(new LinkedHashSet<Integer>(), klist, kmax, size, trials);
            ctest(new LinkedHashSet<Integer>(), vlist, vmax, size, trials);
            ctest(new LinkedList<Integer>(), klist, kmax, size, trials);
            ctest(new LinkedList<Integer>(), vlist, vmax, size, trials);
            //            catest(new LinkedList<Integer>(), klist, kmax, size, trials);
            //            catest(new LinkedList<Integer>(), vlist, vmax, size, trials);
            ctest(new ConcurrentLinkedQueue<Integer>(), klist, kmax, size, trials);
            ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vmax, size, trials);
            ctest(new ConcurrentLinkedDeque<Integer>(), klist, kmax, size, trials);
            ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vmax, size, trials);
            ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
            ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
            ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, kmax, size, trials);
            ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vmax, size, trials);
            ctest(new LinkedTransferQueue<Integer>(), klist, kmax, size, trials);
            ctest(new LinkedTransferQueue<Integer>(), vlist, vmax, size, trials);
            ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
            ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
            ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
            ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
        }

        if (checksum.get() != 0) throw new Error("bad computation");
    }

    static void ctest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials)
        throws Exception {
        String cn = c.getClass().getName();
        if (cn.startsWith("java.util.concurrent."))
            cn = cn.substring(21);
        else if (cn.startsWith("java.util."))
            cn = cn.substring(10);
        c.addAll(klist);
        isptest(c, kmax, size, trials);
        System.out.print(cn + sep());
    }

    static void catest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials)
        throws Exception {
        String cn = c.getClass().getName();
        if (cn.startsWith("java.util.concurrent."))
            cn = cn.substring(21);
        else if (cn.startsWith("java.util."))
            cn = cn.substring(10);
        cn = cn + ".toArrayList";
        c.addAll(klist);
        ArrayList<Integer> ac = new ArrayList<Integer>(c);
        isptest(ac, kmax, size, trials);
        System.out.print(cn + sep());
    }

    static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int kmax, int vmax, int size, int trials) throws Exception {
        String cn = m.getClass().getName();
        if (cn.startsWith("java.util.concurrent."))
            cn = cn.substring(21);
        else if (cn.startsWith("java.util."))
            cn = cn.substring(10);
        for (int i = 0; i < size; ++i)
            m.put(keys[i], vals[i]);
        isptest(m.keySet(), kmax, size, trials);
        System.out.print(cn + ".keys" + sep());
        isptest(m.values(), vmax, size, trials);
        System.out.print(cn + ".vals" + sep());
    }

    static void isptest(Collection<Integer> c, int max, int size, int trials) throws Exception {
        long ti = itest(c, max, trials);
        long ts = stest(c, max, trials);
        long tp = ptest(c, max, trials);
        if (checksum.get() != 0) throw new Error("bad computation");
        if (print) {
            long scale = (long)size * trials;
            double di = ((double)ti) / scale;
            double ds = ((double)ts) / scale;
            double dp = ((double)tp) / scale;
            System.out.printf("n:%7d ", size);
            System.out.printf("i:%8.2f ", di);
            System.out.printf("s:%8.2f ", ds);
            System.out.printf("p:%8.2f   ", dp);
        }
    }

    static long itest(Collection<Integer> c, int max, int trials) throws Exception {
        if (c == null) throw new Error();
        Thread.sleep(250);
        long tlast =  System.nanoTime();
        for (int i = 0; i < trials; ++i) {
            Integer pmax = Integer.valueOf(Integer.MIN_VALUE - checksum.get());
            for (Integer x : c)
                pmax = MAX.apply(pmax, x);
            checksum.getAndAdd(max - pmax);
        }
        return System.nanoTime() - tlast;
    }

    static long stest(Collection<Integer> c, int max, int trials) throws Exception {
        if (c == null) throw new Error();
        Thread.sleep(250);
        long tlast =  System.nanoTime();
        for (int i = 0; i < trials; ++i) {
            int pmax = c.stream().reduce
                (Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX);
            checksum.getAndAdd(max - pmax);
        }
        return System.nanoTime() - tlast;
    }

    static long ptest(Collection<Integer> c, int max, int trials) throws Exception {
        if (c == null) throw new Error();
        Thread.sleep(250);
        long tlast =  System.nanoTime();
        for (int i = 0; i < trials; ++i) {
            int pmax = c.parallelStream().reduce
                (Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX);
            checksum.getAndAdd(max - pmax);
        }
        return System.nanoTime() - tlast;
    }

    // misc

    static final long NPS = (1000L * 1000 * 1000);
    static double elapsedTime(long startTime) {
        return (double)(System.nanoTime() - startTime) / NPS;
    }

    static void shuffle(Object[] a) {
        ThreadLocalRandom rng = ThreadLocalRandom.current();
        for (int i = a.length; i > 1; i--) {
            Object t = a[i-1];
            int r = rng.nextInt(i);
            a[i-1] = a[r];
            a[r] = t;
        }
    }

}
Revision:	1.3
Committed:	Fri Mar 22 18:41:30 2013 UTC (11 years, 1 month ago) by dl
Branch:	MAIN
Changes since 1.2:	+24 -7 lines
Log Message:	Adjust to CSLM changes
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/publicdomain/zero/1.0/
5			*/
6
7			import java.util.*;
8			import java.util.function.*;
9			import java.util.concurrent.*;
10			import java.util.concurrent.atomic.*;
11
12			public class IntegerMax {
13			static final int SIZE = 1000000;
14			static final AtomicInteger checksum = new AtomicInteger();
15			static boolean print;
16			static boolean allClasses = false; // true if also test dumb/default classes
17	jsr166	1.2	static final BinaryOperator<Integer> MAX =
18	dl	1.1	(Integer x, Integer y) -> x >= y ? x : y;
19
20			public static void main(String[] args) throws Exception {
21			if (args.length > 0)
22			allClasses = true;
23			print = false;
24			System.out.println("warmup...");
25			allTests(10000, 100);
26			System.out.println("...");
27			print = true;
28			int step = 10;
29			// int step = 100;
30			for (int reps = 0; reps < 2; ++reps) {
31			int trials = SIZE;
32			for (int size = 1; size <= SIZE; size *= step) {
33			allTests(size, trials);
34			trials /= (step / 2);
35			}
36			}
37			}
38
39	jsr166	1.2	static String sep() { return print ? "\n" : " "; }
40	dl	1.1
41			static void allTests(int size, int trials) throws Exception {
42			System.out.println("---------------------------------------------");
43			System.out.println("size: " + size + " trials: " + trials);
44			Integer[] keys = new Integer[size];
45			for (int i = 0; i < size; ++i)
46			keys[i] = Integer.valueOf(i);
47			Integer[] vals = Arrays.copyOf(keys, size);
48			shuffle(keys);
49			shuffle(vals);
50			List<Integer> klist = Arrays.asList(keys);
51			List<Integer> vlist = Arrays.asList(vals);
52			int kmax = size - 1;
53			int vmax = size - 1;
54
55			isptest(klist, kmax, size, trials);
56			System.out.print("Arrays.asList.keys" + sep());
57			isptest(vlist, vmax, size, trials);
58			System.out.print("Arrays.asList.values" + sep());
59
60			ctest(new ArrayList<Integer>(), klist, kmax, size, trials);
61			ctest(new ArrayList<Integer>(), vlist, vmax, size, trials);
62			ctest(new Vector<Integer>(), klist, kmax, size, trials);
63			ctest(new Vector<Integer>(), vlist, vmax, size, trials);
64			ctest(new ArrayDeque<Integer>(), klist, kmax, size, trials);
65			ctest(new ArrayDeque<Integer>(), vlist, vmax, size, trials);
66			ctest(new CopyOnWriteArrayList<Integer>(), klist, kmax, size, trials);
67			ctest(new CopyOnWriteArrayList<Integer>(), vlist, vmax, size, trials);
68			ctest(new PriorityQueue<Integer>(), klist, kmax, size, trials);
69			ctest(new PriorityQueue<Integer>(), vlist, vmax, size, trials);
70	dl	1.3
71	dl	1.1	ctest(new HashSet<Integer>(), klist, kmax, size, trials);
72			ctest(new HashSet<Integer>(), vlist, vmax, size, trials);
73			ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, kmax, size, trials);
74			ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vmax, size, trials);
75			ctest(new TreeSet<Integer>(), klist, kmax, size, trials);
76			ctest(new TreeSet<Integer>(), vlist, vmax, size, trials);
77	dl	1.3	ctest(new ConcurrentSkipListSet<Integer>(), klist, kmax, size, trials);
78			ctest(new ConcurrentSkipListSet<Integer>(), vlist, vmax, size, trials);
79
80	dl	1.1	mtest(new HashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
81			mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
82			mtest(new WeakHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
83			mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
84	dl	1.3
85	dl	1.1	mtest(new TreeMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
86			mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
87	dl	1.3
88	dl	1.1	if (allClasses) {
89			mtest(new Hashtable<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
90			mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, kmax, vmax, size, trials);
91			ctest(new LinkedHashSet<Integer>(), klist, kmax, size, trials);
92			ctest(new LinkedHashSet<Integer>(), vlist, vmax, size, trials);
93			ctest(new LinkedList<Integer>(), klist, kmax, size, trials);
94			ctest(new LinkedList<Integer>(), vlist, vmax, size, trials);
95	dl	1.3	// catest(new LinkedList<Integer>(), klist, kmax, size, trials);
96			// catest(new LinkedList<Integer>(), vlist, vmax, size, trials);
97	dl	1.1	ctest(new ConcurrentLinkedQueue<Integer>(), klist, kmax, size, trials);
98			ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vmax, size, trials);
99			ctest(new ConcurrentLinkedDeque<Integer>(), klist, kmax, size, trials);
100			ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vmax, size, trials);
101			ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
102			ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
103			ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, kmax, size, trials);
104			ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vmax, size, trials);
105			ctest(new LinkedTransferQueue<Integer>(), klist, kmax, size, trials);
106			ctest(new LinkedTransferQueue<Integer>(), vlist, vmax, size, trials);
107			ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
108			ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
109			ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, kmax, size, trials);
110			ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vmax, size, trials);
111			}
112
113	dl	1.3	if (checksum.get() != 0) throw new Error("bad computation");
114	dl	1.1	}
115
116	jsr166	1.2	static void ctest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials)
117	dl	1.1	throws Exception {
118			String cn = c.getClass().getName();
119			if (cn.startsWith("java.util.concurrent."))
120			cn = cn.substring(21);
121			else if (cn.startsWith("java.util."))
122			cn = cn.substring(10);
123			c.addAll(klist);
124			isptest(c, kmax, size, trials);
125			System.out.print(cn + sep());
126			}
127
128	dl	1.3	static void catest(Collection<Integer> c, List<Integer> klist, int kmax, int size, int trials)
129			throws Exception {
130			String cn = c.getClass().getName();
131			if (cn.startsWith("java.util.concurrent."))
132			cn = cn.substring(21);
133			else if (cn.startsWith("java.util."))
134			cn = cn.substring(10);
135			cn = cn + ".toArrayList";
136			c.addAll(klist);
137			ArrayList<Integer> ac = new ArrayList<Integer>(c);
138			isptest(ac, kmax, size, trials);
139			System.out.print(cn + sep());
140			}
141
142	dl	1.1	static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int kmax, int vmax, int size, int trials) throws Exception {
143			String cn = m.getClass().getName();
144			if (cn.startsWith("java.util.concurrent."))
145			cn = cn.substring(21);
146			else if (cn.startsWith("java.util."))
147			cn = cn.substring(10);
148			for (int i = 0; i < size; ++i)
149			m.put(keys[i], vals[i]);
150			isptest(m.keySet(), kmax, size, trials);
151			System.out.print(cn + ".keys" + sep());
152			isptest(m.values(), vmax, size, trials);
153			System.out.print(cn + ".vals" + sep());
154			}
155
156			static void isptest(Collection<Integer> c, int max, int size, int trials) throws Exception {
157			long ti = itest(c, max, trials);
158			long ts = stest(c, max, trials);
159			long tp = ptest(c, max, trials);
160	dl	1.3	if (checksum.get() != 0) throw new Error("bad computation");
161	dl	1.1	if (print) {
162			long scale = (long)size * trials;
163			double di = ((double)ti) / scale;
164			double ds = ((double)ts) / scale;
165			double dp = ((double)tp) / scale;
166			System.out.printf("n:%7d ", size);
167			System.out.printf("i:%8.2f ", di);
168			System.out.printf("s:%8.2f ", ds);
169			System.out.printf("p:%8.2f ", dp);
170			}
171			}
172
173			static long itest(Collection<Integer> c, int max, int trials) throws Exception {
174			if (c == null) throw new Error();
175			Thread.sleep(250);
176			long tlast = System.nanoTime();
177			for (int i = 0; i < trials; ++i) {
178			Integer pmax = Integer.valueOf(Integer.MIN_VALUE - checksum.get());
179	jsr166	1.2	for (Integer x : c)
180	dl	1.1	pmax = MAX.apply(pmax, x);
181			checksum.getAndAdd(max - pmax);
182			}
183			return System.nanoTime() - tlast;
184			}
185
186			static long stest(Collection<Integer> c, int max, int trials) throws Exception {
187			if (c == null) throw new Error();
188			Thread.sleep(250);
189			long tlast = System.nanoTime();
190			for (int i = 0; i < trials; ++i) {
191			int pmax = c.stream().reduce
192			(Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX);
193			checksum.getAndAdd(max - pmax);
194			}
195			return System.nanoTime() - tlast;
196			}
197
198			static long ptest(Collection<Integer> c, int max, int trials) throws Exception {
199			if (c == null) throw new Error();
200			Thread.sleep(250);
201			long tlast = System.nanoTime();
202			for (int i = 0; i < trials; ++i) {
203			int pmax = c.parallelStream().reduce
204			(Integer.valueOf(Integer.MIN_VALUE - checksum.get()), MAX);
205			checksum.getAndAdd(max - pmax);
206			}
207			return System.nanoTime() - tlast;
208			}
209
210			// misc
211
212			static final long NPS = (1000L * 1000 * 1000);
213			static double elapsedTime(long startTime) {
214			return (double)(System.nanoTime() - startTime) / NPS;
215			}
216
217			static void shuffle(Object[] a) {
218			ThreadLocalRandom rng = ThreadLocalRandom.current();
219			for (int i = a.length; i > 1; i--) {
220			Object t = a[i-1];
221			int r = rng.nextInt(i);
222			a[i-1] = a[r];
223			a[r] = t;
224			}
225			}
226
227			}