test/loops/IteratorLoops.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.*;

/**
 * Estimates time per iteration of collection iterators.  Preloads
 * most elements, but adds about 1/8 of them dynamically to preclude
 * overly clever optimizations. The array of collections has
 * approximately exponentially different lengths, so check both short
 * and long iterators.  Reports include times for adds and other
 * checks, so overestimate times per iteration.
 */
public final class IteratorLoops {
    static final int DEFAULT_SIZE = 16384;
    static final int DEFAULT_TRIALS = 4;
    static final int NC = 16; // number of collections must be power of 2
    static volatile long mismatches = 0;
    static int randomSeed = 3122688;

    public static void main(String[] args) throws Exception {
        Class<?> klass = Class.forName(args[0]);
        int n = (args.length <= 1) ? DEFAULT_SIZE : Integer.parseInt(args[1]);
        int t = (args.length <= 2) ? DEFAULT_TRIALS : Integer.parseInt(args[2]);

        System.out.print("Class: " + klass.getName());
        System.out.print(" ~iters: " + (long) n * (long) n);
        System.out.print(" trials: " + t);
        System.out.println();

        Collection<Integer>[] colls =
            (Collection<Integer>[])new Collection<?>[NC];

        for (int k = 0; k < colls.length; ++k) {
            Object x = klass.getConstructor().newInstance();
            if (x instanceof Collection)
                colls[k] = (Collection<Integer>) x;
            else if (x instanceof Map)
                colls[k] = (Collection<Integer>)
                    Collections.newSetFromMap((Map) x);
            else
                throw new Error("bad class");
        }

        for (int i = 0; i < t; ++i)
            new IteratorLoops(colls).oneRun(n);

        if (mismatches != 0)
            throw new Error("Bad checksum :" + mismatches);
    }

    private int elementCount;
    private final Collection<Integer>[] cs;

    IteratorLoops(Collection<Integer>[] colls) {
        cs = colls;
        elementCount = 0;
    }

    void oneRun(int n) {
        preload(n);
        long startTime = System.nanoTime();
        long count = traversals(n);
        double elapsed = (double) (System.nanoTime() - startTime);
        double npi = elapsed / count;
        double secs = elapsed / 1000000000;
        System.out.printf("%7.1f ns/iter  %8.3fs run time\n", npi, secs);
    }

    long traversals(int n) {
        long count = 0;
        long check = 0;
        for (int i = 0; i < n; i++) {
            check += elementCount;
            count += counts();
            maybeAdd();
        }
        if (count != check)
            mismatches = count;
        return count;
    }

    int counts() {
        int count = 0;
        for (int k = 0; k < cs.length; ++k) {
            for (Integer x : cs[k]) {
                if (x != null)
                    ++count;
            }
        }
        return count;
    }

    void maybeAdd() {
        int r = randomSeed;
        r ^= r << 6;
        r ^= r >>> 21;
        r ^= r << 7;
        randomSeed = r;
        if ((r >>> 29) == 0)
            cs[r & (cs.length-1)].add(new Integer(elementCount++));
    }

