TimeHashes


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8    * copies of the Software, and to permit persons to whom the Software is
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20   * IN THE SOFTWARE.
21   */
22  
23  import java.util.*;
24  
25  import com.sosnoski.util.hashset.*;
26  
27  /**
28   * Benchmark to compare the performance of hash sets. The basic test is
29   * repeatedly generating a set of pseudo-random <code>String</code>s and adding
30   * them to a hash set, then looking up all the items present in the hash set as
31   * well as a number of items not present in the set. Several variations of
32   * the test are performed, each using a different hash set variation.<p>
33   *
34   * For accurate timing results this should be run with a pass count of at least
35   * 3 and the timings for the final pass should be compared. Running with a
36   * lower number of passes may give unoptimized results with a HotSpot-type JVM.
37   * It's also best to use a large number of <code>String</code>s (perhaps
38   * 200000 or more, with the JVM memory set to 64M or more) for the test; results
39   * with low numbers of <code>String</code>s may be very inaccurate, especially
40   * since they'll depend heavily on the default sizes of the tables.
41   *
42   * @author Dennis M. Sosnoski
43   * @version 1.0
44   */
45  
46  public class TimeHashes
47  {
48      /**
49       * Default count of test passes to be executed.
50       */
51  
52      public static final int DEFAULT_PASS_COUNT = 1;
53  
54      /**
55       * Delay in milliseconds between test passes.
56       */
57  
58      public static final int DELAY_BETWEEN_TESTS = 1000;
59  
60      /**
61       * Time to wait after requesting a garbage collection.
62       */
63  
64      public static final int GARBAGE_COLLECT_DELAY = 200;
65  
66      /**
67       * Additive constant value for pseudo-random number generator.
68       */
69  
70      public static final int SEQUENCE_ADD = 11;
71  
72      /**
73       * Multiplicative constant value for pseudo-random number generator.
74       */
75  
76      public static final int SEQUENCE_MULTIPLY = 43;
77  
78      /** Shortest <code>String</code> length used for test. */
79      public static final int MINIMUM_STRING_LENGTH = 4;
80  
81      /** Longest <code>String</code> length used for test. */
82      public static final int MAXIMUM_STRING_LENGTH = 12;
83  
84      /**
85       * Last value in generated pseudo-random value sequence.
86       */
87  
88      private int lastValue;
89  
90      /**
91       * Start time for test run.
92       */
93  
94      private long startTime;
95  
96      /**
97       * Check value for validating test results.
98       */
99  
100     private int checkResult;
101 
102     /**
103      * Flag for printing of test results enabled.
104      */
105 
106     private boolean printFlag;
107 
108     /**
109      * Generates the next value in the pseudo-random sequence used for
110      * controlling the test.
111      *
112      * @return next value in sequence
113      */
114 
115     protected int nextInSequence() {
116         lastValue = (lastValue + SEQUENCE_ADD) * SEQUENCE_MULTIPLY;
117         return lastValue & Integer.MAX_VALUE;
118     }
119 
120     /**
121      * Constructs a set of pseudo-random <code>String</code> values.
122      *
123      * @param set array to be filled with constructed <code>String</code>s
124      */
125 
126     public void buildSet(String  [] set) {
127         char[] chars = new char[MAXIMUM_STRING_LENGTH];
128         for (int i = 0; i < set.length; i++) {
129             int length = MINIMUM_STRING_LENGTH + nextInSequence() %
130                 (MAXIMUM_STRING_LENGTH-MINIMUM_STRING_LENGTH+1);
131             for (int j = 0; j < length; j++) {
132                 char chr = (char)('a' + nextInSequence() % ('z'-'a'+1));
133                 chars[j] = chr;
134             }
135             set[i] = new String  (chars, 0, length);
136         }
137     }
138 
139     /**
140      * Add a set of <code>String</code>s to a hash set. This method is
141      * implemented once for each variety of hash set being tested.
142      *
143      * @param set <code>String</code> set to be added
144      * @param hashset hash set to be filled with <code>String</code>s
145      */
146 
147     public void addSet(String  [] set, HashSet hashset) {
148         for (int i = 0; i < set.length; i++) {
149             hashset.add(set[i]);
150         }
151     }
152 
153     public void addSet(String  [] set, ObjectHashSet hashset) {
154         for (int i = 0; i < set.length; i++) {
155             hashset.add(set[i]);
156         }
157     }
158 
159     public void addSet(String  [] set, StringHashSet hashset) {
160         for (int i = 0; i < set.length; i++) {
161             hashset.add(set[i]);
162         }
163     }
164 
165     /**
166      * Count how many of a set of <code>String</code>s are present in a hash
167      * set. This method is implemented once for each variety of hash set being
168      * tested.
169      *
170      * @param set <code>String</code> set to be checked
171      * @param hashset hash set to be checked for <code>String</code>s
172      * @return number of <code>String</code>s from set present in hash set
173      */
174 
175     public int countPresent(String  [] set, HashSet hashset) {
176         int count = 0;
177         for (int i = 0; i < set.length; i++) {
178             if (hashset.contains(set[i])) {
179                 count++;
180             }
181         }
182         return count;
183     }
184 
185     public int countPresent(String  [] set, ObjectHashSet hashset) {
186         int count = 0;
187         for (int i = 0; i < set.length; i++) {
188             if (hashset.contains(set[i])) {
189                 count++;
190             }
191         }
192         return count;
193     }
194 
195     public int countPresent(String  [] set, StringHashSet hashset) {
196         int count = 0;
197         for (int i = 0; i < set.length; i++) {
198             if (hashset.contains(set[i])) {
199                 count++;
200             }
201         }
202         return count;
203     }
204 
205     /**
206      * Resets the test timer in preparation for running a test.
207      */
208 
209     protected final void startTimer() {
210         startTime = System.currentTimeMillis();
211     }
212 
213     /**
214      * Attempts to trigger a garbage collection in preparation for running a
215      * test.
216      */
217 
218     protected final void cleanMemory() {
219         Runtime   rt = Runtime.getRuntime();
220         try {
221             rt.gc();
222             Thread.sleep(GARBAGE_COLLECT_DELAY);
223             rt.gc();
224             Thread.sleep(GARBAGE_COLLECT_DELAY);
225             rt.gc();
226             Thread.sleep(GARBAGE_COLLECT_DELAY);
227             rt.gc();
228             Thread.sleep(GARBAGE_COLLECT_DELAY);
229         } catch (InterruptedException   ex) {}
230     }
231 
232     /**
233      * Prints the time taken for a particular test run. This method only
234      * generates output if the <code>printFlag</code> value is
235      * <code>true</code>. It assumes the <code>startTimer</code> method was
236      * called prior to the start of the test, and sets the start time for
237      * the next set to the time when called.
238      *
239      * @param text description text for test
240      */
241 
242     protected void printTestTime(String   text) {
243         if (printFlag) {
244             long time = System.currentTimeMillis() - startTime;
245             System.out.println("Ran " + text + " test in " + time + " ms");
246             startTime += time;
247         }
248     }
249 
250     /**
251      * Prints the time taken for a particular test run. This method only
252      * generates output if the <code>printFlag</code> value is
253      * <code>true</code>. It assumes the <code>startTimer</code> method was
254      * called prior to the start of the test, and sets the start time for
255      * the next set to the time when called.
256      *
257      * @param result result value from test run (used for validation)
258      * @param text description text for test
259      */
260 
261     protected void printTestTime(int result, String   text) {
262         if (printFlag) {
263             printTestTime(text);
264             if (result != checkResult) {
265                 System.out.println("  Warning: test result " + result +
266                     " does not match check value of " + checkResult +
267                     " (normal when IDENTITY_COMP or IDENTITY_HASH used)");
268             }
269         }
270     }
271 
272     /**
273      * Runs the entire sequence of tests. If printing results is enabled, the
274      * results of each timing test are printed immediately after that test is
275      * executed.
276      *
277      * @param count number of <code>String</code>s to generate in set
278      * @param print flag for printing results
279      * @return sum of all test result values
280      */
281 
282     public int runAllTests(int count, boolean print) {
283 
284         // print test run header
285         printFlag = print;
286         if (print) {
287             System.out.println("Running tests with " + count +
288                 " Strings in set.");
289         }
290 
291         // run the tests
292         int reset = lastValue;
293         cleanMemory();
294         String  [] iset = new String  [count];
295         String  [] xset = new String  [count];
296         buildSet(iset);
297         buildSet(xset);
298         HashSet hs = new HashSet();
299         startTimer();
300         addSet(iset, hs);
301         printTestTime("HashSet fill");
302         int result = countPresent(iset, hs) + countPresent(xset, hs);
303         checkResult = result;
304         printTestTime(result, "HashSet lookup");
305         int sum = result;
306         iset = null;
307         xset = null;
308         hs = null;
309         cleanMemory();
310         lastValue = reset;
311         iset = new String  [count];
312         xset = new String  [count];
313         buildSet(iset);
314         buildSet(xset);
315         StringHashSet shs = new StringHashSet();
316         startTimer();
317         addSet(iset, shs);
318         printTestTime("default StringHashSet fill");
319         result = countPresent(iset, shs) + countPresent(xset, shs);
320         printTestTime(result, "default StringHashSet lookup");
321         sum += result;
322         iset = null;
323         xset = null;
324         shs = null;
325         cleanMemory();
326         lastValue = reset;
327         iset = new String  [count];
328         xset = new String  [count];
329         buildSet(iset);
330         buildSet(xset);
331         ObjectHashSet ohs = new ObjectHashSet();
332         startTimer();
333         addSet(iset, ohs);
334         printTestTime("default ObjectHashSet fill");
335         result = countPresent(iset, ohs) + countPresent(xset, ohs);
336         printTestTime(result, "default ObjectHashSet lookup");
337         sum += result;
338         iset = null;
339         xset = null;
340         ohs = null;
341         cleanMemory();
342         lastValue = reset;
343         iset = new String  [count];
344         xset = new String  [count];
345         buildSet(iset);
346         buildSet(xset);
347         shs = new StringHashSet(StringHashSet.IDENTITY_COMP);
348         startTimer();
349         addSet(iset, shs);
350         printTestTime("IDENTITY_COMP StringHashSet fill");
351         result = countPresent(iset, shs) + countPresent(xset, shs);
352         printTestTime(result, "IDENTITY_COMP StringHashSet lookup");
353         sum += result;
354         iset = null;
355         xset = null;
356         shs = null;
357         cleanMemory();
358         lastValue = reset;
359         iset = new String  [count];
360         xset = new String  [count];
361         buildSet(iset);
362         buildSet(xset);
363         ohs = new ObjectHashSet(ObjectHashSet.IDENTITY_COMP);
364         startTimer();
365         addSet(iset, ohs);
366         printTestTime("IDENTITY_COMP ObjectHashSet fill");
367         result = countPresent(iset, ohs) + countPresent(xset, ohs);
368         printTestTime(result, "IDENTITY_COMP ObjectHashSet lookup");
369         sum += result;
370         iset = null;
371         xset = null;
372         ohs = null;
373         cleanMemory();
374         lastValue = reset;
375         iset = new String  [count];
376         xset = new String  [count];
377         buildSet(iset);
378         buildSet(xset);
379         shs = new StringHashSet(StringHashSet.IDENTITY_HASH);
380         startTimer();
381         addSet(iset, shs);
382         printTestTime("IDENTITY_HASH StringHashSet fill");
383         result = countPresent(iset, shs) + countPresent(xset, shs);
384         printTestTime(result, "IDENTITY_HASH StringHashSet lookup");
385         sum += result;
386         iset = null;
387         xset = null;
388         shs = null;
389         cleanMemory();
390         lastValue = reset;
391         iset = new String  [count];
392         xset = new String  [count];
393         buildSet(iset);
394         buildSet(xset);
395         ohs = new ObjectHashSet(ObjectHashSet.IDENTITY_HASH);
396         startTimer();
397         addSet(iset, ohs);
398         printTestTime("IDENTITY_HASH ObjectHashSet fill");
399         result = countPresent(iset, ohs) + countPresent(xset, ohs);
400         printTestTime(result, "IDENTITY_HASH ObjectHashSet lookup");
401         sum += result;
402         iset = null;
403         xset = null;
404         ohs = null;
405         cleanMemory();
406         lastValue = reset;
407         return sum;
408     }
409 
410     /**
411      * Test driver, just reads the input parameters and executes the test.  If
412      * requested, multiple test passes may be run.
413      *
414      * @param argv command line arguments
415      */
416 
417     public static void main(String  [] argv) {
418         if (argv.length > 0) {
419 
420             // parse the parameter values
421             int count = Integer.parseInt(argv[0]);
422             int passes = 0;
423             if (argv.length > 1) {
424                 passes = Integer.parseInt(argv[1]);
425             }
426 
427             // construct the test instance
428             TimeHashes inst = new TimeHashes();
429 
430             // report basic information
431             System.out.println("Java version " + System.getProperty("java.version"));
432             String   text = System.getProperty("java.vm.name");
433             int lines = 1;
434             if (text != null) {
435                 System.out.println(text);
436                 lines++;
437             }
438             text = System.getProperty("java.vm.version");
439             if (text != null) {
440                 System.out.println(text);
441                 lines++;
442             }
443             text = System.getProperty("java.vm.vendor");
444             if (text == null) {
445                 text = System.getProperty("java.vendor");
446             }
447             System.out.println(text);
448 
449             // align headers for convenient printout comparison
450             while (++lines < 5) {
451                 System.out.println("");
452             }
453 
454             // execute the specified number of test passes
455             int sum = 0;
456             if (passes == 0) {
457                 System.out.println("Running initialization pass...");
458                 inst.runAllTests(count / 5, false);
459                 try {
460                     Thread.sleep(DELAY_BETWEEN_TESTS);
461                 } catch (InterruptedException   ex) {}
462                 sum += inst.runAllTests(count, true);
463             } else {
464                 for (int i = 0; i < passes; i++) {
465                     sum += inst.runAllTests(count, true);
466                     if (i < passes) {
467                         try {
468                             Thread.sleep(DELAY_BETWEEN_TESTS);
469                         } catch (InterruptedException   ex) {}
470                     }
471                 }
472             }
473             System.out.println("Check result value " + inst.checkResult);
474 
475         } else {
476             System.out.println("Requires parameters:\n" +
477                 " count - the number of Strings to be added to hash set\n" +
478                 " [passes] - number of test passes to run (default is single printed\n" +
479                 "            pass after initialization pass with one-fifth the loops\n");
480         }
481     }
482 }
483
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags