You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@systemml.apache.org by mb...@apache.org on 2016/10/01 19:57:03 UTC
[2/4] incubator-systemml git commit: [SYSTEMML-993] Improved
long-long hash function for matrix indexes
[SYSTEMML-993] Improved long-long hash function for matrix indexes
The existing long-long hash function of matrices indexes shows poor
performance with regard to key distributions for wide matrices. This
patch changes the used hash function to a common hash function as used
in Arrays.hashCode(long[]) but without the need of array allocation or
copy. For a detailed comparison see
https://issues.apache.org/jira/browse/SYSTEMML-993. Note that this
change affects all shuffle-based operations and operations over shuffled
data (e.g., after text/csv to matrix reblocks) as well as both our
MapReduce and Spark backends.
Project: http://git-wip-us.apache.org/repos/asf/incubator-systemml/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-systemml/commit/1d047989
Tree: http://git-wip-us.apache.org/repos/asf/incubator-systemml/tree/1d047989
Diff: http://git-wip-us.apache.org/repos/asf/incubator-systemml/diff/1d047989
Branch: refs/heads/master
Commit: 1d047989cd4a66f6ef9df8eb896bece939d85958
Parents: 98c212b
Author: Matthias Boehm <mb...@us.ibm.com>
Authored: Fri Sep 30 16:59:48 2016 -0700
Committer: Matthias Boehm <mb...@us.ibm.com>
Committed: Sat Oct 1 00:37:49 2016 -0700
----------------------------------------------------------------------
.../runtime/matrix/data/MatrixIndexes.java | 8 +-----
.../sysml/runtime/matrix/data/MatrixValue.java | 2 +-
.../matrix/data/TaggedFirstSecondIndexes.java | 4 +--
.../matrix/data/TaggedTripleIndexes.java | 16 ++++--------
.../runtime/matrix/data/TripleIndexes.java | 12 +++------
.../runtime/util/LongLongDoubleHashMap.java | 4 +--
.../sysml/runtime/util/UtilFunctions.java | 27 +++++++++++++++++++-
7 files changed, 40 insertions(+), 33 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixIndexes.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixIndexes.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixIndexes.java
index 3176a4c..8f66800 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixIndexes.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixIndexes.java
@@ -40,12 +40,6 @@ import org.apache.sysml.runtime.util.UtilFunctions;
public class MatrixIndexes implements WritableComparable<MatrixIndexes>, RawComparator<MatrixIndexes>, Externalizable
{
private static final long serialVersionUID = -1521166657518127789L;
-
- public static final int BYTE_SIZE = (Long.SIZE+Long.SIZE)/8;
- public static final long ADD_PRIME1 = 99991;
- public static final long ADD_PRIME2 = 853;
- //prime close to max int, because it determines the max hash domain size
- public static final int DIVIDE_PRIME = 1405695061;
private long _row = -1;
private long _col = -1;
@@ -106,7 +100,7 @@ public class MatrixIndexes implements WritableComparable<MatrixIndexes>, RawComp
@Override
public int hashCode() {
- return UtilFunctions.longHashFunc((_row<<32)+_col+ADD_PRIME1)%DIVIDE_PRIME;
+ return UtilFunctions.longlongHashCode(_row, _col);
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java
index ae63b6d..bb95af2 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/MatrixValue.java
@@ -62,7 +62,7 @@ public abstract class MatrixValue implements WritableComparable
}
public int hashCode() {
- return UtilFunctions.longHashFunc((row << 16) + column);
+ return UtilFunctions.longHashCode((row << 16) + column);
}
public void set(int r, int c) {
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedFirstSecondIndexes.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedFirstSecondIndexes.java b/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedFirstSecondIndexes.java
index 8efadb5..14d35b4 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedFirstSecondIndexes.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedFirstSecondIndexes.java
@@ -126,7 +126,7 @@ public class TaggedFirstSecondIndexes implements WritableComparable<TaggedFirstS
@Override
public int hashCode() {
- return UtilFunctions.longHashFunc((first<<32)+second+tag+MatrixIndexes.ADD_PRIME1)%MatrixIndexes.DIVIDE_PRIME;
+ return UtilFunctions.longHashCode((first<<32)+second+tag+UtilFunctions.ADD_PRIME1)%UtilFunctions.DIVIDE_PRIME;
}
/** A Comparator optimized for TaggedFirstSecondIndexes. */
@@ -153,7 +153,7 @@ public class TaggedFirstSecondIndexes implements WritableComparable<TaggedFirstS
@Override
public int getPartition(TaggedFirstSecondIndexes key, Writable value, int numPartitions)
{
- return UtilFunctions.longHashFunc(key.getFirstIndex()*127)%10007%numPartitions;
+ return UtilFunctions.longHashCode(key.getFirstIndex()*127)%10007%numPartitions;
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedTripleIndexes.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedTripleIndexes.java b/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedTripleIndexes.java
index a7fd800..071c622 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedTripleIndexes.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/TaggedTripleIndexes.java
@@ -112,7 +112,7 @@ public class TaggedTripleIndexes extends TaggedFirstSecondIndexes
@Override
public int hashCode() {
- return UtilFunctions.longHashFunc((first<<32)+(second<<16)+third+tag+MatrixIndexes.ADD_PRIME1)%MatrixIndexes.DIVIDE_PRIME;
+ return UtilFunctions.longHashCode((first<<32)+(second<<16)+third+tag+UtilFunctions.ADD_PRIME1)%UtilFunctions.DIVIDE_PRIME;
}
public static class Comparator implements RawComparator<TaggedTripleIndexes>
@@ -135,16 +135,10 @@ public class TaggedTripleIndexes extends TaggedFirstSecondIndexes
*/
public static class FirstTwoIndexesPartitioner implements Partitioner<TaggedTripleIndexes, MatrixBlock>{
@Override
- public int getPartition(TaggedTripleIndexes key, MatrixBlock value,
- int numPartitions) {
-
- return UtilFunctions.longHashFunc((key.getFirstIndex()*127)
- +key.getSecondIndex()+MatrixIndexes.ADD_PRIME1)
- %MatrixIndexes.DIVIDE_PRIME%numPartitions;
- /*return UtilFunctions.longHashFunc(((key.getFirstIndex()+MatrixIndexes.ADD_PRIME2)<<32)
- +key.getSecondIndex()+MatrixIndexes.ADD_PRIME1)
- %MatrixIndexes.DIVIDE_PRIME%numPartitions;*/
- // return UtilFunctions.longHashFunc(key.getFirstIndex()*127 + key.getSecondIndex())%10007%numPartitions;
+ public int getPartition(TaggedTripleIndexes key, MatrixBlock value, int numPartitions) {
+ return UtilFunctions.longHashCode((key.getFirstIndex()*127)
+ +key.getSecondIndex()+UtilFunctions.ADD_PRIME1)
+ %UtilFunctions.DIVIDE_PRIME%numPartitions;
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/matrix/data/TripleIndexes.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/matrix/data/TripleIndexes.java b/src/main/java/org/apache/sysml/runtime/matrix/data/TripleIndexes.java
index fe6a82c..ac517be 100644
--- a/src/main/java/org/apache/sysml/runtime/matrix/data/TripleIndexes.java
+++ b/src/main/java/org/apache/sysml/runtime/matrix/data/TripleIndexes.java
@@ -123,7 +123,7 @@ public class TripleIndexes implements WritableComparable<TripleIndexes>, Seriali
@Override
public int hashCode() {
- return UtilFunctions.longHashFunc((first<<32)+(second<<16)+third+MatrixIndexes.ADD_PRIME1)%MatrixIndexes.DIVIDE_PRIME;
+ return UtilFunctions.longHashCode((first<<32)+(second<<16)+third+UtilFunctions.ADD_PRIME1)%UtilFunctions.DIVIDE_PRIME;
}
public static class Comparator implements RawComparator<TripleIndexes>
@@ -149,13 +149,9 @@ public class TripleIndexes implements WritableComparable<TripleIndexes>, Seriali
public int getPartition(TripleIndexes key, TaggedMatrixValue value,
int numPartitions) {
- return UtilFunctions.longHashFunc((key.getFirstIndex()*127)
- +key.getSecondIndex()+MatrixIndexes.ADD_PRIME1)
- %MatrixIndexes.DIVIDE_PRIME%numPartitions;
- /*return UtilFunctions.longHashFunc(((key.getFirstIndex()+MatrixIndexes.ADD_PRIME2)<<32)
- +key.getSecondIndex()+MatrixIndexes.ADD_PRIME1)
- %MatrixIndexes.DIVIDE_PRIME%numPartitions;*/
- // return UtilFunctions.longHashFunc(key.getFirstIndex()*127 + key.getSecondIndex())%10007%numPartitions;
+ return UtilFunctions.longHashCode((key.getFirstIndex()*127)
+ +key.getSecondIndex()+UtilFunctions.ADD_PRIME1)
+ %UtilFunctions.DIVIDE_PRIME%numPartitions;
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java b/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
index d5e2a94..be9b25a 100644
--- a/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
+++ b/src/main/java/org/apache/sysml/runtime/util/LongLongDoubleHashMap.java
@@ -131,9 +131,7 @@ public class LongLongDoubleHashMap
* @return
*/
private static int hash(long key1, long key2) {
- //basic hash mixing of two longs hashes (w/o object creation)
- int h = (int)(key1 ^ (key1 >>> 32));
- h = h*31 + (int)(key2 ^ (key2 >>> 32));
+ int h = UtilFunctions.longlongHashCode(key1, key2);
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
http://git-wip-us.apache.org/repos/asf/incubator-systemml/blob/1d047989/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java b/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java
index 24403d3..24e9e00 100644
--- a/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java
+++ b/src/main/java/org/apache/sysml/runtime/util/UtilFunctions.java
@@ -42,11 +42,36 @@ public class UtilFunctions
//(same epsilon as used for matrix index cast in R)
public static double DOUBLE_EPS = Math.pow(2, -53);
+ //prime numbers for old hash function (divide prime close to max int,
+ //because it determines the max hash domain size
+ public static final long ADD_PRIME1 = 99991;
+ public static final long ADD_PRIME2 = 853;
+ public static final int DIVIDE_PRIME = 1405695061;
- public static int longHashFunc(long v) {
+ public static int longHashCode(long v) {
return (int)(v^(v>>>32));
}
+ @Deprecated
+ public static int longlongHashCodeOld(long key1, long key2) {
+ return UtilFunctions.longHashCode((key1<<32)+key2+ADD_PRIME1)%DIVIDE_PRIME;
+ }
+
+ /**
+ * Returns the hash code for a long-long pair. This is the default
+ * hash function for the keys of a distributed matrix in MR/Spark.
+ *
+ * @param key1
+ * @param key2
+ * @return
+ */
+ public static int longlongHashCode(long key1, long key2) {
+ //basic hash mixing of two longs hashes (similar to
+ //Arrays.hashCode(long[]) but w/o array creation/copy)
+ int h = (int)(key1 ^ (key1 >>> 32));
+ return h*31 + (int)(key2 ^ (key2 >>> 32));
+ }
+
public static int nextIntPow2( int in ) {
int expon = (in==0) ? 0 : 32-Integer.numberOfLeadingZeros(in-1);
long pow2 = (long) Math.pow(2, expon);