13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 25 package org.graalvm.compiler.lir.hashing; 26 27 import java.util.Comparator; 28 import java.util.HashSet; 29 import java.util.Optional; 30 import java.util.Set; 31 import java.util.TreeSet; 32 33 import org.graalvm.compiler.lir.gen.ArithmeticLIRGenerator; 34 35 import jdk.vm.ci.meta.JavaConstant; 36 import jdk.vm.ci.meta.Value; 37 38 /** 39 * This class holds a hash function at a specific cardinality and min value (lowest key). The 40 * cardinality is the required size of the hash table to make the hasher injective for the provided 41 * keys. 42 */ 43 public final class Hasher { 44 45 /** 46 * Tries to find a hash function without conflicts for the provided keys. 47 * 48 * @param keys the keys 49 * @param minDensity the minimum density of the switch table. Used to determine the maximum 50 * cardinality of the hash function 51 * @return an optional hasher 52 */ 53 public static Optional<Hasher> forKeys(JavaConstant[] keys, double minDensity) { 54 if (keys.length <= 2) { 55 return Optional.empty(); 56 } else { 57 int maxCardinality = (int) Math.round(keys.length / minDensity); 58 assertSorted(keys); 59 TreeSet<Hasher> candidates = new TreeSet<>(new Comparator<Hasher>() { 60 @Override 61 public int compare(Hasher o1, Hasher o2) { 62 int d = o1.cardinality - o2.cardinality; 63 if (d != 0) { 64 return d; 65 } else { 66 return o1.effort() - o2.effort(); 67 } 68 } 69 }); 70 long min = keys[0].asLong(); 71 for (HashFunction f : HashFunction.instances()) { 72 for (int cardinality = keys.length; cardinality < maxCardinality; cardinality++) { 73 if (isValid(keys, min, f, cardinality)) { 74 candidates.add(new Hasher(f, cardinality, min)); 75 break; 76 } 77 } 78 } 79 if (candidates.isEmpty()) { 80 return Optional.empty(); 81 } else { 82 return Optional.of(candidates.first()); 83 } 84 } 85 } 86 87 private static void assertSorted(JavaConstant[] keys) { 88 for (int i = 1; i < keys.length; i++) { 89 assert keys[i - 1].asLong() < keys[i].asLong(); 90 } 91 } 92 93 private static boolean isValid(JavaConstant[] keys, long min, HashFunction function, int cardinality) { 94 Set<Integer> seen = new HashSet<>(keys.length); 95 for (JavaConstant key : keys) { 96 int hash = function.apply(key.asLong(), min) & (cardinality - 1); 97 if (!seen.add(hash)) { 98 return false; 99 } 100 } 101 return true; 102 } 103 104 private final HashFunction function; 105 private final int cardinality; 106 private final long min; 107 108 private Hasher(HashFunction function, int cardinality, long min) { 109 this.function = function; 110 this.cardinality = cardinality; 111 this.min = min; 112 } 113 114 /** 115 * Applies the hash function. 116 * 117 * @param value the value to be hashed 118 * @return the hash value 119 */ 120 public int hash(long value) { 121 return function.apply(value, min) & (cardinality - 1); 122 } 123 124 /** 125 * Applies the hash function to a lir value. 126 * 127 * @param value the value to be hashed 128 * @param gen the lir generator 129 * @return the hashed lir value 130 */ 131 public Value hash(Value value, ArithmeticLIRGenerator gen) { 132 Value h = function.gen(value, gen.getLIRGen().emitJavaConstant(JavaConstant.forLong(min)), gen); 133 return gen.emitAnd(h, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(cardinality - 1))); 134 } 135 136 /** 137 * @return the hashing effort 138 */ 139 public int effort() { 140 return function.effort() + 1; 141 } 142 143 /** 144 * @return the cardinality of the hash function that should match the size of the table switch. 145 */ 146 public int cardinality() { 147 return cardinality; 148 } 149 150 /** 151 * @return the hash function 152 */ | 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 25 package org.graalvm.compiler.lir.hashing; 26 27 import java.util.Comparator; 28 import java.util.HashSet; 29 import java.util.Optional; 30 import java.util.Set; 31 import java.util.TreeSet; 32 33 import jdk.vm.ci.meta.JavaKind; 34 import org.graalvm.compiler.lir.gen.ArithmeticLIRGenerator; 35 36 import jdk.vm.ci.meta.JavaConstant; 37 import jdk.vm.ci.meta.Value; 38 39 /** 40 * This class holds a hash function at a specific cardinality and min value (lowest key). The 41 * cardinality is the required size of the hash table to make the hasher injective for the provided 42 * keys. 43 */ 44 public final class Hasher { 45 46 /** 47 * Tries to find a hash function without conflicts for the provided keys. 48 * 49 * @param keys the keys 50 * @param minDensity the minimum density of the switch table. Used to determine the maximum 51 * cardinality of the hash function 52 * @return an optional hasher 53 */ 54 public static Optional<Hasher> forKeys(JavaConstant[] keys, double minDensity) { 55 assert checkKeyKind(keys); 56 if (keys.length <= 2) { 57 return Optional.empty(); 58 } else { 59 int maxCardinality = (int) Math.round(keys.length / minDensity); 60 assert checkIfSorted(keys); 61 TreeSet<Hasher> candidates = new TreeSet<>(new Comparator<Hasher>() { 62 @Override 63 public int compare(Hasher o1, Hasher o2) { 64 int d = o1.cardinality - o2.cardinality; 65 if (d != 0) { 66 return d; 67 } else { 68 return o1.effort() - o2.effort(); 69 } 70 } 71 }); 72 int min = keys[0].asInt(); 73 for (HashFunction f : HashFunction.instances()) { 74 for (int cardinality = keys.length; cardinality < maxCardinality; cardinality++) { 75 if (isValid(keys, min, f, cardinality)) { 76 candidates.add(new Hasher(f, cardinality, min)); 77 break; 78 } 79 } 80 } 81 if (candidates.isEmpty()) { 82 return Optional.empty(); 83 } else { 84 return Optional.of(candidates.first()); 85 } 86 } 87 } 88 89 private static boolean checkKeyKind(JavaConstant[] keys) { 90 for (int i = 0; i < keys.length; i++) { 91 if (keys[i].getJavaKind() != JavaKind.Int) { 92 throw new AssertionError(String.format("Key at index %d is not an int: %s", i, keys[i])); 93 } 94 } 95 return true; 96 } 97 98 private static boolean checkIfSorted(JavaConstant[] keys) { 99 for (int i = 1; i < keys.length; i++) { 100 if (keys[i - 1].asInt() >= keys[i].asInt()) { 101 throw new AssertionError("Keys array is not sorted"); 102 } 103 } 104 return true; 105 } 106 107 private static boolean isValid(JavaConstant[] keys, int min, HashFunction function, int cardinality) { 108 Set<Integer> seen = new HashSet<>(keys.length); 109 for (JavaConstant key : keys) { 110 int hash = function.apply(key.asInt(), min) & (cardinality - 1); 111 if (!seen.add(hash)) { 112 return false; 113 } 114 } 115 return true; 116 } 117 118 private final HashFunction function; 119 private final int cardinality; 120 private final int min; 121 122 private Hasher(HashFunction function, int cardinality, int min) { 123 this.function = function; 124 this.cardinality = cardinality; 125 this.min = min; 126 } 127 128 /** 129 * Applies the hash function. 130 * 131 * @param value the value to be hashed 132 * @return the hash value 133 */ 134 public int hash(int value) { 135 return function.apply(value, min) & (cardinality - 1); 136 } 137 138 /** 139 * Applies the hash function to a lir value. 140 * 141 * @param value the value to be hashed 142 * @param gen the lir generator 143 * @return the hashed lir value 144 */ 145 public Value hash(Value value, ArithmeticLIRGenerator gen) { 146 Value h = function.gen(value, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(min)), gen); 147 return gen.emitAnd(h, gen.getLIRGen().emitJavaConstant(JavaConstant.forInt(cardinality - 1))); 148 } 149 150 /** 151 * @return the hashing effort 152 */ 153 public int effort() { 154 return function.effort() + 1; 155 } 156 157 /** 158 * @return the cardinality of the hash function that should match the size of the table switch. 159 */ 160 public int cardinality() { 161 return cardinality; 162 } 163 164 /** 165 * @return the hash function 166 */ |