Created
September 2, 2015 13:24
-
-
Save apangin/5912c4d90f875c3b1c05 to your computer and use it in GitHub Desktop.
Compare xxHash with default String.hashCode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
java version "1.8.0_60" | |
Java(TM) SE Runtime Environment (build 1.8.0_60-b27) | |
Java HotSpot(TM) 64-Bit Server VM (build 25.60-b23, mixed mode) | |
Benchmark (length) Mode Cnt Score Error Units | |
StringHash.defaultHashCode 10 thrpt 5 93402,407 ± 1890,337 ops/ms | |
StringHash.defaultHashCode 100 thrpt 5 8932,744 ± 336,015 ops/ms | |
StringHash.defaultHashCode 1000 thrpt 5 886,429 ± 8,678 ops/ms | |
StringHash.defaultHashCode 10000 thrpt 5 89,057 ± 1,649 ops/ms | |
StringHash.xxhash 10 thrpt 5 55170,485 ± 2236,430 ops/ms | |
StringHash.xxhash 100 thrpt 5 12645,358 ± 256,102 ops/ms | |
StringHash.xxhash 1000 thrpt 5 1715,421 ± 35,312 ops/ms | |
StringHash.xxhash 10000 thrpt 5 179,315 ± 2,533 ops/ms | |
StringHash.xxhash_unsafe 10 thrpt 5 56964,408 ± 2102,881 ops/ms | |
StringHash.xxhash_unsafe 100 thrpt 5 19359,824 ± 633,949 ops/ms | |
StringHash.xxhash_unsafe 1000 thrpt 5 2677,863 ± 113,022 ops/ms | |
StringHash.xxhash_unsafe 10000 thrpt 5 280,267 ± 8,873 ops/ms |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package bench; | |
import org.openjdk.jmh.annotations.Benchmark; | |
import org.openjdk.jmh.annotations.Param; | |
import org.openjdk.jmh.annotations.Scope; | |
import org.openjdk.jmh.annotations.Setup; | |
import org.openjdk.jmh.annotations.State; | |
import sun.misc.Unsafe; | |
import java.lang.reflect.Field; | |
import java.util.Random; | |
@State(Scope.Benchmark) | |
public class StringHash { | |
@Param({"10", "100", "1000", "10000"}) | |
int length; | |
char[] chars; | |
String str; | |
@Setup | |
public void setup() { | |
Random random = new Random(0); | |
chars = new char[length]; | |
for (int i = 0; i < chars.length; i++) { | |
chars[i] = (char) random.nextInt(65536); | |
} | |
str = new String(chars); | |
} | |
@Benchmark | |
public int defaultHashCode() { | |
int hash = 0; | |
for (char c : chars) { | |
hash = 31 * hash + c; | |
} | |
return hash; | |
} | |
private static final int P1 = 0x9e3779b1; | |
private static final int P2 = 0x85ebca77; | |
private static final int P3 = 0xc2b2ae3d; | |
private static final int P4 = 0x27d4eb2f; | |
private static final int P5 = 0x165667b1; | |
@Benchmark | |
public int xxhash() { | |
String s = str; | |
int h32; | |
int offset = 0; | |
int length = s.length(); | |
if (length >= 8) { | |
int limit = length - 8; | |
int v1 = P1 + P2; | |
int v2 = P2; | |
int v3 = 0; | |
int v4 = -P1; | |
do { | |
v1 += (s.charAt(offset) | s.charAt(offset + 1) << 16) * P2; | |
v1 = ((v1 << 13) | (v1 >>> 19)) * P1; | |
v2 += (s.charAt(offset + 2) | s.charAt(offset + 3) << 16) * P2; | |
v2 = ((v2 << 13) | (v2 >>> 19)) * P1; | |
v3 += (s.charAt(offset + 4) | s.charAt(offset + 5) << 16) * P2; | |
v3 = ((v3 << 13) | (v3 >>> 19)) * P1; | |
v4 += (s.charAt(offset + 6) | s.charAt(offset + 7) << 16) * P2; | |
v4 = ((v4 << 13) | (v4 >>> 19)) * P1; | |
} while ((offset += 8) <= limit); | |
h32 = ((v1 << 1) | (v1 >>> 31)) + ((v2 << 7) | (v2 >>> 25)) + ((v3 << 12) | (v3 >>> 20)) + ((v4 << 18) | (v4 >>> 14)); | |
} else { | |
h32 = P5; | |
} | |
h32 += length * 2; | |
for (; offset + 2 <= length; offset += 2) { | |
h32 += (s.charAt(offset) | s.charAt(offset + 1) << 16) * P3; | |
h32 = ((h32 << 17) | (h32 >>> 15)) * P4; | |
} | |
if (offset < length) { | |
char last = s.charAt(offset); | |
h32 += (last & 0xff) * P5; | |
h32 = ((h32 << 11) | (h32 >>> 21)) * P1; | |
h32 += (last >>> 8) * P5; | |
h32 = ((h32 << 11) | (h32 >>> 21)) * P1; | |
} | |
h32 ^= h32 >>> 15; | |
h32 *= P2; | |
h32 ^= h32 >>> 13; | |
h32 *= P3; | |
h32 ^= h32 >>> 16; | |
return h32; | |
} | |
@Benchmark | |
public int xxhash_unsafe() throws IllegalAccessException { | |
return xxhash_helper(stringValue.get(str), charArrayOffset, str.length() * 2); | |
} | |
private static int xxhash_helper(Object obj, long offset, int length) { | |
int h32; | |
long end = offset + length; | |
if (length >= 16) { | |
long limit = end - 16; | |
int v1 = P1 + P2; | |
int v2 = P2; | |
int v3 = 0; | |
int v4 = -P1; | |
do { | |
v1 += unsafe.getInt(obj, offset) * P2; | |
v1 = ((v1 << 13) | (v1 >>> 19)) * P1; | |
v2 += unsafe.getInt(obj, offset + 4) * P2; | |
v2 = ((v2 << 13) | (v2 >>> 19)) * P1; | |
v3 += unsafe.getInt(obj, offset + 8) * P2; | |
v3 = ((v3 << 13) | (v3 >>> 19)) * P1; | |
v4 += unsafe.getInt(obj, offset + 12) * P2; | |
v4 = ((v4 << 13) | (v4 >>> 19)) * P1; | |
} while ((offset += 16) <= limit); | |
h32 = ((v1 << 1) | (v1 >>> 31)) + ((v2 << 7) | (v2 >>> 25)) + ((v3 << 12) | (v3 >>> 20)) + ((v4 << 18) | (v4 >>> 14)); | |
} else { | |
h32 = P5; | |
} | |
h32 += length; | |
for (; offset + 4 <= end; offset += 4) { | |
h32 += unsafe.getInt(obj, offset) * P3; | |
h32 = ((h32 << 17) | (h32 >>> 15)) * P4; | |
} | |
for (; offset < end; offset++) { | |
h32 += (unsafe.getByte(obj, offset) & 0xff) * P5; | |
h32 = ((h32 << 11) | (h32 >>> 21)) * P1; | |
} | |
h32 ^= h32 >>> 15; | |
h32 *= P2; | |
h32 ^= h32 >>> 13; | |
h32 *= P3; | |
h32 ^= h32 >>> 16; | |
return h32; | |
} | |
private static final Unsafe unsafe; | |
private static final long charArrayOffset; | |
private static final Field stringValue; | |
static { | |
try { | |
Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe"); | |
theUnsafe.setAccessible(true); | |
unsafe = (Unsafe) theUnsafe.get(null); | |
charArrayOffset = unsafe.arrayBaseOffset(char[].class); | |
stringValue = String.class.getDeclaredField("value"); | |
stringValue.setAccessible(true); | |
} catch (Exception e) { | |
throw new AssertionError("Cannot use private API"); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment