[SYSTEMDS-418] Performance lineage tracing w/ probing (better hashing)
This patch fixes an interesting performance bug caused by the recursive
hash computation of lineage items. Due to repeated operation sequences
(from loop iterations) and integer overflows during the hash
computation, there were systematic hash sequence within one lineage DAG.
This in turn lead to less pruning power on recursive equals
computations, and collisions in the lineage cache, leading to even more
recursive equals comparisons.
The fix is simple. We now handle such overflows on hash aggregation
(e.g., hash(int,int)) with a long instead of int hash function on
demand. On the following test scenario
for(i in 1:1000)
X = ((X + X) * 2 - X) / 3
the previous runtime was 162s while with this patch it reduced to
0.244s. Even with 10K iterations, the runtime is still 1.1s, which
suggests that any super-linear behavior has been eliminated.
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
index 7a55902..ec86a5e 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
@@ -160,11 +160,12 @@
public int hashCode() {
if (_hash == 0) {
//compute hash over opcode and all inputs
- int h = _opcode.hashCode();
+ int h = UtilFunctions.intHashCode(
+ _opcode.hashCode(), _data.hashCode());
if (_inputs != null)
for (LineageItem li : _inputs)
- h = UtilFunctions.intHashCode(h, li.hashCode());
- _hash = UtilFunctions.intHashCode(h, _data.hashCode());
+ h = UtilFunctions.intHashCodeRobust(li.hashCode(), h);
+ _hash = h;
}
return _hash;
}
diff --git a/src/main/java/org/apache/sysds/runtime/util/UtilFunctions.java b/src/main/java/org/apache/sysds/runtime/util/UtilFunctions.java
index 8b803dc..375b601 100644
--- a/src/main/java/org/apache/sysds/runtime/util/UtilFunctions.java
+++ b/src/main/java/org/apache/sysds/runtime/util/UtilFunctions.java
@@ -59,11 +59,19 @@
//because it determines the max hash domain size
public static final long ADD_PRIME1 = 99991;
public static final int DIVIDE_PRIME = 1405695061;
-
+
public static int intHashCode(int key1, int key2) {
return 31 * (31 + key1) + key2;
}
+ public static int intHashCodeRobust(int key1, int key2) {
+ // handle overflows to avoid systematic hash code repetitions
+ // in long recursive hash computations w/ repeated structure
+ long tmp = 31L * (31L + key1) + key2;
+ return (tmp < Integer.MAX_VALUE) ?
+ (int) tmp : longHashCode(tmp);
+ }
+
public static int longHashCode(long key1) {
return (int)(key1^(key1>>>32));
}
