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

public class MapWordLoops {

    static final String[] WORDS_FILES = {
        "kw.txt",
        "class.txt",
        "dir.txt",
        "ids.txt",
        "testwords.txt",
        //        "/usr/dict/words",
    };

    static final int MAX_WORDS = 500000;
    static final int pinsert   = 60;
    static final int premove   = 2;
    static final int NOPS      = 8000000;

    static final int numTests = 3;

    public static void main(String[] args) {
        Class mapClass = null;
        try {
            mapClass = Class.forName(args[0]);
        } catch (ClassNotFoundException e) {
            throw new RuntimeException("Class " + args[0] + " not found.");
        }

        System.out.println("Testing " + mapClass.getName());

        for (int s = 0; s < WORDS_FILES.length; ++s)
            tests(mapClass, numTests, s);

        for (int s = WORDS_FILES.length-1; s >= 0; --s)
            tests(mapClass, numTests, s);

    }

    static void tests(Class mapClass, int numTests, int sizeIndex) {
        try {
            String[] key = readWords(sizeIndex);
            int size = key.length;

            System.out.print("n = " +LoopHelpers.rightJustify(size) +" : ");
            long least = Long.MAX_VALUE;

            for (int i = 0; i < numTests; ++i) {
                Map<String,String> m = newMap(mapClass);
                long t = doTest(i, mapClass.getName(), m, key);
                if (t < least) least = t;
                m.clear();
                m = null;
            }

            long nano = Math.round(1000000.0 * (least) / NOPS);
            System.out.println(LoopHelpers.rightJustify(nano) + " ns per op");
        } catch (IOException ignore) {
            return; // skip test if can't read file
        }
    }


    static Map<String,String> newMap(Class cl) {
        try {
            Map m = (Map<String,String>)cl.newInstance();
            return m;
        } catch (Exception e) {
            throw new RuntimeException("Can't instantiate " + cl + ": " + e);
        }
    }

    static void pause() {
        try { Thread.sleep(100); }
        catch (InterruptedException ie) { return; }
    }

    static String[] readWords(int sizeIndex) throws IOException {
        String[] l = new String[MAX_WORDS];
        String[] array = null;
        try {
            FileReader fr = new FileReader(WORDS_FILES[sizeIndex]);
            BufferedReader reader = new BufferedReader(fr);
            int k = 0;
            for (;;) {
                String s = reader.readLine();
                if (s == null) break;
                l[k++] = s;
            }
            array = new String[k];
            for (int i = 0; i < k; ++i) {
                array[i] = l[i];
                l[i] = null;
            }
            l = null;
            reader.close();
        }
        catch (IOException ex) {
            System.out.println("Can't read words file:" + ex);
            throw ex;
        }
        return array;
    }

    static long doTest(int id, String name,
                       final Map<String,String> m,
                       final String[] key) {

        //    System.out.print(name + "\t");
        Runner runner = new Runner(id, m, key);
        long startTime = System.currentTimeMillis();
        runner.run();
        long afterRun = System.currentTimeMillis();
        long runTime =  (afterRun - startTime);
        int np = runner.total;
        if (runner.total == runner.hashCode())
            System.out.println("Useless Number" + runner.total);
        int sz = runner.maxsz;
        if (sz == runner.hashCode())
            System.out.println("Useless Number" + sz);
        //        System.out.print(" m = " + sz);
        return runTime;
    }


    static class Runner implements Runnable {
        final Map<String,String> map;
        final String[] key;
        LoopHelpers.SimpleRandom rng;
        final int pctrem;
        final int pctins;
        int nputs = 0;
        int npgets = 0;
        int nagets = 0;
        int nremoves = 0;
        volatile int total;
        int maxsz;

        Runner(int id, Map<String,String> m, String[] k) {
            map = m; key = k;
            pctrem = (int)(((long)premove * (long)(Integer.MAX_VALUE/2)) / 50);
            pctins = (int)(((long)pinsert * (long)(Integer.MAX_VALUE/2)) / 50);
            rng = new LoopHelpers.SimpleRandom((id + 1) * 8862213513L);
        }


