test/loops/MapWordLoops.java

import java.util.*;
import java.io.*;

public class MapWordLoops {

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

    static final int MAX_WORDS = 500000;
    static final int pinsert   = 60;
    static final int premove   = 1;
    static final int NOPS      = 5000000;
    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(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(String name,
                       final Map<String,String> m, 
                       final String[] key) {

        //    System.out.print(name + "\t");
        Runner runner = new Runner(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 = new LoopHelpers.SimpleRandom();
        final int pctrem;
        final int pctins;
        int nputs = 0;
        int npgets = 0;
        int nagets = 0;
        int nremoves = 0;
        volatile int total;
        int maxsz;

        Runner(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);
        }


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