[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).
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 @@
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 @@
if (!(o instanceof LineageItem))
return false;
- resetVisitStatus();
+ resetVisitStatusNR();
boolean ret = equalsLI((LineageItem) o);
- resetVisitStatus();
+ resetVisitStatusNR();
return ret;
}
@@ -180,16 +182,47 @@
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 @@
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 @@
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 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 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 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;
}