        int oneStep(int j) {
            int n = key.length;
            int r = rng.next() & 0x7FFFFFFF;
            int jinc = (r & 7);
            j += jinc - 3;
            if (j >= n) j -= n;
            if (j < 0) j += n;

            int l = n / 4 + j;
            if (l >= n) l -= n;

            String k = key[j];
            String x = map.get(k);

            if (x == null) {
                ++nagets;
                if (r < pctins) {
                    map.put(k, key[l]);
                    ++nputs;
                    int csz = nputs - nremoves;
                    if (csz > maxsz) maxsz = csz;
                }
            }
            else {
                if (k== x) ++npgets;
                if (r < pctrem) {
                    map.remove(k);
                    ++nremoves;
                    j += ((r >>> 8) & 7) +  n / 2;
                    if (j >= n) j -= n;
                }
            }
            return j;
        }

        public void run() {
            int j = key.length / 2;
            for (int i = 0; i < NOPS; ++i) {
                j = oneStep(j);
            }
            total = nputs + npgets + nagets + nremoves;
        }
    }

}
Revision:	1.7
Committed:	Tue Mar 15 19:47:05 2011 UTC (13 years, 1 month ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0
Changes since 1.6:	+1 -1 lines
Log Message:	Update Creative Commons license URL in legal notices
#	User	Rev	Content
1	dl	1.2	/*
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.7	* http://creativecommons.org/publicdomain/zero/1.0/
5	dl	1.2	*/
6	dl	1.1	import java.util.*;
7			import java.io.*;
8
9			public class MapWordLoops {
10
11			static final String[] WORDS_FILES = {
12	jsr166	1.5	"kw.txt",
13	dl	1.1	"class.txt",
14			"dir.txt",
15	jsr166	1.5	"ids.txt",
16	dl	1.4	"testwords.txt",
17	jsr166	1.5	// "/usr/dict/words",
18	dl	1.1	};
19
20			static final int MAX_WORDS = 500000;
21			static final int pinsert = 60;
22	dl	1.4	static final int premove = 2;
23			static final int NOPS = 8000000;
24
25	dl	1.1	static final int numTests = 3;
26
27			public static void main(String[] args) {
28			Class mapClass = null;
29			try {
30			mapClass = Class.forName(args[0]);
31	jsr166	1.6	} catch (ClassNotFoundException e) {
32	dl	1.1	throw new RuntimeException("Class " + args[0] + " not found.");
33			}
34
35			System.out.println("Testing " + mapClass.getName());
36
37	jsr166	1.5	for (int s = 0; s < WORDS_FILES.length; ++s)
38	dl	1.1	tests(mapClass, numTests, s);
39
40	jsr166	1.5	for (int s = WORDS_FILES.length-1; s >= 0; --s)
41	dl	1.1	tests(mapClass, numTests, s);
42
43			}
44
45			static void tests(Class mapClass, int numTests, int sizeIndex) {
46	jsr166	1.5	try {
47	dl	1.1	String[] key = readWords(sizeIndex);
48			int size = key.length;
49	jsr166	1.5
50	dl	1.1	System.out.print("n = " +LoopHelpers.rightJustify(size) +" : ");
51			long least = Long.MAX_VALUE;
52	jsr166	1.5
53	dl	1.1	for (int i = 0; i < numTests; ++i) {
54			Map<String,String> m = newMap(mapClass);
55	dl	1.3	long t = doTest(i, mapClass.getName(), m, key);
56	dl	1.1	if (t < least) least = t;
57			m.clear();
58			m = null;
59			}
60	jsr166	1.5
61	dl	1.1	long nano = Math.round(1000000.0 * (least) / NOPS);
62			System.out.println(LoopHelpers.rightJustify(nano) + " ns per op");
63			} catch (IOException ignore) {
64			return; // skip test if can't read file
65			}
66			}
67
68
69			static Map<String,String> newMap(Class cl) {
70			try {
71			Map m = (Map<String,String>)cl.newInstance();
72			return m;
73	jsr166	1.6	} catch (Exception e) {
74	dl	1.1	throw new RuntimeException("Can't instantiate " + cl + ": " + e);
75			}
76			}
77
78			static void pause() {
79	jsr166	1.6	try { Thread.sleep(100); }
80			catch (InterruptedException ie) { return; }
81	dl	1.1	}
82
83			static String[] readWords(int sizeIndex) throws IOException {
84			String[] l = new String[MAX_WORDS];
85			String[] array = null;
86			try {
87			FileReader fr = new FileReader(WORDS_FILES[sizeIndex]);
88			BufferedReader reader = new BufferedReader(fr);
89			int k = 0;
90			for (;;) {
91			String s = reader.readLine();
92			if (s == null) break;
93			l[k++] = s;
94			}
95			array = new String[k];
96			for (int i = 0; i < k; ++i) {
97			array[i] = l[i];
98			l[i] = null;
99			}
100			l = null;
101			reader.close();
102			}
103			catch (IOException ex) {
104			System.out.println("Can't read words file:" + ex);
105			throw ex;
106			}
107			return array;
108			}
109
110	dl	1.3	static long doTest(int id, String name,
111	jsr166	1.5	final Map<String,String> m,
112	dl	1.1	final String[] key) {
113
114			// System.out.print(name + "\t");
115	dl	1.3	Runner runner = new Runner(id, m, key);
116	dl	1.1	long startTime = System.currentTimeMillis();
117			runner.run();
118			long afterRun = System.currentTimeMillis();
119			long runTime = (afterRun - startTime);
120			int np = runner.total;
121	jsr166	1.5	if (runner.total == runner.hashCode())
122	dl	1.1	System.out.println("Useless Number" + runner.total);
123			int sz = runner.maxsz;
124	jsr166	1.5	if (sz == runner.hashCode())
125	dl	1.1	System.out.println("Useless Number" + sz);
126			// System.out.print(" m = " + sz);
127			return runTime;
128			}
129
130
131			static class Runner implements Runnable {
132			final Map<String,String> map;
133			final String[] key;
134	dl	1.3	LoopHelpers.SimpleRandom rng;
135	dl	1.1	final int pctrem;
136			final int pctins;
137			int nputs = 0;
138			int npgets = 0;
139			int nagets = 0;
140			int nremoves = 0;
141			volatile int total;
142			int maxsz;
143
144	dl	1.3	Runner(int id, Map<String,String> m, String[] k) {
145	jsr166	1.5	map = m; key = k;
146	dl	1.1	pctrem = (int)(((long)premove * (long)(Integer.MAX_VALUE/2)) / 50);
147			pctins = (int)(((long)pinsert * (long)(Integer.MAX_VALUE/2)) / 50);
148	dl	1.3	rng = new LoopHelpers.SimpleRandom((id + 1) * 8862213513L);
149	dl	1.1	}
150
151
152			int oneStep(int j) {
153			int n = key.length;
154			int r = rng.next() & 0x7FFFFFFF;
155			int jinc = (r & 7);
156			j += jinc - 3;
157	jsr166	1.5	if (j >= n) j -= n;
158	dl	1.1	if (j < 0) j += n;
159
160			int l = n / 4 + j;
161	jsr166	1.5	if (l >= n) l -= n;
162
163	dl	1.1	String k = key[j];
164			String x = map.get(k);
165	jsr166	1.5
166	dl	1.1	if (x == null) {
167			++nagets;
168			if (r < pctins) {
169			map.put(k, key[l]);
170			++nputs;
171			int csz = nputs - nremoves;
172			if (csz > maxsz) maxsz = csz;
173			}
174			}
175			else {
176			if (k== x) ++npgets;
177			if (r < pctrem) {
178			map.remove(k);
179			++nremoves;
180			j += ((r >>> 8) & 7) + n / 2;
181			if (j >= n) j -= n;
182			}
183			}
184			return j;
185			}
186
187			public void run() {
188			int j = key.length / 2;
189			for (int i = 0; i < NOPS; ++i) {
190			j = oneStep(j);
191			}
192			total = nputs + npgets + nagets + nremoves;
193			}
194			}
195
196			}