You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hive.apache.org by tc...@apache.org on 2018/11/27 11:09:05 UTC

hive git commit: HIVE-20873: Use Murmur hash for VectorHashKeyWrapperTwoLong to reduce hash collision (Teddy Choi, reviewed by Gopal V)

Repository: hive
Updated Branches:
  refs/heads/master 7c5b99b5b -> dffa3a165


HIVE-20873: Use Murmur hash for VectorHashKeyWrapperTwoLong to reduce hash collision (Teddy Choi, reviewed by Gopal V)


Project: http://git-wip-us.apache.org/repos/asf/hive/repo
Commit: http://git-wip-us.apache.org/repos/asf/hive/commit/dffa3a16
Tree: http://git-wip-us.apache.org/repos/asf/hive/tree/dffa3a16
Diff: http://git-wip-us.apache.org/repos/asf/hive/diff/dffa3a16

Branch: refs/heads/master
Commit: dffa3a16588bc8e95b9d0ab5af295a74e06ef702
Parents: 7c5b99b
Author: Teddy Choi <pu...@gmail.com>
Authored: Tue Nov 27 20:08:04 2018 +0900
Committer: Teddy Choi <pu...@gmail.com>
Committed: Tue Nov 27 20:08:04 2018 +0900

----------------------------------------------------------------------
 .../apache/hive/common/util/HashCodeUtil.java   | 13 ++---
 .../wrapper/VectorHashKeyWrapperTwoLong.java    |  4 +-
 .../org/apache/hive/common/util/Murmur3.java    | 57 +++++++++++++++++---
 .../apache/hive/common/util/TestMurmur3.java    | 47 ++++++++++++++++
 4 files changed, 103 insertions(+), 18 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
----------------------------------------------------------------------
diff --git a/common/src/java/org/apache/hive/common/util/HashCodeUtil.java b/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
index 700b2e1..1330cbe 100644
--- a/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
+++ b/common/src/java/org/apache/hive/common/util/HashCodeUtil.java
@@ -33,15 +33,12 @@ public class HashCodeUtil {
     return key;
   }
 
+  public static int calculateTwoLongHashCode(long l0, long l1) {
+    return Murmur3.hash32(l0, l1);
+  }
+
   public static int calculateLongHashCode(long key) {
-    // Mixing down into the lower bits - this produces a worse hashcode in purely
-    // numeric terms, but leaving entropy in the higher bits is not useful for a
-    // 2^n bucketing scheme. See JSR166 ConcurrentHashMap r1.89 (released under Public Domain)
-    // Note: ConcurrentHashMap has since reverted this to retain entropy bits higher
-    // up, to support the 2-level hashing for segment which operates at a higher bitmask
-    key ^= (key >>> 7) ^ (key >>> 4);
-    key ^= (key >>> 20) ^ (key >>> 12);
-    return (int) key;
+    return Murmur3.hash32(key);
   }
 
   public static void calculateLongArrayHashCodes(long[] longs, int[] hashCodes, final int count) {

http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
----------------------------------------------------------------------
diff --git a/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java b/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
index 1652728..c40c35d 100644
--- a/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
+++ b/ql/src/java/org/apache/hadoop/hive/ql/exec/vector/wrapper/VectorHashKeyWrapperTwoLong.java
@@ -44,9 +44,7 @@ public class VectorHashKeyWrapperTwoLong extends VectorHashKeyWrapperTwoBase {
                 HashCodeUtil.calculateLongHashCode(longValue0) ^
                 null1Hashcode));
     } else {
-      hashcode =
-          HashCodeUtil.calculateLongHashCode(longValue0) >>> 16 ^
-          HashCodeUtil.calculateLongHashCode(longValue1);
+      hashcode = HashCodeUtil.calculateTwoLongHashCode(longValue0, longValue1);
     }
   }
 

