1 /* 2 * Copyright (C) 2015 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.hash; 18 19 import com.google.caliper.BeforeExperiment; 20 import com.google.caliper.Benchmark; 21 import com.google.caliper.Param; 22 import java.security.MessageDigest; 23 import java.util.Arrays; 24 import java.util.Random; 25 26 /** 27 * Benchmarks for comparing the various {@link HashCode#equals} methods. 28 * 29 * <p>Parameters for the benchmark are: 30 * 31 * <ul> 32 * <li>size: the length of the byte array to hash 33 * <li>whereToDiffer: where in the array the bytes should differ 34 * <li>equalsImpl: which implementation of array equality to use 35 * </ul> 36 * 37 * <p><b>Important note:</b> the primary goal of this benchmark is to ensure that varying {@code 38 * whereToDiffer} produces no observable change in performance. We want to make sure that the array 39 * equals implementation is *not* short-circuiting to prevent timing-based attacks. Being fast is 40 * only a secondary goal. 41 * 42 * @author Kurt Alfred Kluever 43 */ 44 public class HashCodeBenchmark { 45 46 // Use a statically configured random instance for all of the benchmarks 47 private static final Random random = new Random(42); 48 49 @Param({"1000", "100000"}) 50 private int size; 51 52 @Param WhereToDiffer whereToDiffer; 53 54 @Param EqualsImplementation equalsImpl; 55 56 private enum WhereToDiffer { 57 ONE_PERCENT_IN, 58 LAST_BYTE, 59 NOT_AT_ALL; 60 } 61 62 private enum EqualsImplementation { 63 ANDING_BOOLEANS { 64 @Override doEquals(byte[] a, byte[] b)65 boolean doEquals(byte[] a, byte[] b) { 66 if (a.length != b.length) { 67 return false; 68 } 69 boolean areEqual = true; 70 for (int i = 0; i < a.length; i++) { 71 areEqual &= (a[i] == b[i]); 72 } 73 return areEqual; 74 } 75 }, 76 XORING_TO_BYTE { 77 @Override doEquals(byte[] a, byte[] b)78 boolean doEquals(byte[] a, byte[] b) { 79 if (a.length != b.length) { 80 return false; 81 } 82 byte result = 0; 83 for (int i = 0; i < a.length; i++) { 84 result = (byte) (result | a[i] ^ b[i]); 85 } 86 return (result == 0); 87 } 88 }, 89 XORING_TO_INT { 90 @Override doEquals(byte[] a, byte[] b)91 boolean doEquals(byte[] a, byte[] b) { 92 if (a.length != b.length) { 93 return false; 94 } 95 int result = 0; 96 for (int i = 0; i < a.length; i++) { 97 result |= a[i] ^ b[i]; 98 } 99 return (result == 0); 100 } 101 }, 102 MESSAGE_DIGEST_IS_EQUAL { 103 @Override doEquals(byte[] a, byte[] b)104 boolean doEquals(byte[] a, byte[] b) { 105 return MessageDigest.isEqual(a, b); 106 } 107 }, 108 ARRAYS_EQUALS { 109 @Override doEquals(byte[] a, byte[] b)110 boolean doEquals(byte[] a, byte[] b) { 111 return Arrays.equals(a, b); 112 } 113 }; 114 doEquals(byte[] a, byte[] b)115 abstract boolean doEquals(byte[] a, byte[] b); 116 } 117 118 private byte[] testBytesA; 119 private byte[] testBytesB; 120 121 @BeforeExperiment setUp()122 void setUp() { 123 testBytesA = new byte[size]; 124 random.nextBytes(testBytesA); 125 testBytesB = Arrays.copyOf(testBytesA, size); 126 int indexToDifferAt = -1; 127 switch (whereToDiffer) { 128 case ONE_PERCENT_IN: 129 indexToDifferAt = (int) (size * 0.01); 130 break; 131 case LAST_BYTE: 132 indexToDifferAt = size - 1; 133 break; 134 case NOT_AT_ALL: 135 } 136 if (indexToDifferAt != -1) { 137 testBytesA[indexToDifferAt] = (byte) (testBytesB[indexToDifferAt] - 1); 138 } 139 } 140 141 @Benchmark hashFunction(int reps)142 boolean hashFunction(int reps) { 143 boolean result = true; 144 for (int i = 0; i < reps; i++) { 145 result ^= equalsImpl.doEquals(testBytesA, testBytesB); 146 } 147 return result; 148 } 149 } 150