test/loops/IntegerSum.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.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.function.*;

public class IntegerSum {
    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> SUM = (Integer x, Integer 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];
        int ksum = 0;
        for (int i = 0; i < size; ++i) {
            ksum += i;
            keys[i] = Integer.valueOf(i);
        }
        int vsum = ksum;
        Integer[] vals = Arrays.copyOf(keys, size);
        shuffle(vals);
        List<Integer> klist = Arrays.asList(keys);
        List<Integer> vlist = Arrays.asList(vals);

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

        ctest(new ArrayList<Integer>(), klist, ksum, size, trials);
        ctest(new ArrayList<Integer>(), vlist, vsum, size, trials);
        ctest(new Vector<Integer>(), klist, ksum, size, trials);
        ctest(new Vector<Integer>(), vlist, vsum, size, trials);
        ctest(new ArrayDeque<Integer>(), klist, ksum, size, trials);
        ctest(new ArrayDeque<Integer>(), vlist, vsum, size, trials);
        ctest(new CopyOnWriteArrayList<Integer>(), klist, ksum, size, trials);
        ctest(new CopyOnWriteArrayList<Integer>(), vlist, vsum, size, trials);
        ctest(new PriorityQueue<Integer>(), klist, ksum, size, trials);
        ctest(new PriorityQueue<Integer>(), vlist, vsum, size, trials);
        ctest(new HashSet<Integer>(), klist, ksum, size, trials);
        ctest(new HashSet<Integer>(), vlist, vsum, size, trials);
        ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, ksum, size, trials);
        ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vsum, size, trials);
        ctest(new TreeSet<Integer>(), klist, ksum, size, trials);
        ctest(new TreeSet<Integer>(), vlist, vsum, size, trials);
        ctest(new ConcurrentSkipListSet<Integer>(), klist, ksum, size, trials);
        ctest(new ConcurrentSkipListSet<Integer>(), vlist, vsum, size, trials);

        mtest(new HashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
        mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
        mtest(new WeakHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
        mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);

        mtest(new TreeMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
        mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);

        if (allClasses) {
            mtest(new Hashtable<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
            mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
            ctest(new LinkedHashSet<Integer>(), klist, ksum, size, trials);
            ctest(new LinkedHashSet<Integer>(), vlist, vsum, size, trials);
            ctest(new LinkedList<Integer>(), klist, ksum, size, trials);
            ctest(new LinkedList<Integer>(), vlist, vsum, size, trials);
            ctest(new ConcurrentLinkedQueue<Integer>(), klist, ksum, size, trials);
            ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vsum, size, trials);
            ctest(new ConcurrentLinkedDeque<Integer>(), klist, ksum, size, trials);
            ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vsum, size, trials);
            ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
            ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
            ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, ksum, size, trials);
            ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vsum, size, trials);
            ctest(new LinkedTransferQueue<Integer>(), klist, ksum, size, trials);
            ctest(new LinkedTransferQueue<Integer>(), vlist, vsum, size, trials);
            ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
            ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
            ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
            ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
        }

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

    static void ctest(Collection<Integer> c, List<Integer> klist, int ksum, 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, ksum, size, trials);
        System.out.print(cn + sep());
    }

    static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int ksum, int vsum, 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(), ksum, size, trials);
        System.out.print(cn + ".keys" + sep());
        isptest(m.values(), vsum, size, trials);
        System.out.print(cn + ".vals" + sep());
    }

    static void isptest(Collection<Integer> c, int sum, int size, int trials) throws Exception {
        long ti = itest(c, sum, trials);
        long ts = stest(c, sum, trials);
        long tp = ptest(c, sum, 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 sum, 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 psum = Integer.valueOf(checksum.get());
            for (Integer x : c)
                psum = SUM.apply(psum, x);
            checksum.getAndAdd(sum - psum);
        }
        return System.nanoTime() - tlast;
    }

    static long stest(Collection<Integer> c, int sum, 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 psum = c.stream().reduce
                (Integer.valueOf(checksum.get()), SUM);
            checksum.getAndAdd(sum - psum);
        }
        return System.nanoTime() - tlast;
    }

    static long ptest(Collection<Integer> c, int sum, 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 psum = c.parallelStream().reduce
                (Integer.valueOf(checksum.get()), SUM);
            checksum.getAndAdd(sum - psum);
        }
        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.5
