This is an automated email from the ASF dual-hosted git repository.
mboehm7 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/systemml.git
The following commit(s) were added to refs/heads/master by this push:
new 86f7b1f [SYSTEMDS-412] Robustness lineage DAG ops (non-recursive
resetVisit)
86f7b1f is described below
commit 86f7b1f47bc1f1f4291e97adc3c5d996b0dc67ba
Author: Matthias Boehm <[email protected]>
AuthorDate: Sun Jun 7 22:29:56 2020 +0200
[SYSTEMDS-412] Robustness lineage DAG ops (non-recursive resetVisit)
This patch is a first step toward making the lineage DAG more robust
with regard to stack overflow errors, which occur for example in default
JVM configuration when writing out lineage DAGs of a depth >10,000s of
nodes. We use simple non-recursive stacks to perform these operations,
but explain and similar operations require some additional queueing to
preserve the previous output format (no need to break backwards
compatibility to previous releases).
---
.../apache/sysds/runtime/lineage/LineageCache.java | 2 +-
.../apache/sysds/runtime/lineage/LineageItem.java | 43 +++++++++++++++++++---
.../sysds/runtime/lineage/LineageItemUtils.java | 14 +++----
src/main/java/org/apache/sysds/utils/Explain.java | 12 +++---
4 files changed, 52 insertions(+), 19 deletions(-)
diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
index 9f53395..cb2d13b 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java
@@ -255,7 +255,7 @@ public class LineageCache
String boundVarName = outputs.get(i).getName();
LineageItem boundLI = ec.getLineage().get(boundVarName);
if (boundLI != null)
- boundLI.resetVisitStatus();
+ boundLI.resetVisitStatusNR();
if (boundLI == null || !LineageCache.probe(li) ||
!LineageCache.probe(boundLI)) {
AllOutputsCacheable = false;
}
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 e5345e8..38a4cb9 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageItem.java
@@ -19,6 +19,8 @@
package org.apache.sysds.runtime.lineage;
+import java.util.Stack;
+
import org.apache.sysds.runtime.DMLRuntimeException;
import org.apache.sysds.runtime.controlprogram.parfor.util.IDSequence;
import org.apache.sysds.runtime.util.UtilFunctions;
@@ -128,9 +130,9 @@ public class LineageItem {
if (!(o instanceof LineageItem))
return false;
- resetVisitStatus();
+ resetVisitStatusNR();
boolean ret = equalsLI((LineageItem) o);
- resetVisitStatus();
+ resetVisitStatusNR();
return ret;
}
@@ -180,16 +182,47 @@ public class LineageItem {
return !_opcode.isEmpty();
}
- public LineageItem resetVisitStatus() {
+ /**
+ * Non-recursive equivalent of {@link #resetVisitStatus()}
+ * for robustness with regard to stack overflow errors.
+ */
+ public void resetVisitStatusNR() {
+ Stack<LineageItem> q = new Stack<>();
+ q.push(this);
+ while( !q.empty() ) {
+ LineageItem tmp = q.pop();
+ if( !tmp.isVisited() )
+ continue;
+ if (tmp.getInputs() != null)
+ for (LineageItem li : tmp.getInputs())
+ q.push(li);
+ tmp.setVisited(false);
+ }
+ }
+
+ /**
+ * Non-recursive equivalent of {@link #resetVisitStatus(LineageItem[])}
+ * for robustness with regard to stack overflow errors.
+ *
+ * @param lis root lineage items
+ */
+ public static void resetVisitStatusNR(LineageItem[] lis) {
+ if (lis != null)
+ for (LineageItem liRoot : lis)
+ liRoot.resetVisitStatusNR();
+ }
+
+ @Deprecated
+ public void resetVisitStatus() {
if (!isVisited())
- return this;
+ return;
if (_inputs != null)
for (LineageItem li : getInputs())
li.resetVisitStatus();
setVisited(false);
- return this;
}
+ @Deprecated
public static void resetVisitStatus(LineageItem[] lis) {
if (lis != null)
for (LineageItem liRoot : lis)
diff --git
a/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
b/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
index b75baee..c49ba00 100644
--- a/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
+++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageItemUtils.java
@@ -157,7 +157,7 @@ public class LineageItemUtils {
String varname = LVARPREFIX + rootId;
//recursively construct hops
- root.resetVisitStatus();
+ root.resetVisitStatusNR();
Map<Long, Hop> operands = new HashMap<>();
rConstructHops(root, operands);
Hop out = HopRewriteUtils.createTransientWrite(
@@ -581,9 +581,9 @@ public class LineageItemUtils {
LineageItem li = new
LineageItem(item.getInputs()[1].getData(),
item.getInputs()[1].getOpcode(),
inputs.toArray(new LineageItem[0]));
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
rSetDedupInputOntoOutput(item.getData(), li,
dedupInput);
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
return li;
}
else {
@@ -633,9 +633,9 @@ public class LineageItemUtils {
}
public static LineageItem replace(LineageItem root, LineageItem liOld,
LineageItem liNew) {
- root.resetVisitStatus();
+ root.resetVisitStatusNR();
rReplace(root, liOld, liNew);
- root.resetVisitStatus();
+ root.resetVisitStatusNR();
return root;
}
@@ -657,9 +657,9 @@ public class LineageItemUtils {
public static void replaceDagLeaves(ExecutionContext ec, LineageItem
root, CPOperand[] newLeaves) {
//find and replace the placeholder leaves
- root.resetVisitStatus();
+ root.resetVisitStatusNR();
rReplaceDagLeaves(root, LineageItemUtils.getLineage(ec,
newLeaves));
- root.resetVisitStatus();
+ root.resetVisitStatusNR();
}
public static void rReplaceDagLeaves(LineageItem root, LineageItem[]
newleaves) {
diff --git a/src/main/java/org/apache/sysds/utils/Explain.java
b/src/main/java/org/apache/sysds/utils/Explain.java
index 8d6124e..d9e541e 100644
--- a/src/main/java/org/apache/sysds/utils/Explain.java
+++ b/src/main/java/org/apache/sysds/utils/Explain.java
@@ -337,25 +337,25 @@ public class Explain
public static String explainLineageItems( LineageItem[] lis, int level
) {
StringBuilder sb = new StringBuilder();
- LineageItem.resetVisitStatus(lis);
+ LineageItem.resetVisitStatusNR(lis);
for( LineageItem li : lis )
sb.append(explainLineageItem(li, level));
- LineageItem.resetVisitStatus(lis);
+ LineageItem.resetVisitStatusNR(lis);
return sb.toString();
}
public static String explain( LineageItem li ) {
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
String s = explain(li, 0);
s += rExplainDedupItems(li, new ArrayList<>());
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
return s;
}
private static String explain( LineageItem li, int level ) {
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
String ret = explainLineageItem(li, level);
- li.resetVisitStatus();
+ li.resetVisitStatusNR();
return ret;
}