http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
----------------------------------------------------------------------
diff --git a/storage-api/src/java/org/apache/hive/common/util/Murmur3.java b/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
index 8aae28b..85db95c 100644
--- a/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
+++ b/storage-api/src/java/org/apache/hive/common/util/Murmur3.java
@@ -54,6 +54,43 @@ public class Murmur3 {
 
   public static final int DEFAULT_SEED = 104729;
 
+  public static int hash32(long l0, long l1) {
+    return hash32(l0, l1, DEFAULT_SEED);
+  }
+
+  public static int hash32(long l0) {
+    return hash32(l0, DEFAULT_SEED);
+  }
+
+  /**
+   * Murmur3 32-bit variant.
+   */
+  public static int hash32(long l0, int seed) {
+    int hash = seed;
+    final long r0 = Long.reverseBytes(l0);
+
+    hash = mix32((int) r0, hash);
+    hash = mix32((int) (r0 >>> 32), hash);
+
+    return fmix32(Long.BYTES, hash);
+  }
+
+  /**
+   * Murmur3 32-bit variant.
+   */
+  public static int hash32(long l0, long l1, int seed) {
+    int hash = seed;
+    final long r0 = Long.reverseBytes(l0);
+    final long r1 = Long.reverseBytes(l1);
+
+    hash = mix32((int) r0, hash);
+    hash = mix32((int) (r0 >>> 32), hash);
+    hash = mix32((int) (r1), hash);
+    hash = mix32((int) (r1 >>> 32), hash);
+
+    return fmix32(Long.BYTES * 2, hash);
+  }
+
   /**
    * Murmur3 32-bit variant.
    *
@@ -108,12 +145,7 @@ public class Murmur3 {
           | ((data[offset + i_4 + 2] & 0xff) << 16)
           | ((data[offset + i_4 + 3] & 0xff) << 24);
 
-      // mix functions
-      k *= C1_32;
-      k = Integer.rotateLeft(k, R1_32);
-      k *= C2_32;
-      hash ^= k;
-      hash = Integer.rotateLeft(hash, R2_32) * M_32 + N_32;
+      hash = mix32(k, hash);
     }
 
     // tail
@@ -134,7 +166,18 @@ public class Murmur3 {
         hash ^= k1;
     }
 
-    // finalization
+    return fmix32(length, hash);
+  }
+
+  private static int mix32(int k, int hash) {
+    k *= C1_32;
+    k = Integer.rotateLeft(k, R1_32);
+    k *= C2_32;
+    hash ^= k;
+    return Integer.rotateLeft(hash, R2_32) * M_32 + N_32;
+  }
+
+  private static int fmix32(int length, int hash) {
     hash ^= length;
     hash ^= (hash >>> 16);
     hash *= 0x85ebca6b;

http://git-wip-us.apache.org/repos/asf/hive/blob/dffa3a16/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
----------------------------------------------------------------------
diff --git a/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java b/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
index 16955c1..7320d6d 100644
--- a/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
+++ b/storage-api/src/test/org/apache/hive/common/util/TestMurmur3.java
@@ -270,4 +270,51 @@ public class TestMurmur3 {
       assertEquals("Block size " + blockSize, expected, diff.end());
     }
   }
+
+  @Test
+  public void testTwoLongOrdered() {
+    ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES * 2);
+    for (long i = 0; i < 1000; i++) {
+      for (long j = 0; j < 1000; j++) {
+        buffer.putLong(0, i);
+        buffer.putLong(Long.BYTES, j);
+        assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(i, j));
+      }
+    }
+  }
+
+  @Test
+  public void testTwoLongRandom() {
+    ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES * 2);
+    Random random = new Random();
+    for (long i = 0; i < 1000; i++) {
+      for (long j = 0; j < 1000; j++) {
+        long x = random.nextLong();
+        long y = random.nextLong();
+        buffer.putLong(0, x);
+        buffer.putLong(Long.BYTES, y);
+        assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(x, y));
+      }
+    }
+  }
+
+  @Test
+  public void testSingleLongOrdered() {
+    ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
+    for (long i = 0; i < 1000; i++) {
+      buffer.putLong(0, i);
+      assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(i));
+    }
+  }
+
+  @Test
+  public void testSingleLongRandom() {
+    ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
+    Random random = new Random();
+    for (long i = 0; i < 1000; i++) {
+      long x = random.nextLong();
+      buffer.putLong(0, x);
+      assertEquals(Murmur3.hash32(buffer.array()), Murmur3.hash32(x));
+    }
+  }
 }