Committed:	Wed Dec 31 17:00:58 2014 UTC (9 years, 4 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.4:	+1 -1 lines
Log Message:	lexicographic import order
#	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.concurrent.*;
9			import java.util.concurrent.atomic.*;
10	jsr166	1.5	import java.util.function.*;
11	dl	1.1
12			public class IntegerSum {
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
18			static final BinaryOperator<Integer> SUM = (Integer x, Integer 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			int ksum = 0;
46			for (int i = 0; i < size; ++i) {
47			ksum += i;
48			keys[i] = Integer.valueOf(i);
49			}
50			int vsum = ksum;
51			Integer[] vals = Arrays.copyOf(keys, size);
52			shuffle(vals);
53			List<Integer> klist = Arrays.asList(keys);
54			List<Integer> vlist = Arrays.asList(vals);
55
56			isptest(klist, ksum, size, trials);
57			System.out.print("Arrays.asList.keys" + sep());
58			isptest(vlist, vsum, size, trials);
59			System.out.print("Arrays.asList.values" + sep());
60
61			ctest(new ArrayList<Integer>(), klist, ksum, size, trials);
62			ctest(new ArrayList<Integer>(), vlist, vsum, size, trials);
63			ctest(new Vector<Integer>(), klist, ksum, size, trials);
64			ctest(new Vector<Integer>(), vlist, vsum, size, trials);
65			ctest(new ArrayDeque<Integer>(), klist, ksum, size, trials);
66			ctest(new ArrayDeque<Integer>(), vlist, vsum, size, trials);
67			ctest(new CopyOnWriteArrayList<Integer>(), klist, ksum, size, trials);
68			ctest(new CopyOnWriteArrayList<Integer>(), vlist, vsum, size, trials);
69			ctest(new PriorityQueue<Integer>(), klist, ksum, size, trials);
70			ctest(new PriorityQueue<Integer>(), vlist, vsum, size, trials);
71			ctest(new HashSet<Integer>(), klist, ksum, size, trials);
72			ctest(new HashSet<Integer>(), vlist, vsum, size, trials);
73			ctest(ConcurrentHashMap.<Integer>newKeySet(), klist, ksum, size, trials);
74			ctest(ConcurrentHashMap.<Integer>newKeySet(), vlist, vsum, size, trials);
75			ctest(new TreeSet<Integer>(), klist, ksum, size, trials);
76			ctest(new TreeSet<Integer>(), vlist, vsum, size, trials);
77	dl	1.3	ctest(new ConcurrentSkipListSet<Integer>(), klist, ksum, size, trials);
78			ctest(new ConcurrentSkipListSet<Integer>(), vlist, vsum, size, trials);
79	dl	1.1
80			mtest(new HashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
81			mtest(new IdentityHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
82			mtest(new WeakHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
83			mtest(new ConcurrentHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
84
85			mtest(new TreeMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
86			mtest(new ConcurrentSkipListMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
87
88			if (allClasses) {
89			mtest(new Hashtable<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
90			mtest(new LinkedHashMap<Integer,Integer>(), keys, vals, ksum, vsum, size, trials);
91			ctest(new LinkedHashSet<Integer>(), klist, ksum, size, trials);
92			ctest(new LinkedHashSet<Integer>(), vlist, vsum, size, trials);
93			ctest(new LinkedList<Integer>(), klist, ksum, size, trials);
94			ctest(new LinkedList<Integer>(), vlist, vsum, size, trials);
95			ctest(new ConcurrentLinkedQueue<Integer>(), klist, ksum, size, trials);
96			ctest(new ConcurrentLinkedQueue<Integer>(), vlist, vsum, size, trials);
97			ctest(new ConcurrentLinkedDeque<Integer>(), klist, ksum, size, trials);
98			ctest(new ConcurrentLinkedDeque<Integer>(), vlist, vsum, size, trials);
99			ctest(new LinkedBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
100			ctest(new LinkedBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
101			ctest(new LinkedBlockingDeque<Integer>(SIZE), klist, ksum, size, trials);
102			ctest(new LinkedBlockingDeque<Integer>(SIZE), vlist, vsum, size, trials);
103			ctest(new LinkedTransferQueue<Integer>(), klist, ksum, size, trials);
104			ctest(new LinkedTransferQueue<Integer>(), vlist, vsum, size, trials);
105			ctest(new ArrayBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
106			ctest(new ArrayBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
107			ctest(new PriorityBlockingQueue<Integer>(SIZE), klist, ksum, size, trials);
108			ctest(new PriorityBlockingQueue<Integer>(SIZE), vlist, vsum, size, trials);
109			}
110
111	dl	1.3	if (checksum.get() != 0) throw new Error("bad computation");
112	dl	1.1	}
113
114	jsr166	1.2	static void ctest(Collection<Integer> c, List<Integer> klist, int ksum, int size, int trials)
115	dl	1.1	throws Exception {
116			String cn = c.getClass().getName();
117			if (cn.startsWith("java.util.concurrent."))
118			cn = cn.substring(21);
119			else if (cn.startsWith("java.util."))
120			cn = cn.substring(10);
121			c.addAll(klist);
122			isptest(c, ksum, size, trials);
123			System.out.print(cn + sep());
124			}
125
126			static void mtest(Map<Integer,Integer> m, Integer[] keys, Integer[] vals, int ksum, int vsum, int size, int trials) throws Exception {
127			String cn = m.getClass().getName();
128			if (cn.startsWith("java.util.concurrent."))
129			cn = cn.substring(21);
130			else if (cn.startsWith("java.util."))
131			cn = cn.substring(10);
132			for (int i = 0; i < size; ++i)
133			m.put(keys[i], vals[i]);
134			isptest(m.keySet(), ksum, size, trials);
135			System.out.print(cn + ".keys" + sep());
136			isptest(m.values(), vsum, size, trials);
137			System.out.print(cn + ".vals" + sep());
138			}
139
140			static void isptest(Collection<Integer> c, int sum, int size, int trials) throws Exception {
141			long ti = itest(c, sum, trials);
142			long ts = stest(c, sum, trials);
143			long tp = ptest(c, sum, trials);
144	dl	1.3	if (checksum.get() != 0) throw new Error("bad computation");
145	dl	1.1	if (print) {
146			long scale = (long)size * trials;
147			double di = ((double)ti) / scale;
148			double ds = ((double)ts) / scale;
149			double dp = ((double)tp) / scale;
150			System.out.printf("n:%7d ", size);
151			System.out.printf("i:%8.2f ", di);
152			System.out.printf("s:%8.2f ", ds);
153			System.out.printf("p:%8.2f ", dp);
154			}
155			}
156
157			static long itest(Collection<Integer> c, int sum, int trials) throws Exception {
158			if (c == null) throw new Error();
159			Thread.sleep(250);
160	jsr166	1.4	long tlast = System.nanoTime();
161	dl	1.1	for (int i = 0; i < trials; ++i) {
162			Integer psum = Integer.valueOf(checksum.get());
163	jsr166	1.2	for (Integer x : c)
164	dl	1.1	psum = SUM.apply(psum, x);
165			checksum.getAndAdd(sum - psum);
166			}
167			return System.nanoTime() - tlast;
168			}
169
170			static long stest(Collection<Integer> c, int sum, int trials) throws Exception {
171			if (c == null) throw new Error();
172			Thread.sleep(250);
173	jsr166	1.4	long tlast = System.nanoTime();
174	dl	1.1	for (int i = 0; i < trials; ++i) {
175			int psum = c.stream().reduce
176			(Integer.valueOf(checksum.get()), SUM);
177			checksum.getAndAdd(sum - psum);
178			}
179			return System.nanoTime() - tlast;
180			}
181
182			static long ptest(Collection<Integer> c, int sum, int trials) throws Exception {
183			if (c == null) throw new Error();
184			Thread.sleep(250);
185	jsr166	1.4	long tlast = System.nanoTime();
186	dl	1.1	for (int i = 0; i < trials; ++i) {
187			int psum = c.parallelStream().reduce
188			(Integer.valueOf(checksum.get()), SUM);
189			checksum.getAndAdd(sum - psum);
190			}
191			return System.nanoTime() - tlast;
192			}
193
194			// misc
195
196			static final long NPS = (1000L * 1000 * 1000);
197			static double elapsedTime(long startTime) {
198			return (double)(System.nanoTime() - startTime) / NPS;
199			}
200
201			static void shuffle(Object[] a) {
202			ThreadLocalRandom rng = ThreadLocalRandom.current();
203			for (int i = a.length; i > 1; i--) {
204			Object t = a[i-1];
205			int r = rng.nextInt(i);
206			a[i-1] = a[r];
207			a[r] = t;
208			}
209			}
210
211			}