This is an automated email from the ASF dual-hosted git repository. arnabp20 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 faec158 [MINOR] Fix bugs in scoring function and eviction logic. faec158 is described below commit faec15810e18fc497e950b830811a919f5aa5c5f Author: arnabp <arnab.ph...@tugraz.at> AuthorDate: Tue Jun 2 18:34:36 2020 +0200 [MINOR] Fix bugs in scoring function and eviction logic. This patch fixes the root cause behind lineage test failure in github. This patch - fixes a bug in the scoring function, - fixes double polling issue in eviction logic, - adds APIs to control reusable opcodes from outside. This helps anticipating and test caching and eviction behaviors, - removes a faulty assertion from eviction test and also adds a new assertion. --- .../org/apache/sysds/runtime/lineage/LineageCache.java | 1 + .../apache/sysds/runtime/lineage/LineageCacheConfig.java | 15 ++++++++++++--- .../sysds/runtime/lineage/LineageCacheEviction.java | 13 ++++--------- .../sysds/runtime/lineage/LineageCacheStatistics.java | 4 ++++ .../sysds/test/functions/lineage/CacheEvictionTest.java | 10 ++++++---- src/test/scripts/functions/lineage/CacheEviction1.dml | 15 ++++++++------- 6 files changed, 35 insertions(+), 23 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 ca6b349..9f53395 100644 --- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java +++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCache.java @@ -342,6 +342,7 @@ public class LineageCache // Maintain _origItem as head. while (tmp._nextEntry != null) tmp = tmp._nextEntry; + // FIXME: No need add at the end; add just after head. tmp._nextEntry = e; //maintain order for eviction diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java index 7fce53b..c4caed9 100644 --- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java +++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheConfig.java @@ -32,11 +32,12 @@ public class LineageCacheConfig { //-------------CACHING LOGIC RELATED CONFIGURATIONS--------------// - private static final String[] REUSE_OPCODES = new String[] { + private static final String[] OPCODES = new String[] { "tsmm", "ba+*", "*", "/", "+", "||", "nrow", "ncol", "round", "exp", "log", "rightIndex", "leftIndex", "groupedagg", "r'", "solve", "spoof" //TODO: Reuse everything. }; + private static String[] REUSE_OPCODES = new String[] {}; public enum ReuseCacheType { REUSE_FULL, @@ -120,7 +121,7 @@ public class LineageCacheConfig double w2 = LineageCacheConfig.WEIGHTS[1]; // Generate scores double score1 = w1*(((double)e1._computeTime)/e1.getSize()) + w2*e1.getTimestamp(); - double score2 = w1*((double)e2._computeTime)/e2.getSize() + w2*e1.getTimestamp(); + double score2 = w1*((double)e2._computeTime)/e2.getSize() + w2*e2.getTimestamp(); // Generate order. If scores are same, order by LineageItem ID. return score1 == score2 ? Long.compare(e1._key.getId(), e2._key.getId()) : score1 < score2 ? -1 : 1; }; @@ -129,11 +130,19 @@ public class LineageCacheConfig static { //setup static configuration parameters + REUSE_OPCODES = OPCODES; setSpill(true); - //setCachePolicy(LineageCachePolicy.WEIGHTED); + setCachePolicy(LineageCachePolicy.HYBRID); setCompAssRW(true); } + public static void setReusableOpcodes(String... ops) { + REUSE_OPCODES = ops; + } + + public static void resetReusableOpcodes() { + REUSE_OPCODES = OPCODES; + } public static boolean isReusable (Instruction inst, ExecutionContext ec) { boolean insttype = inst instanceof ComputationCPInstruction diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java index 2139689..30f930f 100644 --- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java +++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheEviction.java @@ -178,17 +178,16 @@ public class LineageCacheEviction protected static void makeSpace(Map<LineageItem, LineageCacheEntry> cache, long spaceNeeded) { //Cost based eviction - LineageCacheEntry e = weightedQueue.pollFirst(); - while (e != null) + while ((spaceNeeded + _cachesize) > CACHE_LIMIT) { - if ((spaceNeeded + _cachesize) <= CACHE_LIMIT) - // Enough space recovered. + LineageCacheEntry e = weightedQueue.pollFirst(); + if (e == null) + // Nothing to evict. break; if (!LineageCacheConfig.isSetSpill()) { // If eviction is disabled, just delete the entries. removeOrSpillEntry(cache, e, false); - e = weightedQueue.pollFirst(); continue; } @@ -205,7 +204,6 @@ public class LineageCacheEviction // No spilling for scalar entries. Just delete those. // Note: scalar entries with higher computation time are pinned. removeOrSpillEntry(cache, e, false); - e = weightedQueue.pollFirst(); continue; } @@ -239,9 +237,6 @@ public class LineageCacheEviction else removeOrSpillEntry(cache, e, false); //delete } - - // Remove the entry from cache. - e = weightedQueue.pollFirst(); } } diff --git a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java index 55bf70f..143fdfc 100644 --- a/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java +++ b/src/main/java/org/apache/sysds/runtime/lineage/LineageCacheStatistics.java @@ -79,6 +79,10 @@ public class LineageCacheStatistics { // Number of times single instruction results are reused (full and partial). _numHitsInst.increment(); } + + public static long getInstHits() { + return _numHitsInst.longValue(); + } public static void incrementSBHits() { // Number of times statementblock results are reused. diff --git a/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java b/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java index 9f925c5..03604e4 100644 --- a/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java +++ b/src/test/java/org/apache/sysds/test/functions/lineage/CacheEvictionTest.java @@ -85,6 +85,7 @@ public class CacheEvictionTest extends AutomatedTestBase { fullDMLScriptName = getScript(); Lineage.resetInternalState(); long cacheSize = LineageCacheEviction.getCacheLimit(); + LineageCacheConfig.setReusableOpcodes("exp", "+", "round"); // LRU based eviction List<String> proArgs = new ArrayList<>(); @@ -99,7 +100,7 @@ public class CacheEvictionTest extends AutomatedTestBase { runTest(true, EXCEPTION_NOT_EXPECTED, null, -1); HashMap<MatrixValue.CellIndex, Double> R_lru = readDMLMatrixFromHDFS("R"); long expCount_lru = Statistics.getCPHeavyHitterCount("exp"); - long plusCount_lru = Statistics.getCPHeavyHitterCount("+"); + long hitCount_lru = LineageCacheStatistics.getInstHits(); long evictedCount_lru = LineageCacheStatistics.getMemDeletes(); // Weighted scheme (computationTime/Size) @@ -116,8 +117,9 @@ public class CacheEvictionTest extends AutomatedTestBase { runTest(true, EXCEPTION_NOT_EXPECTED, null, -1); HashMap<MatrixValue.CellIndex, Double> R_weighted= readDMLMatrixFromHDFS("R"); long expCount_wt = Statistics.getCPHeavyHitterCount("exp"); - long plusCount_wt = Statistics.getCPHeavyHitterCount("+"); + long hitCount_wt = LineageCacheStatistics.getInstHits(); long evictedCount_wt = LineageCacheStatistics.getMemDeletes(); + LineageCacheConfig.resetReusableOpcodes(); // Compare results Lineage.setLinReuseNone(); @@ -125,11 +127,11 @@ public class CacheEvictionTest extends AutomatedTestBase { // Compare reused instructions Assert.assertTrue(expCount_lru > expCount_wt); - Assert.assertTrue(plusCount_lru < plusCount_wt); - // Compare counts of evicted items // LRU tends to evict more entries to recover equal amount of memory Assert.assertTrue(evictedCount_lru > evictedCount_wt); + // Compare cache hits + Assert.assertTrue(hitCount_lru < hitCount_wt); } finally { OptimizerUtils.ALLOW_ALGEBRAIC_SIMPLIFICATION = old_simplification; diff --git a/src/test/scripts/functions/lineage/CacheEviction1.dml b/src/test/scripts/functions/lineage/CacheEviction1.dml index f25ad6d..5c9b94c 100644 --- a/src/test/scripts/functions/lineage/CacheEviction1.dml +++ b/src/test/scripts/functions/lineage/CacheEviction1.dml @@ -19,7 +19,6 @@ # #------------------------------------------------------------- - cache_size = ceil($1/(1024*1024)); #in MB output_size = 8; #8MB X = rand(rows=1024, cols=1024, sparsity = 1.0, seed=42); @@ -34,17 +33,19 @@ for (i in 1:k/2) { X = X + 1; } -# Trigger eviction. LRU evicts both 'exp' and '+' results, -# where Weighted scheme evicts only '+' results to recover +# Trigger evictions. LRU evicts half of both 'exp' and '+' results, +# where Weighted scheme evicts all the '+' results to recover # same amount of memory. -for (i in 1:1.5*k/4) { +for (i in 1:k/4) { R = round(X); X = X + 1; } - -# Try to reuse 'exp' and '+' results. LRU reuses less -# 'exp' outputs but more '+' outputs. +# Try to reuse 'exp' and '+' results. LRU keeps evicting +# the remaining half of 'exp' and '+' results from the 1st +# loop, and in turn fails to reuse any of the instructions, +# where Weighted scheme keeps evicting the '+'s (from 2nd loop) +# but able to reuse 'exp's. for (i in 1:k/4) { R1 = exp(X1); X1 = X1 + 1;