| /* |
| * Copyright (C) 2019 The Guava Authors |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package com.google.common.collect; |
| |
| import com.google.caliper.BeforeExperiment; |
| import com.google.caliper.Benchmark; |
| import com.google.caliper.Param; |
| import com.google.common.math.IntMath; |
| import java.math.RoundingMode; |
| |
| /** Benchmark of implementations of {@link ImmutableSet#hashFloodingDetected(Object[])}. */ |
| public class ImmutableSetHashFloodingDetectionBenchmark { |
| private static final int TEST_CASES = 0x100; |
| |
| @Param({"10", "100", "1000", "10000"}) |
| int size; |
| |
| @Param Impl impl; |
| |
| private static final Object[][] tables = new Object[TEST_CASES][]; |
| |
| @BeforeExperiment |
| public void setUp() { |
| int tableSize = ImmutableSet.chooseTableSize(size); |
| int mask = tableSize - 1; |
| for (int i = 0; i < TEST_CASES; i++) { |
| tables[i] = new Object[tableSize]; |
| for (int j = 0; j < size; j++) { |
| Object o = new Object(); |
| for (int k = o.hashCode(); ; k++) { |
| int index = k & mask; |
| if (tables[i][index] == null) { |
| tables[i][index] = o; |
| break; |
| } |
| } |
| } |
| } |
| } |
| |
| enum Impl { |
| EXHAUSTIVE { |
| int maxRunBeforeFallback(int tableSize) { |
| return 12 * IntMath.log2(tableSize, RoundingMode.UNNECESSARY); |
| } |
| |
| @Override |
| boolean hashFloodingDetected(Object[] hashTable) { |
| int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length); |
| |
| // Test for a run wrapping around the end of the table, then check for runs in the middle. |
| int endOfStartRun; |
| for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) { |
| if (hashTable[endOfStartRun] == null) { |
| break; |
| } |
| endOfStartRun++; |
| if (endOfStartRun > maxRunBeforeFallback) { |
| return true; |
| } |
| } |
| int startOfEndRun; |
| for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) { |
| if (hashTable[startOfEndRun] == null) { |
| break; |
| } |
| if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) { |
| return true; |
| } |
| } |
| for (int i = endOfStartRun + 1; i < startOfEndRun; i++) { |
| for (int runLength = 0; i < startOfEndRun && hashTable[i] != null; i++) { |
| runLength++; |
| if (runLength > maxRunBeforeFallback) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| }, |
| SEPARATE_RANGES { |
| int maxRunBeforeFallback(int tableSize) { |
| return 13 * IntMath.log2(tableSize, RoundingMode.UNNECESSARY); |
| } |
| |
| @Override |
| boolean hashFloodingDetected(Object[] hashTable) { |
| int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length); |
| |
| // Test for a run wrapping around the end of the table, then check for runs in the middle. |
| int endOfStartRun; |
| for (endOfStartRun = 0; endOfStartRun < hashTable.length; ) { |
| if (hashTable[endOfStartRun] == null) { |
| break; |
| } |
| endOfStartRun++; |
| if (endOfStartRun > maxRunBeforeFallback) { |
| return true; |
| } |
| } |
| int startOfEndRun; |
| for (startOfEndRun = hashTable.length - 1; startOfEndRun > endOfStartRun; startOfEndRun--) { |
| if (hashTable[startOfEndRun] == null) { |
| break; |
| } |
| if (endOfStartRun + (hashTable.length - 1 - startOfEndRun) > maxRunBeforeFallback) { |
| return true; |
| } |
| } |
| |
| // If this part returns true, there is definitely a run of size maxRunBeforeFallback/2. |
| // If this part returns false, there are definitely no runs of size >= maxRunBeforeFallback. |
| int testBlockSize = maxRunBeforeFallback / 2; |
| for (int i = endOfStartRun + 1; i + testBlockSize <= startOfEndRun; i += testBlockSize) { |
| boolean runGood = false; |
| for (int j = 0; j < testBlockSize; j++) { |
| if (hashTable[i + j] == null) { |
| runGood = true; |
| break; |
| } |
| } |
| if (!runGood) { |
| return true; |
| } |
| } |
| return false; |
| } |
| }; |
| |
| abstract boolean hashFloodingDetected(Object[] array); |
| } |
| |
| @Benchmark |
| public int detect(int reps) { |
| int count = 0; |
| for (int i = 0; i < reps; i++) { |
| if (impl.hashFloodingDetected(tables[i & 0xFF])) { |
| count++; |
| } |
| } |
| return count; |
| } |
| } |