jars/icu4j-52_1/main/tests/core/src/com/ibm/icu/dev/test/util/TrieMapTest.java

   1 /*
   2  *******************************************************************************
   3  * Copyright (C) 2011-2012, Google, International Business Machines Corporation and
   4  * others. All Rights Reserved.
   5  *******************************************************************************
   6  */
   7 package com.ibm.icu.dev.test.util;
   8
   9 import java.util.ArrayList;
  10 import java.util.Arrays;
  11 import java.util.HashMap;
  12 import java.util.HashSet;
  13 import java.util.Iterator;
  14 import java.util.List;
  15 import java.util.Map;
  16 import java.util.Map.Entry;
  17 import java.util.TreeMap;
  18
  19 import com.ibm.icu.dev.test.TestFmwk;
  20 import com.ibm.icu.dev.test.util.TrieMap.Style;
  21 import com.ibm.icu.dev.util.Timer;
  22 import com.ibm.icu.impl.Row;
  23 import com.ibm.icu.impl.Row.R3;
  24 import com.ibm.icu.impl.Utility;
  25 import com.ibm.icu.lang.UCharacter;
  26 import com.ibm.icu.lang.UScript;
  27 import com.ibm.icu.text.DecimalFormat;
  28 import com.ibm.icu.text.UnicodeSet;
  29 import com.ibm.icu.util.StringTrieBuilder.Option;
  30 import com.ibm.icu.util.ULocale;
  31
  32 public class TrieMapTest extends TestFmwk {
  33     static final boolean SHORT = false;
  34     static final boolean HACK_TO_MAKE_TESTS_PASS = false;
  35     static final int MASK = 0x3;
  36
  37     private Map<String, Integer> unicodeTestMap = new HashMap<String, Integer>();
  38     private boolean useSmallList = true;
  39
  40     private Timer t = new Timer();
  41     private DecimalFormat nf = t.getNumberFormat();
  42     private DecimalFormat pf = t.getPercentFormat();
  43     {
  44         pf.setMaximumFractionDigits(0);
  45     }
  46
  47     @Override
  48     protected void init() throws Exception {
  49         super.init();
  50         if (unicodeTestMap.size() == 0) {
  51             if (getInclusion() < 5) {
  52                 logln("\tShort version, timing for 1s:\t to get more accurate figures and test for reasonable times, use -e5 or more");
  53                 t.setTimingPeriod(1*Timer.SECONDS);
  54             } else {
  55                 int seconds = getInclusion();
  56                 logln("\tExhaustive version, timing for " + seconds + "s");
  57                 t.setTimingPeriod(seconds*Timer.SECONDS);
  58                 useSmallList = false;
  59             }
  60
  61             int i = 0;
  62             UnicodeSet testSet = new UnicodeSet("[[:^C:]-[:sc=han:]]");
  63             for (String s : testSet) {
  64                 int codePoint = s.codePointAt(0);
  65                 String extendedName = UCharacter.getExtendedName(codePoint);
  66                 if (!unicodeTestMap.containsKey(extendedName)) {
  67                     unicodeTestMap.put(extendedName, i++);
  68                 }
  69                 if (i > 500 && useSmallList) break;
  70             }
  71             ULocale[] locales = useSmallList ? new ULocale[] {new ULocale("zh"), new ULocale("el")} : ULocale.getAvailableLocales();
  72             for (ULocale locale : locales) {
  73                 if (locale.getDisplayCountry().length() != 0) {
  74                     continue;
  75                 }
  76                 String localeName;
  77                 for (String languageCode : ULocale.getISOLanguages()) {
  78                     localeName = ULocale.getDisplayName(languageCode, locale);
  79                     if (!localeName.equals(languageCode)) {
  80                         if (!unicodeTestMap.containsKey(localeName)) {
  81                             unicodeTestMap.put(localeName, MASK & i++);
  82                         }
  83                         if (SHORT) break;
  84                     }
  85                 }
  86                 for (String countryCode : ULocale.getISOCountries()) {
  87                     localeName = ULocale.getDisplayCountry("und-" + countryCode, locale);
  88                     if (!localeName.equals(countryCode)) {
  89                         if (!unicodeTestMap.containsKey(localeName)) {
  90                             unicodeTestMap.put(localeName, MASK & i++);
  91                         }
  92                         if (SHORT) break;
  93                     }
  94                 }
  95             }
  96             int charCount = 0;
  97             for (String key : unicodeTestMap.keySet()) {
  98                 charCount += key.length();
  99             }
 100             logln("\tTest Data Elements:\t\t\t" + nf.format(unicodeTestMap.size()));
 101             logln("\tTotal chars:\t\t\t" + nf.format(charCount));
 102         }
 103     }
 104
 105     public static void main(String[] args) {
 106         new TrieMapTest().run(args);
 107     }
 108
 109     public void TestByteConversion() {
 110         byte bytes[] = new byte[200];
 111         for (Entry<String, Integer> entry : unicodeTestMap.entrySet()) {
 112             String source = entry.getKey();
 113             int limit = TrieMap.ByteConverter.getBytes(source, bytes, 0);
 114             //logln(source + "\t=> " + Utility.hex(source, " ") + "\t=> " + Utility.hex(bytes, 0, limit, " "));
 115             String recovered = TrieMap.ByteConverter.getChars(bytes, 0, limit);
 116             if (!source.equals(recovered)) {
 117                 assertEquals("Char/Byte Conversion", source, recovered);
 118             }
 119         }
 120     }
 121
 122     public void TestGet() {
 123         checkGet(unicodeTestMap, TrieMap.Style.BYTES);
 124         checkGet(unicodeTestMap, TrieMap.Style.CHARS);
 125     }
 126
 127     private void checkGet(Map<String, Integer> testmap, TrieMap.Style style) {
 128         if (testmap.size() == 0) {
 129             return;
 130         }
 131         TrieMap<Integer> trieMap = TrieMap.Builder.with(style, Option.SMALL, testmap).build();
 132         //logln(trieMap.toString());
 133         for (Entry<String, Integer> entry : testmap.entrySet()) {
 134             Integer value = entry.getValue();
 135             String key = entry.getKey();
 136             Integer foundValue = trieMap.get(key);
 137             if (!value.equals(foundValue)) {
 138                 // TODO fix this
 139                 if (!HACK_TO_MAKE_TESTS_PASS || 39497 != value) {
 140                     assertEquals(style + "\tGet of '" + key + "' = {" + Utility.hex(key) + "}", value, foundValue);
 141                 }
 142             }
 143         }
 144     }
 145
 146     public void TestTimeIteration() {
 147         long comparisonTime = timeIteration(unicodeTestMap, 0, null, 0);
 148         timeIteration(unicodeTestMap, comparisonTime, null, 0);
 149         timeIteration(unicodeTestMap, comparisonTime, Style.BYTES, 5);
 150         timeIteration(unicodeTestMap, comparisonTime, Style.CHARS, 3);
 151     }
 152
 153     @SuppressWarnings("unused")
 154     public long timeIteration(Map<String, Integer> testMap, long comparisonTime, Style style, double ratioToMap) {
 155         TrieMap<Integer> trieMap = TrieMap.BytesBuilder.with(style, Option.SMALL, testMap).build();
 156         TreeMap<String,Integer> expected = new TreeMap<String, Integer>(testMap);
 157
 158         System.gc();
 159         t.start();
 160         if (style == null) {
 161             Map<String, Integer> map = comparisonTime == 0 ? new TreeMap<String, Integer>(testMap) : new HashMap<String, Integer>(testMap);
 162
 163             long mapTime = t.timeIterations(new MyLoop() {
 164                 public void time(int repeat) {
 165                     for (int tt = 0; tt < repeat; ++tt) {
 166                         for (Entry<String, Integer> entry : map.entrySet()) {
 167                             String key = entry.getKey();
 168                             Integer value = entry.getValue();
 169                         }
 170                     }
 171                 }
 172             }, null, map);
 173             if (comparisonTime == 0) {
 174                 logln("\titeration time\tTREEMAP\tn/a\t" + t.toString(testMap.size()) + "\t\titerations=" + t.getIterations());
 175             } else {
 176                 logln("\titeration time\tHASHMAP\tn/a\t" + t.toString(testMap.size(), comparisonTime) + "\titerations=" + t.getIterations());
 177             }
 178             return mapTime;
 179         } else {
 180             long trieTime = t.timeIterations(new MyLoop() {
 181                 public void time(int repeat) {
 182                     for (int tt = 0; tt < repeat; ++tt) {
 183                         for (Entry<CharSequence, Integer> entry : trieMap) {
 184                             CharSequence key = entry.getKey();
 185                             Integer value = entry.getValue();
 186                         }
 187                     }
 188                 }
 189             }, null, trieMap);
 190             logln("\titeration time\t" + style + "\tn/a\t" + t.toString(testMap.size(), comparisonTime) + "\titerations=" + t.getIterations());
 191             if (!useSmallList && trieTime > ratioToMap * comparisonTime) {
 192                 errln(style + "\tTime iteration takes too long. Expected:\t< " + ratioToMap * comparisonTime + ", Actual:\t" + trieTime);
 193             }
 194             return trieTime;
 195         }
 196     }
 197
 198     public void TestContents() {
 199         checkContents(unicodeTestMap, Style.BYTES);
 200         checkContents(unicodeTestMap, Style.CHARS);
 201     }
 202
 203     public void checkContents(Map<String, Integer> testMap, Style style) {
 204         if (testMap.size() == 0) {
 205             return;
 206         }
 207         TrieMap<Integer> trieMap = TrieMap.BytesBuilder.with(style, Option.SMALL, testMap).build();
 208         TreeMap<String,Integer> expected = new TreeMap<String, Integer>(testMap);
 209         Iterator<Entry<CharSequence, Integer>> trieIterator = trieMap.iterator();
 210         Iterator<Entry<String, Integer>> mapIterator = expected.entrySet().iterator();
 211         while (true) {
 212             boolean trieOk = trieIterator.hasNext();
 213             boolean mapOk = mapIterator.hasNext();
 214             if (mapOk!=trieOk) {
 215                 assertEquals("Iterators end at same point", mapOk, trieOk);
 216             }
 217
 218             if (!mapOk) break;
 219             Entry<CharSequence, Integer> trieEntry = trieIterator.next();
 220             Entry<String, Integer> mapEntry = mapIterator.next();
 221             String mapKey = mapEntry.getKey();
 222             CharSequence trieKey = trieEntry.getKey();
 223             if (!mapKey.contentEquals(trieKey)) {
 224                 assertEquals(style + "\tKeys match", mapKey, trieKey.toString());
 225             }
 226             Integer mapValue = mapEntry.getValue();
 227             Integer trieValue = trieEntry.getValue();
 228             if (!mapValue.equals(trieValue)) {
 229                 assertEquals(style + "\tValues match", mapValue, trieValue);
 230             }
 231         }
 232     }
 233
 234     public void TestSearch() {
 235         checkSearch(Style.BYTES);
 236         checkSearch(Style.CHARS);
 237     }
 238
 239     public void checkSearch(Style style) {
 240
 241         TrieMap<String> trieMap = TrieMap.BytesBuilder.with(style, Option.SMALL, "abc", "first")
 242         .add("cdab", "fifth")
 243         .add("abcde", "second")
 244         .add("abdfg", "third").build();
 245
 246         String string = "xabcdab abcde abdfg";
 247         @SuppressWarnings("unchecked")
 248         Row.R3<Integer, Integer, String>[] expected = new Row.R3[] {
 249             Row.of(1,4,"first"),
 250             Row.of(3,7,"fifth"),
 251             Row.of(8,11,"first"),
 252             Row.of(8,13,"second"),
 253             Row.of(14,19,"third"),
 254         };
 255         List<R3<Integer, Integer, String>> expectedList = Arrays.asList(expected);
 256         List<R3<Integer, Integer, String>> actualList = new ArrayList<R3<Integer, Integer, String>>();
 257
 258         TrieMap.Matcher<String> matcher = trieMap.getMatcher();
 259         matcher.set(string, 0);
 260         do {
 261             boolean hasMore;
 262             do {
 263                 hasMore = matcher.next();
 264                 String value = matcher.getValue();
 265                 if (value != null) {
 266                     int start = matcher.getStart();
 267                     int end = matcher.getEnd();
 268                     actualList.add(Row.of(start,end,value));
 269                 }
 270             } while (hasMore);
 271         } while (matcher.nextStart());
 272         assertEquals(style + "\tTrieMap matcher", expectedList, actualList);
 273         //        logln(bytes + "\tValue <" + value + "> at "
 274         //                + start + ".." + end + ", "
 275         //                + string.substring(0, start) + "|"
 276         //                + string.substring(start, end) + "|"
 277         //                + string.substring(end)
 278         //        );
 279     }
 280
 281     public void TestTimeBuilding() {
 282         long comparisonTime = timeBuilding(unicodeTestMap, 0, null, Option.SMALL, 0);
 283         timeBuilding(unicodeTestMap, comparisonTime, null, Option.SMALL, 0);
 284         timeBuilding(unicodeTestMap, comparisonTime, Style.BYTES, Option.SMALL, 20);
 285         timeBuilding(unicodeTestMap, comparisonTime, Style.BYTES, Option.FAST, 20);
 286         timeBuilding(unicodeTestMap, comparisonTime, Style.CHARS, Option.SMALL, 20);
 287         timeBuilding(unicodeTestMap, comparisonTime, Style.CHARS, Option.FAST, 20);
 288     }
 289
 290     @SuppressWarnings("unused")
 291     public long timeBuilding(Map<String, Integer> testmap, long comparisonTime, Style style, Option option, double ratioToMap) {
 292         System.gc();
 293         t.start();
 294         if (style == null) {
 295             if (comparisonTime == 0) {
 296                 long mapTime = t.timeIterations(new MyLoop() {
 297                     public void time(int repeat) {
 298                         for (int tt = 0; tt < repeat; ++tt) {
 299                             Map<String, Integer> map2 = new TreeMap<String, Integer>(map);
 300                         }
 301                     }
 302                 }, null, testmap);
 303                 logln("\tbuild time\tTREEMAP\tn/a\t" + t.toString(testmap.size()) + "\t\titerations=" + t.getIterations());
 304                 return mapTime;
 305             } else {
 306                 long mapTime = t.timeIterations(new MyLoop() {
 307                     public void time(int repeat) {
 308                         for (int tt = 0; tt < repeat; ++tt) {
 309                             Map<String, Integer> map2 = new HashMap<String, Integer>(map);
 310                         }
 311                     }
 312                 }, null, testmap);
 313                 logln("\tbuild time\tHASHMAP\tn/a\t" + t.toString(testmap.size(), comparisonTime) + "\titerations=" + t.getIterations());
 314                 return mapTime;
 315             }
 316         } else {
 317             long trieTime = t.timeIterations(new MyLoop() {
 318                 public void time(int repeat) {
 319                     for (int tt = 0; tt < repeat; ++tt) {
 320                         trieMap = TrieMap.BytesBuilder.with(style, option, map).build();
 321                     }
 322                 }
 323             }, null, testmap, style, option);
 324
 325             logln("\tbuild time\t" + style + "\t" + option + "\t" + t.toString(testmap.size(), comparisonTime) + "\titerations=" + t.getIterations());
 326             if (!useSmallList && trieTime > ratioToMap * comparisonTime) {
 327                 errln(style + "\t" + option + "\tTrie build takes too long. Expected:\t< " + nf.format(ratioToMap * comparisonTime) + ", Actual:\t" + nf.format(trieTime));
 328             }
 329             return trieTime;
 330         }
 331     }
 332
 333     public void TestSize() {
 334         int size = checkSize(0, null, Option.SMALL, 0);
 335         checkSize(size, Style.BYTES, Option.SMALL, 0.20);
 336         checkSize(size, Style.BYTES, Option.FAST, 0.20);
 337         checkSize(size, Style.CHARS, Option.SMALL, 0.30);
 338         checkSize(size, Style.CHARS, Option.FAST, 0.30);
 339     }
 340
 341     /**
 342      * @param option TODO
 343      * @param ratioToMap TODO
 344      * @param bytes
 345      */
 346     private int checkSize(int comparisonSize, Style style, Option option, double ratioToMap) {
 347         if (style == null) {
 348             int mapKeyByteSize = 0;
 349             TreeMap<String, Integer> map = new TreeMap<String, Integer>(unicodeTestMap);
 350             for (Entry<String, Integer> entry : map.entrySet()) {
 351                 mapKeyByteSize += 8 * (int) ((((entry.getKey().length()) * 2) + 45) / 8);
 352             }
 353             logln("\tkey byte size\tTREEMAP\tn/a\t" + nf.format(mapKeyByteSize));
 354             return mapKeyByteSize;
 355         } else {
 356             TrieMap<Integer> trieMap = TrieMap.BytesBuilder.with(style, option, unicodeTestMap).build();
 357
 358             int trieKeyByteSize = trieMap.keyByteSize();
 359             logln("\tkey byte size\t" + style + "\t" + option + "\t" + nf.format(trieKeyByteSize) + "\t\t" + pf.format(trieKeyByteSize/(double)comparisonSize - 1D) + "");
 360
 361
 362             if (!useSmallList && trieKeyByteSize > ratioToMap * comparisonSize) {
 363                 errln(style + "\t" + option + "\ttrieKeyByteSize too large. Expected:\t< " + nf.format(ratioToMap * comparisonSize) + ", Actual:\t" + nf.format(trieKeyByteSize));
 364             }
 365             return trieKeyByteSize;
 366         }
 367     }
 368
 369     public void TestTimeGet() {
 370         HashSet<String> keySet = new HashSet<String>(unicodeTestMap.keySet());
 371         ULocale[] locales = ULocale.getAvailableLocales();
 372         int i = 0;
 373         for (ULocale locale : locales) {
 374             if (locale.getDisplayCountry().length() != 0) {
 375                 continue;
 376             }
 377             String localeName;
 378             for (int scriptCodeInt = 0; scriptCodeInt < UScript.CODE_LIMIT; ++scriptCodeInt) {
 379                 String scriptCode = UScript.getShortName(scriptCodeInt);
 380                 localeName = ULocale.getDisplayScript("und-" + scriptCode, locale);
 381                 if (!localeName.equals(scriptCode)) {
 382                     if (!keySet.contains(localeName)) {
 383                         keySet.add(localeName);
 384                         ++i;
 385                     }
 386                     if (SHORT) break;
 387                 }
 388             }
 389         }
 390         logln("\tExtra Key Elements\t" + i);
 391
 392         ArrayList<String> keys = new ArrayList<String>(keySet);
 393
 394         long comparisonTime = timeGet(keys, unicodeTestMap, 0, null, 0);
 395         timeGet(keys, unicodeTestMap, comparisonTime, null, 0);
 396         timeGet(keys, unicodeTestMap, comparisonTime, Style.BYTES, 3);
 397         timeGet(keys, unicodeTestMap, comparisonTime, Style.CHARS, 3);
 398     }
 399
 400     @SuppressWarnings("unused")
 401     public long timeGet(ArrayList<String> keys, Map<String, Integer> testmap, long comparisonTime, Style style, int ratioToMap) {
 402
 403         TrieMap<Integer> trieMap = TrieMap.Builder.with(style, Option.SMALL, testmap).build();
 404
 405         if (style == null) {
 406             Map<String, Integer> map = comparisonTime == 0 ? new TreeMap<String, Integer>(testmap) : new HashMap<String, Integer>(testmap);
 407
 408             long mapTime = t.timeIterations(new MyLoop() {
 409                 public void time(int repeat) {
 410                     for (int tt = 0; tt < repeat; ++tt) {
 411                         for (String key : keys) {
 412                             Integer foundValue = map.get(key);
 413                         }
 414                     }
 415                 }
 416             }, keys, map);
 417             if (comparisonTime == 0) {
 418                 logln("\tget() time\tTREEMAP\tn/a\t" + t.toString(keys.size()) + "\t\titerations=" + t.getIterations());
 419             } else {
 420                 logln("\tget() time\tHASHMAP\tn/a\t" + t.toString(keys.size(), comparisonTime) + "\titerations=" + t.getIterations());
 421             }
 422             return mapTime;
 423         } else {
 424             long trieTime = t.timeIterations(new MyLoop() {
 425                 public void time(int repeat) {
 426                     for (int tt = 0; tt < repeat; ++tt) {
 427                         for (String key : keys) {
 428                             Integer foundValue = trieMap.get(key);
 429                         }
 430                     }
 431                 }
 432             }, keys, trieMap);
 433
 434             //            System.gc();
 435             //            t.start();
 436             //            for (int tt = 0; tt < repeat; ++tt) {
 437             //                for (String key : keys) {
 438             //                    Integer foundValue = trieMap.get(key);
 439             //                }
 440             //            }
 441             //            long trieTime = t.getDuration();
 442             logln("\tget() time\t" + style + "\tn/a\t" + t.toString(keys.size(), comparisonTime) + "\titerations=" + t.getIterations());
 443             if (!useSmallList && trieTime > ratioToMap * comparisonTime) {
 444                 errln(style + "\tTime iteration takes too long. Expected:\t< " + ratioToMap * comparisonTime + ", Actual:\t" + trieTime);
 445             }
 446             return trieTime;
 447         }
 448     }
 449
 450     static abstract class MyLoop extends Timer.Loop {
 451         ArrayList<String> keys;
 452         TrieMap<Integer> trieMap;
 453         Map<String, Integer> map;
 454         Style style;
 455         Option option;
 456         public void init(Object... params) {
 457             if (params.length > 0) {
 458                 keys = (ArrayList<String>) params[0];
 459             }
 460             if (params.length > 1) {
 461                 if (params[1] instanceof Map) {
 462                     map = (Map<String, Integer>) params[1];
 463                 } else {
 464                     trieMap = (TrieMap<Integer>) params[1];
 465                 }
 466             }
 467             if (params.length > 2) {
 468                 style = (Style) params[2];
 469             }
 470             if (params.length > 3) {
 471                 option = (Option) params[3];
 472             }
 473         }
 474         abstract public void time(int repeat);
 475     }
 476
 477     //    static class Storage {
 478     //        char[] buffer;
 479     //        int limit;
 480     //
 481     //        public Storage(int initialCapacity) {
 482     //            buffer = new char[initialCapacity];
 483     //        }
 484     //
 485     //        public CharSequence add(CharSequence input) {
 486     //            int start = limit;
 487     //            int length = input.length();
 488     //            for (int i = 0; i < length; ++i) {
 489     //                try {
 490     //                    buffer[limit++] = input.charAt(i);
 491     //                } catch (Exception e) {
 492     //                    // we failed to add (limit-1)
 493     //                    int newCapacity = buffer.length * 3 / 2 + length;
 494     //                    //System.out.println(buffer.length + " => " + newCapacity);
 495     //                    char[] temp = new char[newCapacity];
 496     //                    System.arraycopy(buffer, 0, temp, 0, buffer.length);
 497     //                    buffer = temp;
 498     //                    buffer[limit - 1] = input.charAt(i);
 499     //                }
 500     //            }
 501     //            return new StorageCharSequence(start, limit);
 502     //        }
 503     //
 504     //        final class StorageCharSequence implements CharSequence, Comparable<CharSequence> {
 505     //            private int start;
 506     //            private int len;
 507     //
 508     //            public StorageCharSequence(int start, int limit) {
 509     //                if (start < 0 || start > limit || limit > buffer.length) {
 510     //                    throw new ArrayIndexOutOfBoundsException();
 511     //                }
 512     //                this.start = start;
 513     //                this.len = limit - start;
 514     //            }
 515     //            public char charAt(int arg0) {
 516     //                return arg0 < 0 || arg0 >= len ? buffer[-1] : buffer[arg0 + start];
 517     //            }
 518     //            public int length() {
 519     //                return len;
 520     //            }
 521     //            public CharSequence subSequence(int start, int limit) {
 522     //                return new StorageCharSequence(this.start + start, this.start + limit);
 523     //            }
 524     //            public String toString() {
 525     //                return String.valueOf(buffer, start, len);
 526     //            }
 527     //            public int hashCode() {
 528     //                int result = len;
 529     //                int limit = start + len;
 530     //                for (int i = start; i < limit; ++i) {
 531     //                    result *= 37;
 532     //                    result += i;
 533     //                }
 534     //                return result;
 535     //            }
 536     //            public boolean equals(Object other) {
 537     //                try {
 538     //                    StorageCharSequence that = (StorageCharSequence) other;
 539     //                    // can optimize
 540     //                    return CharSequences.equalsChars(this, that);
 541     //                } catch (Exception e) {
 542     //                    return false;
 543     //                }
 544     //            }
 545     //            public int compareTo(CharSequence other) {
 546     //                // can optimize
 547     //                return CharSequences.compare(this, other);
 548     //            }
 549     //        }
 550     //
 551     //    }
 552     //    public void TestStorage() {
 553     //        ArrayList<String> keys = new ArrayList<String>(unicodeTestMap.keySet());
 554     //        int repeat = REPEAT * 10;
 555     //        System.gc();
 556     //        t.start();
 557     //        for (int tt = 0; tt < repeat; ++tt) {
 558     //            Set<CharSequence> store = new HashSet<CharSequence>();
 559     //            // Storage storage = new Storage(1024);
 560     //            for (String key : keys) {
 561     //                store.add(key);
 562     //                //                CharSequence item = storage.add(key);
 563     //                //                if (!store.contains(item)) {
 564     //                //                    store.add(item);
 565     //                //                }
 566     //                //                if (!CharSequences.equalsChars(key, item)) {
 567     //                //                    throw new IllegalArgumentException(key);
 568     //                //                }
 569     //            }
 570     //            CharSequence[] raw = store.toArray(new CharSequence[store.size()]);
 571     //            Arrays.sort(raw);
 572     //        }
 573     //        long comparisonTime = t.getDuration();
 574     //        logln("\tget() time\tHashSet,sort\tn/a\t" + t.toString(repeat*keys.size()));
 575     //
 576     //        System.gc();
 577     //        t.start();
 578     //        for (int tt = 0; tt < repeat; ++tt) {
 579     //            Set<CharSequence> store = new TreeSet<CharSequence>();
 580     //            for (String key : keys) {
 581     //                store.add(key);
 582     //            }
 583     //            CharSequence[] raw = store.toArray(new CharSequence[store.size()]);
 584     //        }
 585     //        long trieTime = t.getDuration();
 586     //        logln("\tget() time\tTreeSet\tn/a\t" + t.toString(repeat*keys.size(), comparisonTime));
 587     //
 588     //    }
 589 }