Details
diff --git a/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/CallGraphReader.java b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/CallGraphReader.java
new file mode 100644
index 0000000..c383207
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/CallGraphReader.java
@@ -0,0 +1,63 @@
+/*
+ * 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.approachescomparison.adapter;
+
+import br.ufrgs.inf.prosoft.memoizeit.graph.Graph;
+import br.ufrgs.inf.prosoft.memoizeit.graph.Node;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.logging.Level;
+import java.util.logging.Logger;
+
+/**
+ *
+ * @author romulo
+ */
+public class CallGraphReader {
+
+ public static Graph<String> parseFile(String path) {
+ try {
+ Map<String, Node<String>> callHasNode = new HashMap<>();
+ List<String> lines = Files.readAllLines(Paths.get(path));
+ for (String line : lines) {
+ if (line.charAt(0) != 'M') {
+ continue;
+ }
+ int indexOfSpace = line.indexOf(" ");
+ String callerString = line.substring(2, indexOfSpace);
+ String calleeString = line.substring(indexOfSpace + 4, line.length());
+ callerString = reshapeMethodName(callerString);
+ calleeString = reshapeMethodName(calleeString);
+ Node<String> callerNode = callHasNode.get(callerString);
+ if (callerNode == null) {
+ callerNode = new Node<>(callerString);
+ callHasNode.put(callerString, callerNode);
+ }
+ Node<String> calleeNode = callHasNode.get(calleeString);
+ if (calleeNode == null) {
+ calleeNode = new Node<>(calleeString);
+ callHasNode.put(calleeString, calleeNode);
+ }
+ callerNode.addLink(calleeNode);
+ }
+ return new Graph<>(callHasNode);
+ } catch (IOException ex) {
+ Logger.getLogger(CallGraphReader.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ return new Graph<>();
+ }
+
+ private static String reshapeMethodName(String methodName) {
+ return methodName.substring(0, methodName.indexOf("("))
+ .replace(":", ".")
+ .replace("$", ".");
+ }
+
+}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/Main.java b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/Main.java
index 9ed36c0..19fc7e8 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/Main.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/Main.java
@@ -7,6 +7,7 @@ package br.ufrgs.inf.prosoft.approachescomparison.adapter;
import br.ufrgs.inf.prosoft.memoizeit.MemoizeIt;
import br.ufrgs.inf.prosoft.memoizeit.Method;
+import br.ufrgs.inf.prosoft.memoizeit.graph.Graph;
import br.ufrgs.inf.prosoft.trace.Trace;
import java.util.List;
@@ -17,28 +18,22 @@ import java.util.List;
public class Main {
public static void main(String[] args) {
- String path = null;
- long totalExecutionTime = 0;
- if (args.length < 1) {
- System.err.println("No path provided");
+ String tracePath = null;
+ String callGraphPath = null;
+ if (args.length < 2) {
+ System.err.println("<TracePath> <CallGraphPath>");
System.exit(1);
} else {
- path = args[0];
- if (args.length < 2) {
- System.err.println("No execution time provided");
- try {
- totalExecutionTime = Long.parseLong(args[1]);
- } catch (NumberFormatException e) {
- System.err.println("Argument must be a long number");
- System.exit(1);
- }
- }
+ tracePath = args[0];
+ callGraphPath = args[1];
}
- List<Trace> traces = TraceReader.readFile(path);
- MemoizeIt memoizeIt = new MemoizeIt(totalExecutionTime);
+ Graph<String> graph = CallGraphReader.parseFile(callGraphPath);
+ List<Trace> traces = TraceReader.parseFile(tracePath);
List<Method> methods = TraceReader.groupByMethods(traces);
+ MemoizeIt memoizeIt = new MemoizeIt();
+ memoizeIt.setCallGraph(graph);
memoizeIt.setMethods(methods);
- memoizeIt.removeChangefulMethods();
+ memoizeIt.run();
methods.forEach(System.out::println);
}
}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/TraceReader.java b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/TraceReader.java
index 99bb6bd..c23268b 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/TraceReader.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/TraceReader.java
@@ -28,7 +28,7 @@ import java.util.logging.Logger;
*/
public class TraceReader {
- public static List<Trace> readFile(String path) {
+ public static List<Trace> parseFile(String path) {
List<Trace> traces = new ArrayList<>();
try {
List<String> lines = Files.readAllLines(Paths.get(path));
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Graph.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Graph.java
new file mode 100644
index 0000000..9296ec9
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Graph.java
@@ -0,0 +1,31 @@
+/*
+ * 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.graph;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ *
+ * @author romulo
+ */
+public class Graph<U> {
+
+ private final Map<U, Node<U>> contentHasNode;
+
+ public Graph() {
+ this.contentHasNode = new HashMap<>();
+ }
+
+ public Graph(Map<U, Node<U>> contentHasNode) {
+ this.contentHasNode = contentHasNode;
+ }
+
+ public Node<U> getNode(U content) {
+ return this.contentHasNode.get(content);
+ }
+
+}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Node.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Node.java
new file mode 100644
index 0000000..3cf33fb
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/graph/Node.java
@@ -0,0 +1,59 @@
+/*
+ * 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.graph;
+
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Objects;
+
+/**
+ *
+ * @author romulo
+ */
+public class Node<U> {
+
+ private final U content;
+ private final Collection<Node<U>> links;
+
+ public Node(U content) {
+ this.content = content;
+ this.links = new HashSet<>();
+ }
+
+ public U getContent() {
+ return content;
+ }
+
+ public Node addLink(Node node) {
+ links.add(node);
+ return this;
+ }
+
+ public Collection<Node<U>> getLinks() {
+ return links;
+ }
+
+ @Override
+ public int hashCode() {
+ return Objects.hashCode(this.content);
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
+ if (!(obj instanceof Node)) {
+ return false;
+ }
+ Node other = (Node) obj;
+ return this.content.equals(other.content);
+ }
+
+}
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 e0146d3..fda5a8b 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
@@ -6,8 +6,14 @@
package br.ufrgs.inf.prosoft.memoizeit;
import br.ufrgs.inf.prosoft.memoizeit.cache.CachingPerformance;
+import br.ufrgs.inf.prosoft.memoizeit.graph.Graph;
+import br.ufrgs.inf.prosoft.memoizeit.graph.Node;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
import java.util.List;
import java.util.Map;
+import java.util.stream.Collectors;
/**
*
@@ -31,6 +37,8 @@ public class MemoizeIt {
private List<Method> methods;
// Stoping condition to iterative algorithm
private boolean maxDepthReached;
+ // Call Graph
+ private Graph<String> callGraph;
public MemoizeIt() {
this.maxDepthReached = false;
@@ -76,6 +84,11 @@ public class MemoizeIt {
return this;
}
+ public MemoizeIt setCallGraph(Graph<String> callGraph) {
+ this.callGraph = callGraph;
+ return this;
+ }
+
private void estimateTotalProgramExecution() {
this.methods.forEach((method) -> {
this.totalProgramExecution += method.getTotalExecutionTime();
@@ -167,39 +180,91 @@ public class MemoizeIt {
}
}
- public void removeChangefulMethods() {
- if (this.methods.isEmpty()) {
- throw new RuntimeException("Empty execution traces");
+ private Collection<Method> getIndirectCallees(List<Node<String>> visited, String packageName, 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(packageName)) {
+ cluster.add(callee);
+ }
+ });
+ cluster.addAll(getIndirectCallees(visited, packageName, directCallee));
}
- filterInitialCandidates();
- refineCandidatesIteratively();
- rankMethods();
- suggestImplementations();
+ return cluster;
}
-// 3.3 clustering and ranking
- private void rankMethods() {
- rankMethods(true);
+ 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());
+ visited.add(node);
+ Collection<Node<String>> directCallees = node.getLinks();
+ for (Node<String> directCallee : directCallees) {
+ if (visited.contains(directCallee)) {
+ continue;
+ }
+ visited.add(directCallee);
+ Map<String, Method> a = null;
+ this.methods.stream()
+ .filter(method -> method.getName().equals(directCallee.getContent()))
+ .findAny()
+ .ifPresent(cluster::add);
+ cluster.addAll(getIndirectCallees(visited, rootPackage, directCallee));
+ }
+ return cluster;
}
- private void rankMethods(boolean cluster) {
- if (cluster) {
- clusterMethods();
+ 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 clusterMethods() {
+ 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(cluster1), clusterHasSavedTime.get(cluster2))));
}
-// 3.4 suggest cache implementation
- private void suggestImplementations() {
- for (Method method : this.methods) {
- System.out.println(method.getName());
- suggestImplementation(method);
+// 3.3 clustering and ranking
+ private void printClusters(boolean shouldRank) {
+ List<Collection<Method>> clusters = clusterMethods();
+ if (shouldRank) {
+ rankClusters(clusters);
+ }
+ for (int i = 0; i < clusters.size(); i++) {
+ Collection<Method> cluster = clusters.get(i);
+ System.out.println("Cluster#" + i);
+ cluster.forEach(System.out::println);
System.out.println();
}
}
+ private void printClusters() {
+ printClusters(true);
+ }
+
private void suggestImplementation(Method method) {
Map<String, CachingPerformance> cachingStrategyHasPerformance = method.simulateCachingStrategies();
CachingPerformance globalMultiCachePerformance = cachingStrategyHasPerformance.get("globalMultiCache");
@@ -232,4 +297,48 @@ public class MemoizeIt {
System.out.println("none");
}
}
+
+// 3.4 suggest cache implementation
+ private void suggestImplementations() {
+ for (Method method : this.methods) {
+ System.out.println(method.getName());
+ suggestImplementation(method);
+ System.out.println();
+ }
+ }
+
+ public void removeChangefulMethods() {
+ 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();
+ refineCandidatesIteratively();
+ }
+
+ public void suggestCachingImplementations() {
+ 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();
+ suggestImplementations();
+ }
+
+ public void run() {
+ 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();
+ refineCandidatesIteratively();
+ printClusters();
+ suggestImplementations();
+ }
}
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 214aa5a..d330456 100644
--- a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
@@ -46,17 +46,19 @@ public class Method {
}
public long getTotalExecutionTime() {
- long averageExecutionTime = 0;
- for (Occurrence occurrence : this.occurrences) {
- averageExecutionTime += occurrence.getExecutionTime();
- }
- return averageExecutionTime;
+ return this.occurrences.stream()
+ .map(occurrence -> 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;
}
@@ -100,12 +102,8 @@ public class Method {
}
protected double getPotentialHitRatio() {
- double potentialHitRatio = 0;
- for (Map.Entry<String, List<Occurrence>> entry : this.groupByParameter.entrySet()) {
- potentialHitRatio += entry.getValue().size();
- }
+ double potentialHitRatio = this.groupByParameter.entrySet().stream().map(entry -> entry.getValue().size()).reduce(Integer::sum).get();
potentialHitRatio = (potentialHitRatio - this.groupByParameter.size()) / potentialHitRatio;
- this.groupByParameter.clear();
return potentialHitRatio;
}
@@ -153,6 +151,12 @@ public class Method {
@Override
public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null) {
+ return false;
+ }
if (!(obj instanceof Method)) {
return false;
}
