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/licenses/publicdomain
 */

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