memoizeit
Changes
src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java 629(+306 -323)
src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java 396(+188 -208)
Details
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Main.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Main.java
index 913f5a2..2f0618b 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Main.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Main.java
@@ -10,6 +10,7 @@ import br.ufrgs.inf.prosoft.memoizeit.adapter.TraceReader;
import br.ufrgs.inf.prosoft.memoizeit.graph.Graph;
import br.ufrgs.inf.prosoft.trace.Trace;
import br.ufrgs.inf.prosoft.trace.reader.Mode;
+
import java.util.List;
import java.util.Map;
import java.util.logging.Level;
@@ -29,7 +30,12 @@ public class Main {
System.setProperty("java.util.logging.SimpleFormatter.format", "[%1$tF %1$tT+%1$tL] [%4$-7s] [MemoizeIt] %5$s %n");
if (args.length < 2) {
- System.err.println("--trace=<TracePath> --callgraph=<CallGraphPath> [--mode=<complete|hashed|partial>] [--kernel=<iterative|exhaustive>] [--window=<windowSize>] [--shift=<shiftTime>]");
+ System.err.println("--trace=<TracePath>" +
+ " --callgraph=<CallGraphPath>" +
+ " [--mode=<complete|hashed|partial>]" +
+ " [--kernel=<iterative|exhaustive>]" +
+ " [--window=<windowSize>]" +
+ " [--shift=<shiftTime>]");
System.exit(1);
}
src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java 629(+306 -323)
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
index fa22b41..740e5cb 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
@@ -16,344 +16,327 @@ import java.util.logging.Logger;
import java.util.stream.Collectors;
/**
- *
* @author romulo
*/
public class MemoizeIt {
- // Minimum Execution Time Threshold
- private long minimumExecutionTime;
- // Minimum Relative Execution Time Threshold
- private double minimumRelativeTime;
- // Minimum Calls
- private int minimumMethodCalls;
- // Minimum Potential Hit Ratio Threshold
- private double minimumHitRatio;
- // List of methods called
- private List<Method> methods;
- // Call Graph
- private Graph<String> callGraph;
-
- private static final Logger LOGGER = Logger.getLogger(MemoizeIt.class.getName());
-
- public MemoizeIt() {
- this.minimumHitRatio = 0.5;
- this.minimumMethodCalls = 2;
- this.minimumRelativeTime = 1.0;
- this.minimumExecutionTime = 5;
+ private static final Logger LOGGER = Logger.getLogger(MemoizeIt.class.getName());
+ // Minimum Execution Time Threshold
+ private long minimumExecutionTime;
+ // Minimum Relative Execution Time Threshold
+ private double minimumRelativeTime;
+ // Minimum Calls
+ private int minimumMethodCalls;
+ // Minimum Potential Hit Ratio Threshold
+ private double minimumHitRatio;
+ // List of methods called
+ private List<Method> methods;
+ // Call Graph
+ private Graph<String> callGraph;
+
+ public MemoizeIt() {
+ this.minimumHitRatio = 0.5;
+ this.minimumMethodCalls = 2;
+ this.minimumRelativeTime = 1.0;
+ this.minimumExecutionTime = 5;
+ }
+
+ public static void suggestImplementation(Method method) {
+ Map<String, CachePerformance> cachingStrategyHasPerformance = method.simulateCachingStrategies();
+ CachePerformance globalMultiCachePerformance = cachingStrategyHasPerformance.get("globalMultiCache");
+ CachePerformance globalSingleCachePerformance = cachingStrategyHasPerformance.get("globalSingleCache");
+ CachePerformance instanceMultiCachePerformance = cachingStrategyHasPerformance.get("instanceMultiCache");
+ CachePerformance instanceSingleCachePerformance = cachingStrategyHasPerformance.get("instanceSingleCache");
+ StringBuilder stringBuilder = new StringBuilder();
+ stringBuilder.append("\t");
+ stringBuilder.append("GS: ");
+ stringBuilder.append("R").append(globalSingleCachePerformance.getRoundedHitRatio());
+ stringBuilder.append(" * ").append(globalSingleCachePerformance);
+ stringBuilder.append(" | IS: ");
+ stringBuilder.append("R").append(instanceSingleCachePerformance.getRoundedHitRatio());
+ stringBuilder.append(" * ").append(instanceSingleCachePerformance);
+ stringBuilder.append(" | GM: ");
+ stringBuilder.append("R").append(globalMultiCachePerformance.getRoundedHitRatio());
+ stringBuilder.append(" * ").append(globalMultiCachePerformance);
+ stringBuilder.append(" | IM: ");
+ stringBuilder.append("R").append(instanceMultiCachePerformance.getRoundedHitRatio());
+ stringBuilder.append(" * ").append(instanceMultiCachePerformance);
+ System.out.println(stringBuilder);
+ if (globalSingleCachePerformance.getRoundedHitRatio() >= 50) {
+ System.out.println("\tsingle, global");
+ } else if (instanceSingleCachePerformance.getRoundedHitRatio() >= 50) {
+ System.out.println("\tsingle, instance");
+ } else if (globalMultiCachePerformance.getRoundedHitRatio() >= 50) {
+ System.out.println("\tmulti, global");
+ } else if (instanceMultiCachePerformance.getRoundedHitRatio() >= 50) {
+ System.out.println("\tmulti, instance");
+ } else {
+ System.out.println("\tnone");
}
-
- public MemoizeIt setMinimumExecutionTime(long minimumExecutionTime) {
- this.minimumExecutionTime = minimumExecutionTime;
- return this;
- }
-
- public MemoizeIt setMinimumRelativeTime(double minimumRelativeTime) {
- this.minimumRelativeTime = minimumRelativeTime;
- return this;
- }
-
- public MemoizeIt setMinimumMethodCalls(int minimumMethodCalls) {
- this.minimumMethodCalls = minimumMethodCalls;
- return this;
- }
-
- public MemoizeIt setMinimumHitRatio(double minimumHitRatio) {
- this.minimumHitRatio = minimumHitRatio;
- return this;
- }
-
- public MemoizeIt setMethods(List<Method> methods) {
- this.methods = methods;
- return this;
- }
-
- public MemoizeIt setCallGraph(Graph<String> callGraph) {
- this.callGraph = callGraph;
- return this;
- }
-
- private Method getMethodByName(String name) {
- try {
- return this.methods.stream()
- .filter(method -> method.getName().equals(name))
- .findAny().get();
- } catch (Exception ex) {
- return null;
- }
- }
-
-// 3.1 time and frequency profiling
- private void filterInitialCandidates() {
- LOGGER.log(Level.INFO, "Fitering {0} initial candidates by frequency and average execution time", this.methods.size());
- this.methods.removeIf(method -> method.getOccurrencesSize() < this.minimumMethodCalls || method.getAverageExecutionTime() < this.minimumExecutionTime);
- LOGGER.log(Level.INFO, "Calculating representativity of {0} methods", this.methods.size());
- Collection<Node<String>> roots = this.callGraph.getRoots();
- roots.stream().forEach(root -> {
- Method method = getMethodByName(root.getContent());
- if (method == null) {
- return;
- }
- if (method.getRepresentativeness() != 0) {
- return;
- }
- method.setRepresentativeness(1);
- long rootAverageExecutionTime = method.getAverageExecutionTime();
- root.getLinks().stream().forEach(new Consumer<Node<String>>() {
-
- private final Collection<Node<String>> visited = new ArrayList<>();
-
- @Override
- public void accept(Node<String> node) {
- if (visited.contains(node)) {
- return;
- }
- visited.add(node);
- Method callee = getMethodByName(node.getContent());
- if (callee != null && callee.getRepresentativeness() == 0) {
- callee.setRepresentativeness(callee.getAverageExecutionTime() / rootAverageExecutionTime);
- }
- node.getLinks().stream().forEach(this);
- }
- });
-
- });
- this.methods.stream().filter(method -> method.getRepresentativeness() == 0)
- .forEach(method -> method.setRepresentativeness(1));
- LOGGER.log(Level.INFO, "Fitering {0} candidates by representativeness", this.methods.size());
- this.methods.removeIf(method -> method.getRepresentativeness() < this.minimumRelativeTime);
- }
-
- private void removeUnusedFields() {
- LOGGER.log(Level.INFO, "Removing unused fields from {0} methods", this.methods.size());
- this.methods.forEach(method -> method.removeUnusedFields(this.callGraph.getNode(method.getName())));
- }
-
-// 3.2 input-output profiling
- private void refineCandidates() {
- refineCandidates(true);
- }
-
- private void refineCandidates(boolean iteratively) {
- LOGGER.log(Level.INFO, "Refining {0} candidates", this.methods.size());
- this.methods.sort(Comparator.comparingInt(Method::getOccurrencesSize));
- this.methods.removeIf(method -> iteratively ? refineCandidateIteratively(method) : refineCandidateExhaustively(method));
- }
-
- private boolean refineCandidateExhaustively(Method method) {
- return refineCandidate(method, Integer.MAX_VALUE);
- }
-
- private boolean refineCandidateIteratively(Method method) {
- LOGGER.log(Level.INFO, "Iteratively refining {0}", method);
- int depth = 1;
- while (!method.wasFullyExplored()) {
- LOGGER.log(Level.INFO, "Exploring depth {0}", depth);
- boolean refineCandidate = refineCandidate(method, depth);
- if (refineCandidate) {
- LOGGER.log(Level.INFO, "Removing candidate");
- return true;
- }
- depth *= 2;
- }
- return false;
- }
-
- private boolean refineCandidate(Method method, int depth) {
- int occurrencesSize = method.getOccurrencesSize();
- method.groupByParameter(depth);
- int distinctOccurrencesSize = method.getDistinctOccurrencesSize();
- if (occurrencesSize == distinctOccurrencesSize) {
- return true;
- }
- if (method.isChangeful()) {
- return true;
- }
- return method.getPotentialHitRatio() < this.minimumHitRatio;
+ }
+
+ public MemoizeIt setMinimumExecutionTime(long minimumExecutionTime) {
+ this.minimumExecutionTime = minimumExecutionTime;
+ return this;
+ }
+
+ public MemoizeIt setMinimumRelativeTime(double minimumRelativeTime) {
+ this.minimumRelativeTime = minimumRelativeTime;
+ return this;
+ }
+
+ public MemoizeIt setMinimumMethodCalls(int minimumMethodCalls) {
+ this.minimumMethodCalls = minimumMethodCalls;
+ return this;
+ }
+
+ public MemoizeIt setMinimumHitRatio(double minimumHitRatio) {
+ this.minimumHitRatio = minimumHitRatio;
+ return this;
+ }
+
+ public MemoizeIt setMethods(List<Method> methods) {
+ this.methods = methods;
+ return this;
+ }
+
+ public MemoizeIt setCallGraph(Graph<String> callGraph) {
+ this.callGraph = callGraph;
+ return this;
+ }
+
+ private Method getMethodByName(String name) {
+ try {
+ return this.methods.stream()
+ .filter(method -> method.getName().equals(name))
+ .findAny().get();
+ } catch (Exception ex) {
+ return null;
}
-
- private Collection<Method> getIndirectCallees(List<Node<String>> visited, String rootPackage, Node<String> node) {
- Collection<Method> cluster = new ArrayList<>();
- Collection<Node<String>> directCallees = node.getLinks();
- for (Node<String> directCallee : directCallees) {
- if (visited.contains(directCallee)) {
- continue;
- }
- visited.add(directCallee);
- this.methods.stream()
- .filter(method -> method.getName().equals(directCallee.getContent()))
- .findAny()
- .ifPresent(callee -> {
- String calleePackage = callee.getName().substring(0, callee.getName().lastIndexOf("."));
- if (calleePackage.equals(rootPackage)) {
- cluster.add(callee);
- }
- });
- cluster.addAll(getIndirectCallees(visited, rootPackage, directCallee));
+ }
+
+ // 3.1 time and frequency profiling
+ private void filterInitialCandidates() {
+ LOGGER.log(Level.INFO, "Fitering {0} initial candidates by frequency and average execution time", this.methods.size());
+ this.methods.removeIf(method -> method.getOccurrencesSize() < this.minimumMethodCalls || method.getAverageExecutionTime() < this.minimumExecutionTime);
+ LOGGER.log(Level.INFO, "Calculating representativity of {0} methods", this.methods.size());
+ Collection<Node<String>> roots = this.callGraph.getRoots();
+ roots.stream().forEach(root -> {
+ Method method = getMethodByName(root.getContent());
+ if (method == null) {
+ return;
+ }
+ if (method.getRepresentativeness() != 0) {
+ return;
+ }
+ method.setRepresentativeness(1);
+ long rootAverageExecutionTime = method.getAverageExecutionTime();
+ root.getLinks().stream().forEach(new Consumer<Node<String>>() {
+
+ private final Collection<Node<String>> visited = new ArrayList<>();
+
+ @Override
+ public void accept(Node<String> node) {
+ if (visited.contains(node)) {
+ return;
+ }
+ visited.add(node);
+ Method callee = getMethodByName(node.getContent());
+ if (callee != null && callee.getRepresentativeness() == 0) {
+ callee.setRepresentativeness(callee.getAverageExecutionTime() / rootAverageExecutionTime);
+ }
+ node.getLinks().stream().forEach(this);
}
- return cluster;
+ });
+
+ });
+ this.methods.stream().filter(method -> method.getRepresentativeness() == 0)
+ .forEach(method -> method.setRepresentativeness(1));
+ LOGGER.log(Level.INFO, "Fitering {0} candidates by representativeness", this.methods.size());
+ this.methods.removeIf(method -> method.getRepresentativeness() < this.minimumRelativeTime);
+ }
+
+ private void removeUnusedFields() {
+ LOGGER.log(Level.INFO, "Removing unused fields from {0} methods", this.methods.size());
+ this.methods.forEach(method -> method.removeUnusedFields(this.callGraph.getNode(method.getName())));
+ }
+
+ // 3.2 input-output profiling
+ private void refineCandidates() {
+ refineCandidates(true);
+ }
+
+ private void refineCandidates(boolean iteratively) {
+ LOGGER.log(Level.INFO, "Refining {0} candidates", this.methods.size());
+ this.methods.sort(Comparator.comparingInt(Method::getOccurrencesSize));
+ this.methods.removeIf(method -> iteratively ? refineCandidateIteratively(method) : refineCandidateExhaustively(method));
+ }
+
+ private boolean refineCandidateExhaustively(Method method) {
+ return refineCandidate(method, Integer.MAX_VALUE);
+ }
+
+ private boolean refineCandidateIteratively(Method method) {
+ LOGGER.log(Level.INFO, "Iteratively refining {0}", method);
+ int depth = 1;
+ while (!method.wasFullyExplored()) {
+ LOGGER.log(Level.INFO, "Exploring depth {0}", depth);
+ boolean refineCandidate = refineCandidate(method, depth);
+ if (refineCandidate) {
+ LOGGER.log(Level.INFO, "Removing candidate");
+ return true;
+ }
+ depth *= 2;
}
-
- private Collection<Method> getTreeCluster(List<Node<String>> visited, Method root) {
- Collection<Method> cluster = new ArrayList<>();
- cluster.add(root);
- String rootPackage = root.getName().substring(0, root.getName().lastIndexOf("."));
- Node<String> node = this.callGraph.getNode(root.getName());
- if (node == null) {
- return cluster;
- }
- visited.add(node);
- Collection<Node<String>> directCallees = node.getLinks();
- for (Node<String> directCallee : directCallees) {
- if (visited.contains(directCallee)) {
- continue;
- }
- visited.add(directCallee);
- this.methods.stream()
- .filter(method -> method.getName().equals(directCallee.getContent()))
- .findAny()
- .ifPresent(cluster::add);
- cluster.addAll(getIndirectCallees(visited, rootPackage, directCallee));
- }
- return cluster;
+ return false;
+ }
+
+ private boolean refineCandidate(Method method, int depth) {
+ int occurrencesSize = method.getOccurrencesSize();
+ method.groupByParameter(depth);
+ int distinctOccurrencesSize = method.getDistinctOccurrencesSize();
+ if (occurrencesSize == distinctOccurrencesSize) {
+ return true;
}
-
- private List<Collection<Method>> clusterMethods() {
- List<Method> methods = new ArrayList<>(this.methods);
- List<Collection<Method>> clusters = new ArrayList<>();
- List<Node<String>> visited = new ArrayList<>();
- while (!methods.isEmpty()) {
- Method method = methods.remove(0);
- Collection<Method> treeCluster = getTreeCluster(visited, method);
- methods.removeAll(treeCluster);
- clusters.add(treeCluster);
- }
- return clusters;
- }
-
- private void rankClusters(List<Collection<Method>> clusters) {
- Map<Collection<Method>, Double> clusterHasSavedTime = clusters.stream()
- .collect(Collectors.toMap(
- cluster -> cluster,
- cluster -> cluster.stream().map(method -> method.getSavedTime()).max(Double::compare).get()));
-
- Collections.sort(clusters, (cluster1, cluster2)
- -> (Double.compare(clusterHasSavedTime.get(cluster2), clusterHasSavedTime.get(cluster1))));
+ if (method.isChangeable()) {
+ return true;
}
-
-// 3.3 clustering and ranking
- private void printClusters(boolean shouldRank) {
- LOGGER.log(Level.INFO, "Clustering {0} cacheable methods", this.methods.size());
- List<Collection<Method>> clusters = clusterMethods();
- if (shouldRank) {
- LOGGER.log(Level.INFO, "Ranking {0} clusters", clusters.size());
- rankClusters(clusters);
- }
- for (int i = 0; i < clusters.size(); i++) {
- Collection<Method> cluster = clusters.get(i);
- System.out.println("Cluster#" + i);
- cluster.forEach(method -> {
- System.out.println("\t" + method.getName());
- System.out.println("\tOccurrences " + method.getOccurrencesSize() + "(" + method.getDistinctOccurrencesSize() + ") Representativeness " + method.getRepresentativeness() + " ExecutionTime " + method.getTotalExecutionTime() + "(" + method.getAverageExecutionTime() + ") PotentialHitRatio " + method.getPotentialHitRatio() + " SavedTime " + method.getSavedTime());
- suggestImplementation(method);
- });
- }
- }
-
- private void printClusters() {
- printClusters(true);
- }
-
- public static void suggestImplementation(Method method) {
- Map<String, CachePerformance> cachingStrategyHasPerformance = method.simulateCachingStrategies();
- CachePerformance globalMultiCachePerformance = cachingStrategyHasPerformance.get("globalMultiCache");
- CachePerformance globalSingleCachePerformance = cachingStrategyHasPerformance.get("globalSingleCache");
- CachePerformance instanceMultiCachePerformance = cachingStrategyHasPerformance.get("instanceMultiCache");
- CachePerformance instanceSingleCachePerformance = cachingStrategyHasPerformance.get("instanceSingleCache");
- StringBuilder stringBuilder = new StringBuilder();
- stringBuilder.append("\t");
- stringBuilder.append("GS: ");
- stringBuilder.append("R").append(globalSingleCachePerformance.getRoundedHitRatio());
- stringBuilder.append(" * ").append(globalSingleCachePerformance);
- stringBuilder.append(" | IS: ");
- stringBuilder.append("R").append(instanceSingleCachePerformance.getRoundedHitRatio());
- stringBuilder.append(" * ").append(instanceSingleCachePerformance);
- stringBuilder.append(" | GM: ");
- stringBuilder.append("R").append(globalMultiCachePerformance.getRoundedHitRatio());
- stringBuilder.append(" * ").append(globalMultiCachePerformance);
- stringBuilder.append(" | IM: ");
- stringBuilder.append("R").append(instanceMultiCachePerformance.getRoundedHitRatio());
- stringBuilder.append(" * ").append(instanceMultiCachePerformance);
- System.out.println(stringBuilder);
- if (globalSingleCachePerformance.getRoundedHitRatio() >= 50) {
- System.out.println("\tsingle, global");
- } else if (instanceSingleCachePerformance.getRoundedHitRatio() >= 50) {
- System.out.println("\tsingle, instance");
- } else if (globalMultiCachePerformance.getRoundedHitRatio() >= 50) {
- System.out.println("\tmulti, global");
- } else if (instanceMultiCachePerformance.getRoundedHitRatio() >= 50) {
- System.out.println("\tmulti, instance");
- } else {
- System.out.println("\tnone");
- }
- }
-
-// 3.4 suggest cache implementation
- public void suggestImplementations() {
- if (this.methods == null || this.methods.isEmpty()) {
- throw new RuntimeException("Empty execution traces");
- }
- LOGGER.log(Level.INFO, "Suggesting caching implementation");
- this.methods.forEach(method -> {
- System.out.println(method.getName());
- suggestImplementation(method);
+ return method.getPotentialHitRatio() < this.minimumHitRatio;
+ }
+
+ private Collection<Method> getIndirectCallees(List<Node<String>> visited, String rootPackage, Node<String> node) {
+ Collection<Method> cluster = new ArrayList<>();
+ Collection<Node<String>> directCallees = node.getLinks();
+ for (Node<String> directCallee : directCallees) {
+ if (visited.contains(directCallee)) {
+ continue;
+ }
+ visited.add(directCallee);
+ this.methods.stream()
+ .filter(method -> method.getName().equals(directCallee.getContent()))
+ .findAny()
+ .ifPresent(callee -> {
+ String calleePackage = callee.getName().substring(0, callee.getName().lastIndexOf("."));
+ if (calleePackage.equals(rootPackage)) {
+ cluster.add(callee);
+ }
});
+ cluster.addAll(getIndirectCallees(visited, rootPackage, directCallee));
}
-
- public void removeChangeableMethods() {
- removeChangeableMethods(false);
- }
-
- public void removeChangeableMethods(boolean iteratively) {
- if (this.methods == null || this.methods.isEmpty()) {
- throw new RuntimeException("Empty execution traces");
- }
- if (this.callGraph == null) {
- throw new RuntimeException("Call Graph not set");
- }
- filterInitialCandidates();
- removeUnusedFields();
- refineCandidates(iteratively);
+ return cluster;
+ }
+
+ private Collection<Method> getTreeCluster(List<Node<String>> visited, Method root) {
+ Collection<Method> cluster = new ArrayList<>();
+ cluster.add(root);
+ String rootPackage = root.getName().substring(0, root.getName().lastIndexOf("."));
+ Node<String> node = this.callGraph.getNode(root.getName());
+ if (node == null) {
+ return cluster;
}
-
- public void suggestCachingImplementations() {
- suggestCachingImplementations(true);
+ visited.add(node);
+ Collection<Node<String>> directCallees = node.getLinks();
+ for (Node<String> directCallee : directCallees) {
+ if (visited.contains(directCallee)) {
+ continue;
+ }
+ visited.add(directCallee);
+ this.methods.stream()
+ .filter(method -> method.getName().equals(directCallee.getContent()))
+ .findAny()
+ .ifPresent(cluster::add);
+ cluster.addAll(getIndirectCallees(visited, rootPackage, directCallee));
}
-
- public void suggestCachingImplementations(boolean shouldRank) {
- if (this.methods == null || this.methods.isEmpty()) {
- throw new RuntimeException("Empty execution traces");
- }
- if (this.callGraph == null) {
- throw new RuntimeException("Call Graph not set");
- }
- printClusters(shouldRank);
+ return cluster;
+ }
+
+ public List<Collection<Method>> clusterMethods() {
+ List<Method> methods = new ArrayList<>(this.methods);
+ List<Collection<Method>> clusters = new ArrayList<>();
+ List<Node<String>> visited = new ArrayList<>();
+ while (!methods.isEmpty()) {
+ Method method = methods.remove(0);
+ Collection<Method> treeCluster = getTreeCluster(visited, method);
+ methods.removeAll(treeCluster);
+ clusters.add(treeCluster);
}
-
- public void run() {
- run(false, true);
+ return clusters;
+ }
+
+ public void rankClusters(List<Collection<Method>> clusters) {
+ Map<Collection<Method>, Double> clusterHasSavedTime = clusters.stream()
+ .collect(Collectors.toMap(
+ cluster -> cluster,
+ cluster -> cluster.stream().map(Method::getSavedTime).max(Double::compare).get()));
+
+ clusters.sort((cluster1, cluster2) -> (Double.compare(clusterHasSavedTime.get(cluster2), clusterHasSavedTime.get(cluster1))));
+ }
+
+ // 3.3 clustering and ranking
+ private void printClusters(boolean shouldRank) {
+ LOGGER.log(Level.INFO, "Clustering {0} cacheable methods", this.methods.size());
+ List<Collection<Method>> clusters = clusterMethods();
+ if (shouldRank) {
+ LOGGER.log(Level.INFO, "Ranking {0} clusters", clusters.size());
+ rankClusters(clusters);
}
-
- public void run(boolean iteratively, boolean shouldRank) {
- if (this.methods == null || this.methods.isEmpty()) {
- throw new RuntimeException("Empty execution traces");
- }
- if (this.callGraph == null) {
- throw new RuntimeException("Call Graph not set");
- }
- filterInitialCandidates();
- removeUnusedFields();
- refineCandidates(iteratively);
- printClusters(shouldRank);
+ for (int i = 0; i < clusters.size(); i++) {
+ Collection<Method> cluster = clusters.get(i);
+ System.out.println("Cluster#" + i);
+ cluster.forEach(method -> {
+ System.out.println("\t" + method.getName());
+ System.out.println("\tOccurrences " + method.getOccurrencesSize() + "(" + method.getDistinctOccurrencesSize() + ") Representativeness " + method.getRepresentativeness() + " ExecutionTime " + method.getTotalExecutionTime() + "(" + method.getAverageExecutionTime() + ") PotentialHitRatio " + method.getPotentialHitRatio() + " SavedTime " + method.getSavedTime());
+ suggestImplementation(method);
+ });
}
+ }
+
+ private void printClusters() {
+ printClusters(true);
+ }
+
+ // 3.4 suggest cache implementation
+ public void suggestImplementations() {
+ if (this.methods == null || this.methods.isEmpty()) throw new RuntimeException("Empty execution traces");
+ LOGGER.log(Level.INFO, "Suggesting caching implementation");
+ this.methods.forEach(method -> {
+ System.out.println(method.getName());
+ suggestImplementation(method);
+ });
+ }
+
+ public void removeChangeableMethods() {
+ removeChangeableMethods(false);
+ }
+
+ public void removeChangeableMethods(boolean iteratively) {
+ if (this.methods == null || this.methods.isEmpty()) throw new RuntimeException("Empty execution traces");
+ if (this.callGraph == null) throw new RuntimeException("Call Graph not set");
+ filterInitialCandidates();
+ removeUnusedFields();
+ refineCandidates(iteratively);
+ }
+
+ public void suggestCachingImplementations() {
+ suggestCachingImplementations(true);
+ }
+
+ public void suggestCachingImplementations(boolean shouldRank) {
+ if (this.methods == null || this.methods.isEmpty()) throw new RuntimeException("Empty execution traces");
+ if (this.callGraph == null) throw new RuntimeException("Call Graph not set");
+ printClusters(shouldRank);
+ }
+
+ public void run() {
+ run(false, true);
+ }
+
+ public void run(boolean iteratively, boolean shouldRank) {
+ if (this.methods == null || this.methods.isEmpty()) throw new RuntimeException("Empty execution traces");
+ if (this.callGraph == null) throw new RuntimeException("Call Graph not set");
+ filterInitialCandidates();
+ removeUnusedFields();
+ refineCandidates(iteratively);
+ printClusters(shouldRank);
+ }
}
src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java 396(+188 -208)
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
index da697d7..eff701c 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
@@ -1,228 +1,208 @@
-/*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
package br.ufrgs.inf.prosoft.memoizeit;
import br.ufrgs.inf.prosoft.cache.CachePerformance;
import br.ufrgs.inf.prosoft.cache.MultiCache;
import br.ufrgs.inf.prosoft.cache.SingleCache;
import br.ufrgs.inf.prosoft.memoizeit.graph.Node;
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.List;
-import java.util.Map;
-import java.util.Objects;
+
+import java.util.*;
import java.util.function.Consumer;
import java.util.logging.Level;
import java.util.logging.Logger;
+import java.util.stream.Stream;
-/**
- *
- * @author romulo
- */
public class Method {
- private static final Logger LOGGER = Logger.getLogger(Method.class.getName());
-
- private final String name;
- private final List<Occurrence> occurrences;
- private double representativeness;
- private Map<String, List<Occurrence>> groupByParameter;
- private Boolean fullyExplored;
- private final boolean isStatic;
-
- public Method(String name, boolean isStatic, List<Occurrence> occurrences) {
- this.name = name;
- this.occurrences = occurrences;
- this.fullyExplored = false;
- this.isStatic = isStatic;
- }
-
- public String getName() {
- return name;
- }
-
- public int getOccurrencesSize() {
- return this.occurrences.size();
- }
-
- public void setRepresentativeness(double representativeness) {
- this.representativeness = representativeness;
- }
-
- public double getRepresentativeness() {
- return representativeness;
- }
-
- public int getDistinctOccurrencesSize() {
- return this.groupByParameter.size();
- }
-
- public long getTotalExecutionTime() {
- return this.occurrences.stream()
- .map(Occurrence::getExecutionTime)
- .reduce(Long::sum).get();
- }
-
- public long getAverageExecutionTime() {
- return getTotalExecutionTime() / this.occurrences.size();
- }
-
- public double getSavedTime() {
- return getAverageExecutionTime() * getPotentialHitRatio();
- }
-
- protected boolean wasFullyExplored() {
- return this.fullyExplored;
- }
-
- protected void groupByParameter(int depth) {
- LOGGER.log(Level.FINE, "\tGrouping by parameters {0} occurrences of {1}", new Object[]{this.name, this.occurrences.size()});
- this.groupByParameter = new HashMap<>();
- this.occurrences.stream().parallel().forEach(new Consumer<Occurrence>() {
- int i = 0;
-
- @Override
- public void accept(Occurrence occurrence) {
- String verbose = System.getenv("TRACER_VERBOSE");
- if (verbose != null && verbose.equals("true")) {
- System.out.print(".");
- System.out.flush();
- if (++i % 100 == 0) {
- System.out.println();
- }
- }
- if (depth < Integer.MAX_VALUE) {
- OccurrenceConcrete thisOccurrence = occurrence.getConcrete();
- OccurrenceConcrete truncated = thisOccurrence.getView(depth);
- Method.this.fullyExplored = truncated == thisOccurrence;
- occurrence = truncated;
- }
- String parameters = occurrence.getParameters().toString();
- synchronized (Method.this.groupByParameter) {
- try {
- Method.this.groupByParameter.get(parameters).add(occurrence);
- } catch (Exception e) {
- List<Occurrence> occurrences = new ArrayList<>();
- occurrences.add(occurrence);
- Method.this.groupByParameter.put(parameters, occurrences);
- }
- }
- }
- });
- }
-
- protected void groupByParameter() {
- groupByParameter(Integer.MAX_VALUE);
- }
-
- protected boolean isChangeful() {
- for (List<Occurrence> occurrences : this.groupByParameter.values()) {
- if (occurrences.size() == 1) {
- continue;
- }
- Occurrence firstOccurrence = occurrences.get(0);
- if (occurrences.stream()
- .anyMatch(occurrence -> occurrence.getReturnValue() != null
- && !occurrence.getReturnValue().equals(firstOccurrence.getReturnValue()))) {
- return true;
- }
+ private static final Logger LOGGER = Logger.getLogger(Method.class.getName());
+
+ private final String name;
+ private final List<Occurrence> occurrences;
+ private final boolean isStatic;
+ private double representativeness;
+ private Map<String, List<Occurrence>> groupByParameter;
+ private Boolean fullyExplored;
+
+ public Method(String name, boolean isStatic, List<Occurrence> occurrences) {
+ this.name = name;
+ this.occurrences = occurrences;
+ this.fullyExplored = false;
+ this.isStatic = isStatic;
+ }
+
+ public String getName() {
+ return name;
+ }
+
+ public int getOccurrencesSize() {
+ return this.occurrences.size();
+ }
+
+ public Stream<Occurrence> occurrences() {
+ return this.occurrences.stream();
+ }
+
+ public double getRepresentativeness() {
+ return representativeness;
+ }
+
+ public void setRepresentativeness(double representativeness) {
+ this.representativeness = representativeness;
+ }
+
+ public int getDistinctOccurrencesSize() {
+ return this.groupByParameter.size();
+ }
+
+ public long getTotalExecutionTime() {
+ return this.occurrences.stream()
+ .map(Occurrence::getExecutionTime)
+ .reduce(Long::sum).get();
+ }
+
+ public long getAverageExecutionTime() {
+ return getTotalExecutionTime() / this.occurrences.size();
+ }
+
+ public double getSavedTime() {
+ return getAverageExecutionTime() * getPotentialHitRatio();
+ }
+
+ protected boolean wasFullyExplored() {
+ return this.fullyExplored;
+ }
+
+ protected void groupByParameter(int depth) {
+ LOGGER.log(Level.FINE, "\tGrouping by parameters {0} occurrences of {1}", new Object[]{this.name, this.occurrences.size()});
+ this.groupByParameter = new HashMap<>();
+ this.occurrences.stream().parallel().forEach(new Consumer<Occurrence>() {
+ int i = 0;
+
+ @Override
+ public void accept(Occurrence occurrence) {
+ String verbose = System.getenv("TRACER_VERBOSE");
+ if (verbose != null && verbose.equals("true")) {
+ System.out.print(".");
+ System.out.flush();
+ if (++i % 100 == 0) System.out.println();
}
- return false;
- }
-
- protected double getPotentialHitRatio() {
- double potentialHitRatio = this.groupByParameter.entrySet().stream().map(entry -> entry.getValue().size()).reduce(Integer::sum).get();
- potentialHitRatio = (potentialHitRatio - this.groupByParameter.size()) / potentialHitRatio;
- return potentialHitRatio;
- }
-
- protected void removeUnusedFields(Node<String> methodNode) {
- LOGGER.log(Level.FINE, "\tRemoving unused fields of {0} occurrences of {1}", new Object[]{this.occurrences.size(), this.name});
- if (methodNode == null) {
- LOGGER.log(Level.WARNING, "methodNode null: {0}", this.name);
- return;
+ if (depth < Integer.MAX_VALUE) {
+ OccurrenceConcrete thisOccurrence = occurrence.getConcrete();
+ OccurrenceConcrete truncated = thisOccurrence.getView(depth);
+ Method.this.fullyExplored = truncated == thisOccurrence;
+ occurrence = truncated;
}
- this.occurrences.stream().parallel()
- .forEach(new Consumer<Occurrence>() {
- private int i = 1;
-
- @Override
- public void accept(Occurrence occurrence) {
- String verbose = System.getenv("TRACER_VERBOSE");
- if (verbose != null && verbose.equals("true")) {
- System.out.print(".");
- if (i++ % 100 == 0) {
- System.out.println();
- }
- }
- occurrence.removeUnusedFields(methodNode);
- }
- });
- }
-
- protected Map<String, CachePerformance> simulateCachingStrategies() {
- Map<String, CachePerformance> cachingStrategyHasPerformance = new HashMap<>();
- CachePerformance globalMultiCachePerformance = new CachePerformance();
- CachePerformance globalSingleCachePerformance = new CachePerformance();
- CachePerformance instanceMultiCachePerformance = new CachePerformance();
- CachePerformance instanceSingleCachePerformance = new CachePerformance();
- cachingStrategyHasPerformance.put("globalMultiCache", globalMultiCachePerformance);
- cachingStrategyHasPerformance.put("globalSingleCache", globalSingleCachePerformance);
- cachingStrategyHasPerformance.put("instanceMultiCache", instanceMultiCachePerformance);
- cachingStrategyHasPerformance.put("instanceSingleCache", instanceSingleCachePerformance);
- MultiCache globalMultiCache = new MultiCache(globalMultiCachePerformance);
- SingleCache globalSingleCache = new SingleCache(globalSingleCachePerformance);
- Map<String, MultiCache> instanceHasMultiCache = new HashMap<>();
- Map<String, SingleCache> instanceHasSingleCache = new HashMap<>();
- for (Occurrence occurrence : this.occurrences) {
- if (!this.isStatic) {
- MultiCache instanceMultiCache = instanceHasMultiCache.get(occurrence.getInstance());
- if (instanceMultiCache == null) {
- instanceMultiCache = new MultiCache(instanceMultiCachePerformance);
- instanceHasMultiCache.put(occurrence.getInstance(), instanceMultiCache);
- }
- occurrence.simulateCaching(instanceMultiCache);
- SingleCache instanceSingleCache = instanceHasSingleCache.get(occurrence.getInstance());
- if (instanceSingleCache == null) {
- instanceSingleCache = new SingleCache(instanceSingleCachePerformance);
- instanceHasSingleCache.put(occurrence.getInstance(), instanceSingleCache);
- }
- occurrence.simulateCaching(instanceSingleCache);
- }
- occurrence.simulateCaching(globalMultiCache);
- occurrence.simulateCaching(globalSingleCache);
+ String parameters = occurrence.getParameters().toString();
+ synchronized (Method.this.groupByParameter) {
+ try {
+ Method.this.groupByParameter.get(parameters).add(occurrence);
+ } catch (Exception e) {
+ List<Occurrence> occurrences = new ArrayList<>();
+ occurrences.add(occurrence);
+ Method.this.groupByParameter.put(parameters, occurrences);
+ }
}
- return cachingStrategyHasPerformance;
- }
-
- @Override
- public int hashCode() {
- int hash = 5;
- hash = 37 * hash + Objects.hashCode(this.name);
- return hash;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj) {
- return true;
+ }
+ });
+ }
+
+ protected void groupByParameter() {
+ groupByParameter(Integer.MAX_VALUE);
+ }
+
+ protected boolean isChangeable() {
+ for (List<Occurrence> occurrences : this.groupByParameter.values()) {
+ if (occurrences.size() == 1) continue;
+ Occurrence firstOccurrence = occurrences.get(0);
+ if (occurrences.stream().anyMatch(occurrence -> occurrence.getReturnValue() != null
+ && !occurrence.getReturnValue().equals(firstOccurrence.getReturnValue()))) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ protected double getPotentialHitRatio() {
+ double potentialHitRatio = this.groupByParameter.values().stream().map(List::size).reduce(Integer::sum).get();
+ potentialHitRatio = (potentialHitRatio - this.groupByParameter.size()) / potentialHitRatio;
+ return potentialHitRatio;
+ }
+
+ protected void removeUnusedFields(Node<String> methodNode) {
+ LOGGER.log(Level.FINE, "\tRemoving unused fields of {0} occurrences of {1}", new Object[]{this.occurrences.size(), this.name});
+ if (methodNode == null) {
+ LOGGER.log(Level.WARNING, "methodNode null: {0}", this.name);
+ return;
+ }
+ this.occurrences.stream().parallel()
+ .forEach(new Consumer<Occurrence>() {
+ private int i = 1;
+
+ @Override
+ public void accept(Occurrence occurrence) {
+ String verbose = System.getenv("TRACER_VERBOSE");
+ if (verbose != null && verbose.equals("true")) {
+ System.out.print(".");
+ if (i++ % 100 == 0) System.out.println();
+ }
+ occurrence.removeUnusedFields(methodNode);
}
- if (obj == null) {
- return false;
+ });
+ }
+
+ protected Map<String, CachePerformance> simulateCachingStrategies() {
+ Map<String, CachePerformance> cachingStrategyHasPerformance = new HashMap<>();
+ CachePerformance globalMultiCachePerformance = new CachePerformance();
+ CachePerformance globalSingleCachePerformance = new CachePerformance();
+ CachePerformance instanceMultiCachePerformance = new CachePerformance();
+ CachePerformance instanceSingleCachePerformance = new CachePerformance();
+ cachingStrategyHasPerformance.put("globalMultiCache", globalMultiCachePerformance);
+ cachingStrategyHasPerformance.put("globalSingleCache", globalSingleCachePerformance);
+ cachingStrategyHasPerformance.put("instanceMultiCache", instanceMultiCachePerformance);
+ cachingStrategyHasPerformance.put("instanceSingleCache", instanceSingleCachePerformance);
+ MultiCache globalMultiCache = new MultiCache(globalMultiCachePerformance);
+ SingleCache globalSingleCache = new SingleCache(globalSingleCachePerformance);
+ Map<String, MultiCache> instanceHasMultiCache = new HashMap<>();
+ Map<String, SingleCache> instanceHasSingleCache = new HashMap<>();
+ for (Occurrence occurrence : this.occurrences) {
+ if (!this.isStatic) {
+ MultiCache instanceMultiCache = instanceHasMultiCache.get(occurrence.getInstance());
+ if (instanceMultiCache == null) {
+ instanceMultiCache = new MultiCache(instanceMultiCachePerformance);
+ instanceHasMultiCache.put(occurrence.getInstance(), instanceMultiCache);
}
- if (!(obj instanceof Method)) {
- return false;
+ occurrence.simulateCaching(instanceMultiCache);
+ SingleCache instanceSingleCache = instanceHasSingleCache.get(occurrence.getInstance());
+ if (instanceSingleCache == null) {
+ instanceSingleCache = new SingleCache(instanceSingleCachePerformance);
+ instanceHasSingleCache.put(occurrence.getInstance(), instanceSingleCache);
}
- Method method = (Method) obj;
- return this.name.equals(method.name);
- }
-
- @Override
- public String toString() {
- return this.name;
- }
+ occurrence.simulateCaching(instanceSingleCache);
+ }
+ occurrence.simulateCaching(globalMultiCache);
+ occurrence.simulateCaching(globalSingleCache);
+ }
+ return cachingStrategyHasPerformance;
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 5;
+ hash = 37 * hash + Objects.hashCode(this.name);
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) return true;
+ if (obj == null) return false;
+ if (!(obj instanceof Method)) return false;
+ Method method = (Method) obj;
+ return this.name.equals(method.name);
+ }
+
+ @Override
+ public String toString() {
+ return this.name;
+ }
}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Occurrence.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Occurrence.java
index 93c66e7..6fc26d7 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Occurrence.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Occurrence.java
@@ -8,6 +8,7 @@ package br.ufrgs.inf.prosoft.memoizeit;
import br.ufrgs.inf.prosoft.cache.Cache;
import br.ufrgs.inf.prosoft.cache.KeyNotFoundException;
import br.ufrgs.inf.prosoft.memoizeit.graph.Node;
+
import java.util.List;
import java.util.Objects;
@@ -35,11 +36,11 @@ public abstract class Occurrence {
public abstract List<Parameter> getParameters();
- protected long getStartTime() {
+ public long getStartTime() {
return startTime;
}
- protected long getEndTime() {
+ public long getEndTime() {
return endTime;
}