1 /* 2 * Copyright (C) 2010 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import static com.google.common.base.Preconditions.checkNotNull; 20 21 import com.google.common.primitives.Ints; 22 import java.util.Collections; 23 import java.util.List; 24 import java.util.Set; 25 import org.checkerframework.checker.nullness.qual.Nullable; 26 27 /** 28 * Package up sample data for common collections benchmarking. 29 * 30 * @author Nicholaus Shupe 31 */ 32 class CollectionBenchmarkSampleData { 33 private final boolean isUserTypeFast; 34 private final SpecialRandom random; 35 private final double hitRate; 36 private final int size; 37 38 private final Set<Element> valuesInSet; 39 private final Element[] queries; 40 CollectionBenchmarkSampleData(int size)41 CollectionBenchmarkSampleData(int size) { 42 this(true, new SpecialRandom(), 1.0, size); 43 } 44 CollectionBenchmarkSampleData( boolean isUserTypeFast, SpecialRandom random, double hitRate, int size)45 CollectionBenchmarkSampleData( 46 boolean isUserTypeFast, SpecialRandom random, double hitRate, int size) { 47 this.isUserTypeFast = isUserTypeFast; 48 this.random = checkNotNull(random); 49 this.hitRate = hitRate; 50 this.size = size; 51 52 this.valuesInSet = createData(); 53 this.queries = createQueries(valuesInSet, 1024); 54 } 55 getValuesInSet()56 Set<Element> getValuesInSet() { 57 return valuesInSet; 58 } 59 getQueries()60 Element[] getQueries() { 61 return queries; 62 } 63 createQueries(Set<Element> elementsInSet, int numQueries)64 private Element[] createQueries(Set<Element> elementsInSet, int numQueries) { 65 List<Element> queryList = Lists.newArrayListWithCapacity(numQueries); 66 67 int numGoodQueries = (int) (numQueries * hitRate + 0.5); 68 69 // add good queries 70 int size = elementsInSet.size(); 71 if (size > 0) { 72 int minCopiesOfEachGoodQuery = numGoodQueries / size; 73 int extras = numGoodQueries % size; 74 75 for (int i = 0; i < minCopiesOfEachGoodQuery; i++) { 76 queryList.addAll(elementsInSet); 77 } 78 List<Element> tmp = Lists.newArrayList(elementsInSet); 79 Collections.shuffle(tmp, random); 80 queryList.addAll(tmp.subList(0, extras)); 81 } 82 83 // now add bad queries 84 while (queryList.size() < numQueries) { 85 Element candidate = newElement(); 86 if (!elementsInSet.contains(candidate)) { 87 queryList.add(candidate); 88 } 89 } 90 Collections.shuffle(queryList, random); 91 return queryList.toArray(new Element[0]); 92 } 93 createData()94 private Set<Element> createData() { 95 Set<Element> set = Sets.newHashSetWithExpectedSize(size); 96 while (set.size() < size) { 97 set.add(newElement()); 98 } 99 return set; 100 } 101 newElement()102 private Element newElement() { 103 int value = random.nextInt(); 104 return isUserTypeFast ? new Element(value) : new SlowElement(value); 105 } 106 107 static class Element implements Comparable<Element> { 108 final int hash; 109 Element(int hash)110 Element(int hash) { 111 this.hash = hash; 112 } 113 114 @Override equals(@ullable Object obj)115 public boolean equals(@Nullable Object obj) { 116 return this == obj || (obj instanceof Element && ((Element) obj).hash == hash); 117 } 118 119 @Override hashCode()120 public int hashCode() { 121 return hash; 122 } 123 124 @Override compareTo(Element that)125 public int compareTo(Element that) { 126 return Ints.compare(hash, that.hash); 127 } 128 129 @Override toString()130 public String toString() { 131 return String.valueOf(hash); 132 } 133 } 134 135 static class SlowElement extends Element { SlowElement(int hash)136 SlowElement(int hash) { 137 super(hash); 138 } 139 140 @Override equals(@ullable Object obj)141 public boolean equals(@Nullable Object obj) { 142 return slowItDown() != 1 && super.equals(obj); 143 } 144 145 @Override hashCode()146 public int hashCode() { 147 return slowItDown() + hash; 148 } 149 150 @Override compareTo(Element e)151 public int compareTo(Element e) { 152 int x = slowItDown(); 153 return x + super.compareTo(e) - x; // silly attempt to prevent opt 154 } 155 slowItDown()156 static int slowItDown() { 157 int result = 0; 158 for (int i = 1; i <= 1000; i++) { 159 result += i; 160 } 161 return result; 162 } 163 } 164 } 165