    void preload(int n) {
        for (int i = 0; i < cs.length; ++i)
            cs[i].clear();
        int k = (n - n / 8) / 2;
        ArrayList<Integer> al = new ArrayList<Integer>(k+1);
        for (int i = 0; i < cs.length; ++i) {
            if (k > 0) {
                for (int j = 0; j < k; ++j)
                    al.add(new Integer(elementCount++));
                cs[i].addAll(al);
                al.clear();
            }
            k >>>= 1;
        }
        // let GC settle down
        try { Thread.sleep(500); }
        catch (Exception ex) { return; }
    }
}
Revision:	1.14
Committed:	Sun Oct 23 03:03:23 2016 UTC (7 years, 6 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.13:	+1 -1 lines
Log Message:	fix deprecation warnings for Class#newInstance
#	Content
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
9	/**
10	* Estimates time per iteration of collection iterators. Preloads
11	* most elements, but adds about 1/8 of them dynamically to preclude
12	* overly clever optimizations. The array of collections has
13	* approximately exponentially different lengths, so check both short
14	* and long iterators. Reports include times for adds and other
15	* checks, so overestimate times per iteration.
16	*/
17	public final class IteratorLoops {
18	static final int DEFAULT_SIZE = 16384;
19	static final int DEFAULT_TRIALS = 4;
20	static final int NC = 16; // number of collections must be power of 2
21	static volatile long mismatches = 0;
22	static int randomSeed = 3122688;
23
24	public static void main(String[] args) throws Exception {
25	Class<?> klass = Class.forName(args[0]);
26	int n = (args.length <= 1) ? DEFAULT_SIZE : Integer.parseInt(args[1]);
27	int t = (args.length <= 2) ? DEFAULT_TRIALS : Integer.parseInt(args[2]);
28
29	System.out.print("Class: " + klass.getName());
30	System.out.print(" ~iters: " + (long) n * (long) n);
31	System.out.print(" trials: " + t);
32	System.out.println();
33
34	Collection<Integer>[] colls =
35	(Collection<Integer>[])new Collection<?>[NC];
36
37	for (int k = 0; k < colls.length; ++k) {
38	Object x = klass.getConstructor().newInstance();
39	if (x instanceof Collection)
40	colls[k] = (Collection<Integer>) x;
41	else if (x instanceof Map)
42	colls[k] = (Collection<Integer>)
43	Collections.newSetFromMap((Map) x);
44	else
45	throw new Error("bad class");
46	}
47
48	for (int i = 0; i < t; ++i)
49	new IteratorLoops(colls).oneRun(n);
50
51	if (mismatches != 0)
52	throw new Error("Bad checksum :" + mismatches);
53	}
54
55	private int elementCount;
56	private final Collection<Integer>[] cs;
57
58	IteratorLoops(Collection<Integer>[] colls) {
59	cs = colls;
60	elementCount = 0;
61	}
62
63	void oneRun(int n) {
64	preload(n);
65	long startTime = System.nanoTime();
66	long count = traversals(n);
67	double elapsed = (double) (System.nanoTime() - startTime);
68	double npi = elapsed / count;
69	double secs = elapsed / 1000000000;
70	System.out.printf("%7.1f ns/iter %8.3fs run time\n", npi, secs);
71	}
72
73	long traversals(int n) {
74	long count = 0;
75	long check = 0;
76	for (int i = 0; i < n; i++) {
77	check += elementCount;
78	count += counts();
79	maybeAdd();
80	}
81	if (count != check)
82	mismatches = count;
83	return count;
84	}
85
86	int counts() {
87	int count = 0;
88	for (int k = 0; k < cs.length; ++k) {
89	for (Integer x : cs[k]) {
90	if (x != null)
91	++count;
92	}
93	}
94	return count;
95	}
96
97	void maybeAdd() {
98	int r = randomSeed;
99	r ^= r << 6;
100	r ^= r >>> 21;
101	r ^= r << 7;
102	randomSeed = r;
103	if ((r >>> 29) == 0)
104	cs[r & (cs.length-1)].add(new Integer(elementCount++));
105	}
106
107	void preload(int n) {
108	for (int i = 0; i < cs.length; ++i)
109	cs[i].clear();
110	int k = (n - n / 8) / 2;
111	ArrayList<Integer> al = new ArrayList<Integer>(k+1);
112	for (int i = 0; i < cs.length; ++i) {
113	if (k > 0) {
114	for (int j = 0; j < k; ++j)
115	al.add(new Integer(elementCount++));
116	cs[i].addAll(al);
117	al.clear();
118	}
119	k >>>= 1;
120	}
121	// let GC settle down
122	try { Thread.sleep(500); }
123	catch (Exception ex) { return; }
124	}
125	}