GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — [SYSTEMDS-418] Performance improvements lineage reuse probing/spilling · apache/systemds@1abe9cb

File tree

Expand file treeCollapse file tree

Open diff view settings

Filter options

src/main/java/org/apache/sysds/runtime
- controlprogram
  - ProgramBlock.java
- lineage

Expand file treeCollapse file tree

Open diff view settings

Collapse file

`‎src/main/java/org/apache/sysds/runtime/controlprogram/ProgramBlock.java‎`

Copy file name to clipboardExpand all lines: src/main/java/org/apache/sysds/runtime/controlprogram/ProgramBlock.java

+1-1Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -247,7 +247,7 @@ private void executeSingleInstruction( Instruction currInst, ExecutionContext ec`
`247`	`247`	`tmp.processInstruction(ec);`
`248`	`248`
`249`	`249`	`// cache result`
`250`		`- LineageCache.putValue(tmp, ec, System.nanoTime()-et0);`
	`250`	`+ LineageCache.putValue(tmp, ec, et0);`
`251`	`251`
`252`	`252`	`// post-process instruction (debug)`
`253`	`253`	`tmp.postprocessInstruction( ec );`

Collapse file

`‎src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java‎`

Copy file name to clipboardExpand all lines: src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java

+28-20Lines changed: 28 additions & 20 deletions

Original file line number	Diff line number	Diff line change
`@@ -19,6 +19,8 @@`
`19`	`19`
`20`	`20`	`package org.apache.sysds.runtime.lineage;`
`21`	`21`
	`22`	`+import org.apache.commons.lang3.tuple.MutablePair;`
	`23`	`+import org.apache.commons.lang3.tuple.Pair;`
`22`	`24`	`import org.apache.sysds.api.DMLScript;`
`23`	`25`	`import org.apache.sysds.common.Types.DataType;`
`24`	`26`	`import org.apache.sysds.common.Types.FileFormat;`
`@@ -45,6 +47,8 @@`
`45`	`47`	`import org.apache.sysds.runtime.matrix.data.MatrixBlock;`
`46`	`48`	`import org.apache.sysds.runtime.meta.MetaDataFormat;`
`47`	`49`
	`50`	`+import java.util.ArrayList;`
	`51`	`+import java.util.Arrays;`
`48`	`52`	`import java.util.HashMap;`
`49`	`53`	`import java.util.List;`
`50`	`54`	`import java.util.Map;`
`@@ -81,39 +85,40 @@ public static boolean reuse(Instruction inst, ExecutionContext ec) {`
`81`	`85`	`if (LineageCacheConfig.isReusable(inst, ec)) {`
`82`	`86`	`ComputationCPInstruction cinst = (ComputationCPInstruction) inst;`
`83`	`87`	`LineageItem instLI = cinst.getLineageItem(ec).getValue();`
`84`		`- HashMap<LineageItem, LineageCacheEntry> liMap = new HashMap<>();`
	`88`	`+ List<MutablePair<LineageItem, LineageCacheEntry>> liList = null;`
`85`	`89`	`if (inst instanceof MultiReturnBuiltinCPInstruction) {`
	`90`	`+ liList = new ArrayList<>();`
`86`	`91`	`MultiReturnBuiltinCPInstruction mrInst = (MultiReturnBuiltinCPInstruction)inst;`
`87`	`92`	`for (int i=0; i<mrInst.getNumOutputs(); i++) {`
`88`	`93`	`String opcode = instLI.getOpcode() + String.valueOf(i);`
`89`		`- liMap.put(new LineageItem(opcode, instLI.getInputs()), null);`
	`94`	`+ liList.add(MutablePair.of(new LineageItem(opcode, instLI.getInputs()), null));`
`90`	`95`	`}`
`91`	`96`	`}`
`92`	`97`	`else`
`93`		`- liMap.put(instLI, null);`
	`98`	`+ liList = Arrays.asList(MutablePair.of(instLI, null));`
`94`	`99`
`95`	`100`	`//atomic try reuse full/partial and set placeholder, without`
`96`	`101`	`//obtaining value to avoid blocking in critical section`
`97`	`102`	`LineageCacheEntry e = null;`
`98`	`103`	`boolean reuseAll = true;`
`99`	`104`	`synchronized( _cache ) {`
`100`	`105`	`//try to reuse full or partial intermediates`
`101`		`- for (LineageItem item : liMap.keySet()) {`
	`106`	`+ for (MutablePair<LineageItem,LineageCacheEntry> item : liList) {`
`102`	`107`	`if (LineageCacheConfig.getCacheType().isFullReuse())`
`103`		`- e = LineageCache.probe(item) ? getIntern(item) : null;`
	`108`	`+ e = LineageCache.probe(item.getKey()) ? getIntern(item.getKey()) : null;`
`104`	`109`	`//TODO need to also move execution of compensation plan out of here`
`105`	`110`	`//(create lazily evaluated entry)`
`106`	`111`	`if (e == null && LineageCacheConfig.getCacheType().isPartialReuse())`
`107`	`112`	`if( LineageRewriteReuse.executeRewrites(inst, ec) )`
`108`		`- e = getIntern(item);`
	`113`	`+ e = getIntern(item.getKey());`
`109`	`114`	`//TODO: MultiReturnBuiltin and partial rewrites`
`110`	`115`	`reuseAll &= (e != null);`
`111`		`- liMap.put(item, e);`
	`116`	`+ item.setValue(e);`
`112`	`117`
`113`	`118`	`//create a placeholder if no reuse to avoid redundancy`
`114`	`119`	`//(e.g., concurrent threads that try to start the computation)`
`115`	`120`	`if(e == null && isMarkedForCaching(inst, ec)) {`
`116`		`- putIntern(item, cinst.output.getDataType(), null, null, 0);`
	`121`	`+ putIntern(item.getKey(), cinst.output.getDataType(), null, null, 0);`
`117`	`122`	`//FIXME: different o/p datatypes for MultiReturnBuiltins.`
`118`	`123`	`}`
`119`	`124`	`}`
`@@ -122,7 +127,7 @@ public static boolean reuse(Instruction inst, ExecutionContext ec) {`
`122`	`127`
`123`	`128`	`if(reuse) { //reuse`
`124`	`129`	`//put reuse value into symbol table (w/ blocking on placeholders)`
`125`		`- for (Map.Entry<LineageItem, LineageCacheEntry> entry : liMap.entrySet()) {`
	`130`	`+ for (MutablePair<LineageItem, LineageCacheEntry> entry : liList) {`
`126`	`131`	`e = entry.getValue();`
`127`	`132`	`String outName = null;`
`128`	`133`	`if (inst instanceof MultiReturnBuiltinCPInstruction)`
`@@ -243,39 +248,42 @@ public static void putMatrix(Instruction inst, ExecutionContext ec, long compute`
`243`	`248`	`}`
`244`	`249`	`}`
`245`	`250`
`246`		`- public static void putValue(Instruction inst, ExecutionContext ec, long computetime) {`
	`251`	`+ public static void putValue(Instruction inst, ExecutionContext ec, long starttime) {`
`247`	`252`	`if (ReuseCacheType.isNone())`
`248`	`253`	`return;`
	`254`	`+ long computetime = System.nanoTime() - starttime;`
`249`	`255`	`if (LineageCacheConfig.isReusable(inst, ec) ) {`
`250`	`256`	`//if (!isMarkedForCaching(inst, ec)) return;`
`251`		`- HashMap<LineageItem, Data> liDataMap = new HashMap<>();`
	`257`	`+ List<Pair<LineageItem, Data>> liData = null;`
`252`	`258`	`LineageItem instLI = ((LineageTraceable) inst).getLineageItem(ec).getValue();`
`253`	`259`	`if (inst instanceof MultiReturnBuiltinCPInstruction) {`
	`260`	`+ liData = new ArrayList<>();`
`254`	`261`	`MultiReturnBuiltinCPInstruction mrInst = (MultiReturnBuiltinCPInstruction)inst;`
`255`	`262`	`for (int i=0; i<mrInst.getNumOutputs(); i++) {`
`256`	`263`	`String opcode = instLI.getOpcode() + String.valueOf(i);`
`257`	`264`	`LineageItem li = new LineageItem(opcode, instLI.getInputs());`
`258`	`265`	`Data value = ec.getVariable(mrInst.getOutput(i));`
`259`		`- liDataMap.put(li, value);`
	`266`	`+ liData.add(Pair.of(li, value));`
`260`	`267`	`}`
`261`	`268`	`}`
`262`	`269`	`else`
`263`		`- liDataMap.put(instLI, ec.getVariable(((ComputationCPInstruction) inst).output));`
	`270`	`+ liData = Arrays.asList(Pair.of(instLI, ec.getVariable(((ComputationCPInstruction) inst).output)));`
`264`	`271`	`synchronized( _cache ) {`
`265`		`- for (Map.Entry<LineageItem, Data> entry : liDataMap.entrySet()) {`
	`272`	`+ for (Pair<LineageItem, Data> entry : liData) {`
`266`	`273`	`LineageItem item = entry.getKey();`
`267`	`274`	`Data data = entry.getValue();`
	`275`	`+ LineageCacheEntry centry = _cache.get(item);`
`268`	`276`	`if (data instanceof MatrixObject)`
`269`		`- _cache.get(item).setValue(((MatrixObject)data).acquireReadAndRelease(), computetime);`
	`277`	`+ centry.setValue(((MatrixObject)data).acquireReadAndRelease(), computetime);`
`270`	`278`	`else if (data instanceof ScalarObject)`
`271`		`- _cache.get(item).setValue((ScalarObject)data, computetime);`
	`279`	`+ centry.setValue((ScalarObject)data, computetime);`
`272`	`280`	`else`
`273`	`281`	`throw new DMLRuntimeException("Lineage Cache: unsupported data: "+data.getDataType());`
`274`	`282`
`275`	`283`	`//maintain order for eviction`
`276`		`- LineageCacheEviction.addEntry(_cache.get(item));`
	`284`	`+ LineageCacheEviction.addEntry(centry);`
`277`	`285`
`278`		`- long size = _cache.get(item).getSize();`
	`286`	`+ long size = centry.getSize();`
`279`	`287`	`if (!LineageCacheEviction.isBelowThreshold(size))`
`280`	`288`	`LineageCacheEviction.makeSpace(_cache, size);`
`281`	`289`	`LineageCacheEviction.updateSize(size, true);`
`@@ -284,8 +292,8 @@ else if (data instanceof ScalarObject)`
`284`	`292`	`}`
`285`	`293`	`}`
`286`	`294`
`287`		`- public static void putValue(List<DataIdentifier> outputs, LineageItem[] liInputs,`
`288`		`- String name, ExecutionContext ec, long computetime)`
	`295`	`+ public static void putValue(List<DataIdentifier> outputs,`
	`296`	`+ LineageItem[] liInputs, String name, ExecutionContext ec, long computetime)`
`289`	`297`	`{`
`290`	`298`	`if (!LineageCacheConfig.isMultiLevelReuse())`
`291`	`299`	`return;`

Collapse file

`‎src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java‎`

Copy file name to clipboardExpand all lines: src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java

+4-9Lines changed: 4 additions & 9 deletions

Original file line number	Diff line number	Diff line change
`@@ -99,7 +99,7 @@ private enum CachedItemTail {`
`99`	`99`
`100`	`100`	`private static LineageCachePolicy _cachepolicy = null;`
`101`	`101`	`// Weights for scoring components (computeTime/size, LRU timestamp)`
`102`		`- private static double[] WEIGHTS = {0, 1};`
	`102`	`+ protected static double[] WEIGHTS = {0, 1};`
`103`	`103`
`104`	`104`	`protected enum LineageCacheStatus {`
`105`	`105`	`EMPTY, //Placeholder with no data. Cannot be evicted.`
`@@ -121,14 +121,9 @@ public enum LineageCachePolicy {`
`121`	`121`	`}`
`122`	`122`
`123`	`123`	`protected static Comparator<LineageCacheEntry> LineageCacheComparator = (e1, e2) -> {`
`124`		`- // Gather the weights for scoring components`
`125`		`- double w1 = LineageCacheConfig.WEIGHTS[0];`
`126`		`- double w2 = LineageCacheConfig.WEIGHTS[1];`
`127`		`- // Generate scores`
`128`		`- double score1 = w1(((double)e1._computeTime)/e1.getSize()) + w2e1.getTimestamp();`
`129`		`- double score2 = w1((double)e2._computeTime)/e2.getSize() + w2e2.getTimestamp();`
`130`		`- // Generate order. If scores are same, order by LineageItem ID.`
`131`		`- return score1 == score2 ? Long.compare(e1._key.getId(), e2._key.getId()) : score1 < score2 ? -1 : 1;`
	`124`	`+ return e1.score == e2.score ?`
	`125`	`+ Long.compare(e1._key.getId(), e2._key.getId()) :`
	`126`	`+ e1.score < e2.score ? -1 : 1;`
`132`	`127`	`};`
`133`	`128`
`134`	`129`	`//----------------------------------------------------------------//`

Collapse file

`‎src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java‎`

Copy file name to clipboardExpand all lines: src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEntry.java

+10Lines changed: 10 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -35,6 +35,7 @@ public class LineageCacheEntry {`
`35`	`35`	`protected LineageCacheStatus _status;`
`36`	`36`	`protected LineageCacheEntry _nextEntry;`
`37`	`37`	`protected LineageItem _origItem;`
	`38`	`+ protected double score;`
`38`	`39`
`39`	`40`	`public LineageCacheEntry(LineageItem key, DataType dt, MatrixBlock Mval, ScalarObject Sval, long computetime) {`
`40`	`41`	`_key = key;`
`@@ -123,9 +124,18 @@ protected synchronized void setNullValues() {`
`123`	`124`
`124`	`125`	`protected synchronized void setTimestamp() {`
`125`	`126`	`_timestamp = System.currentTimeMillis();`
	`127`	`+ recomputeScore();`
`126`	`128`	`}`
`127`	`129`
`128`	`130`	`protected synchronized long getTimestamp() {`
`129`	`131`	`return _timestamp;`
`130`	`132`	`}`
	`133`	`+`
	`134`	`+ private void recomputeScore() {`
	`135`	`+ // Gather the weights for scoring components`
	`136`	`+ double w1 = LineageCacheConfig.WEIGHTS[0];`
	`137`	`+ double w2 = LineageCacheConfig.WEIGHTS[1];`
	`138`	`+ // Generate scores`
	`139`	`+ score = w1(((double)_computeTime)/getSize()) + w2getTimestamp();`
	`140`	`+ }`
`131`	`141`	`}`

Collapse file

`‎src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java‎`

Copy file name to clipboardExpand all lines: src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java

+7-13Lines changed: 7 additions & 13 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,6 +23,7 @@`
`23`	`23`	`import java.util.HashMap;`
`24`	`24`	`import java.util.HashSet;`
`25`	`25`	`import java.util.Map;`
	`26`	`+import java.util.Set;`
`26`	`27`	`import java.util.TreeSet;`
`27`	`28`
`28`	`29`	`import org.apache.sysds.api.DMLScript;`
`@@ -36,7 +37,7 @@ public class LineageCacheEviction`
`36`	`37`	`{`
`37`	`38`	`private static long _cachesize = 0;`
`38`	`39`	`private static long CACHE_LIMIT; //limit in bytes`
`39`		`- protected static final HashSet<LineageItem> _removelist = new HashSet<>();`
	`40`	`+ protected static final Set<LineageItem> _removelist = new HashSet<>();`
`40`	`41`	`private static final Map<LineageItem, SpilledItem> _spillList = new HashMap<>();`
`41`	`42`	`private static String _outdir = null;`
`42`	`43`	`private static TreeSet<LineageCacheEntry> weightedQueue = new TreeSet<>(LineageCacheConfig.LineageCacheComparator);`
`@@ -202,8 +203,6 @@ protected static void makeSpace(Map<LineageItem, LineageCacheEntry> cache, long`
`202`	`203`	`//TODO: Graceful handling of status.`
`203`	`204`	`}`
`204`	`205`
`205`		`- double exectime = ((double) e._computeTime) / 1000000; // in milliseconds`
`206`		`-`
`207`	`206`	`if (!e.isMatrixValue()) {`
`208`	`207`	`// No spilling for scalar entries. Just delete those.`
`209`	`208`	`// Note: scalar entries with higher computation time are pinned.`
`@@ -213,6 +212,7 @@ protected static void makeSpace(Map<LineageItem, LineageCacheEntry> cache, long`
`213`	`212`
`214`	`213`	`// Estimate time to write to FS + read from FS.`
`215`	`214`	`double spilltime = getDiskSpillEstimate(e) * 1000; // in milliseconds`
	`215`	`+ double exectime = ((double) e._computeTime) / 1000000; // in milliseconds`
`216`	`216`
`217`	`217`	`if (LineageCache.DEBUG) {`
`218`	`218`	`if (exectime > LineageCacheConfig.MIN_SPILL_TIME_ESTIMATE) {`
`@@ -227,19 +227,13 @@ protected static void makeSpace(Map<LineageItem, LineageCacheEntry> cache, long`
`227`	`227`	`if (spilltime < LineageCacheConfig.MIN_SPILL_TIME_ESTIMATE) {`
`228`	`228`	`// Can't trust the estimate if less than 100ms.`
`229`	`229`	`// Spill if it takes longer to recompute.`
`230`		`- if (exectime >= LineageCacheConfig.MIN_SPILL_TIME_ESTIMATE)`
`231`		`- //spillToLocalFS(e);`
`232`		`- removeOrSpillEntry(cache, e, true); //spill`
`233`		`- else`
`234`		`- removeOrSpillEntry(cache, e, false); //delete`
	`230`	`+ removeOrSpillEntry(cache, e, //spill or delete`
	`231`	`+ exectime >= LineageCacheConfig.MIN_SPILL_TIME_ESTIMATE);`
`235`	`232`	`}`
`236`	`233`	`else {`
`237`	`234`	`// Spill if it takes longer to recompute than spilling.`
`238`		`- if (exectime > spilltime)`
`239`		`- //spillToLocalFS(e);`
`240`		`- removeOrSpillEntry(cache, e, true); //spill`
`241`		`- else`
`242`		`- removeOrSpillEntry(cache, e, false); //delete`
	`235`	`+ removeOrSpillEntry(cache, e, //spill or delete`
	`236`	`+ exectime > spilltime);`
`243`	`237`	`}`
`244`	`238`	`}`
`245`	`239`	`}`

0 commit comments

Comments

0 (0)

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.