memoizeit
Details
.gitignore 34(+34 -0)
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..4a482b8
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,34 @@
+# ignore eclipse project files
+.project
+.classpath
+
+# ignore Intellij Idea project files
+.idea
+*.iml
+
+# Netbeans
+/nbproject/
+/nbactions.xml
+
+# Netbeans deploy
+/build/
+
+# Maven deploy
+/target/
+
+# Ant deploy
+/dist/
+
+# Class files
+*.class
+
+# Mobile Tools for Java (J2ME)
+.mtj.tmp/
+
+# Package Files #
+*.jar
+*.war
+*.ear
+
+# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
+hs_err_pid*
pom.xml 65(+65 -0)
diff --git a/pom.xml b/pom.xml
new file mode 100644
index 0000000..c86f907
--- /dev/null
+++ b/pom.xml
@@ -0,0 +1,65 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
+ <modelVersion>4.0.0</modelVersion>
+ <groupId>br.ufrgs.inf.prosoft.memoizeit</groupId>
+ <artifactId>MemoizeIt</artifactId>
+ <version>1.0</version>
+ <packaging>jar</packaging>
+ <properties>
+ <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
+ <maven.compiler.source>1.8</maven.compiler.source>
+ <maven.compiler.target>1.8</maven.compiler.target>
+ </properties>
+ <dependencies>
+ <dependency>
+ <groupId>br.ufrgs.inf.prosoft.trace</groupId>
+ <artifactId>Trace</artifactId>
+ <version>1.0</version>
+ </dependency>
+ <!-- https://mvnrepository.com/artifact/com.google.code.gson/gson -->
+ <dependency>
+ <groupId>com.google.code.gson</groupId>
+ <artifactId>gson</artifactId>
+ <version>2.8.5</version>
+ </dependency>
+ </dependencies>
+ <build>
+ <plugins>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-dependency-plugin</artifactId>
+ <executions>
+ <execution>
+ <id>copy</id>
+ <phase>package</phase>
+ <goals>
+ <goal>copy-dependencies</goal>
+ </goals>
+ <configuration>
+ <outputDirectory>
+ ${project.build.directory}/lib
+ </outputDirectory>
+ </configuration>
+ </execution>
+ </executions>
+ </plugin>
+ <plugin>
+ <groupId>org.apache.maven.plugins</groupId>
+ <artifactId>maven-jar-plugin</artifactId>
+ <version>3.1.0</version>
+ <configuration>
+ <archive>
+ <manifest>
+ <addClasspath>true</addClasspath>
+ <classpathPrefix>lib</classpathPrefix>
+ <mainClass>br.ufrgs.inf.prosoft.approachescomparison.adapter.Main</mainClass>
+ </manifest>
+ <manifestEntries>
+ <Class-Path>lib/</Class-Path>
+ </manifestEntries>
+ </archive>
+ </configuration>
+ </plugin>
+ </plugins>
+ </build>
+</project>
\ No newline at end of file
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
new file mode 100644
index 0000000..9ed36c0
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/Main.java
@@ -0,0 +1,44 @@
+/*
+ * 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.MemoizeIt;
+import br.ufrgs.inf.prosoft.memoizeit.Method;
+import br.ufrgs.inf.prosoft.trace.Trace;
+import java.util.List;
+
+/**
+ *
+ * @author romulo
+ */
+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");
+ 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);
+ }
+ }
+ }
+ List<Trace> traces = TraceReader.readFile(path);
+ MemoizeIt memoizeIt = new MemoizeIt(totalExecutionTime);
+ List<Method> methods = TraceReader.groupByMethods(traces);
+ memoizeIt.setMethods(methods);
+ memoizeIt.removeChangefulMethods();
+ 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
new file mode 100644
index 0000000..08c288e
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/approachescomparison/adapter/TraceReader.java
@@ -0,0 +1,71 @@
+/*
+ * 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.Method;
+import br.ufrgs.inf.prosoft.memoizeit.Occurrence;
+import br.ufrgs.inf.prosoft.trace.Trace;
+import com.google.gson.Gson;
+import com.google.gson.JsonSyntaxException;
+import java.io.IOException;
+import java.nio.file.Files;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+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 TraceReader {
+
+ public static List<Trace> readFile(String path) {
+ List<Trace> traces = new ArrayList<>();
+ try {
+ List<String> lines = Files.readAllLines(Paths.get(path));
+ Gson gson = new Gson();
+ for (String line : lines) {
+ try {
+ Trace trace = gson.fromJson(line, Trace.class);
+ traces.add(trace);
+ } catch (JsonSyntaxException e) {
+ System.err.println("Malformed Trace");
+ }
+ }
+ } catch (IOException ex) {
+ Logger.getLogger(TraceReader.class.getName()).log(Level.SEVERE, null, ex);
+ }
+ return traces;
+ }
+
+ public static List<Method> groupByMethods(List<Trace> traces) {
+ Map<String, List<Occurrence>> methodNameHasOccurrences = new HashMap<>();
+ while (!traces.isEmpty()) {
+ Trace trace = traces.remove(0);
+ List<Object> parameters = new ArrayList<>();
+ trace.getParameters().forEach((parameter) -> {
+ parameters.add(parameter.getData());
+ });
+ Occurrence occurrence = new Occurrence(trace.getReturn().getData(), parameters, trace.getStartTime(), trace.getEndTime());
+ try {
+ methodNameHasOccurrences.get(trace.getName()).add(occurrence);
+ } catch (Exception ex) {
+ List<Occurrence> occurrences = new ArrayList<>();
+ occurrences.add(occurrence);
+ methodNameHasOccurrences.put(trace.getName(), occurrences);
+ }
+ }
+ List<Method> methods = new ArrayList<>();
+ methodNameHasOccurrences.entrySet().forEach((entry) -> {
+ methods.add(new Method(entry.getKey(), entry.getValue()));
+ });
+ return methods;
+ }
+}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
new file mode 100644
index 0000000..6d154ee
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/MemoizeIt.java
@@ -0,0 +1,141 @@
+/*
+ * 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 java.util.List;
+
+/**
+ *
+ * @author romulo
+ */
+public class MemoizeIt {
+
+ // Total program execution time
+ private long totalProgramExecution;
+ // Average of all occurrences execution time
+ private double averageProgramExecution;
+ // 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;
+
+ public MemoizeIt() {
+ this.minimumHitRatio = 0.5;
+ this.minimumMethodCalls = 2;
+ this.minimumRelativeTime = 1.0;
+ this.minimumExecutionTime = 5;
+ }
+
+ public MemoizeIt(long totalProgramExecution) {
+ this();
+ this.totalProgramExecution = totalProgramExecution;
+ }
+
+ public MemoizeIt setTotalProgramExecution(long totalProgramExecution) {
+ this.totalProgramExecution = totalProgramExecution;
+ return this;
+ }
+
+ 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;
+ }
+
+ private void estimateTotalProgramExecution() {
+ this.methods.forEach((method) -> {
+ this.totalProgramExecution += method.getTotalExecutionTime();
+ });
+ }
+
+ private void calculateAverageExecutionTime() {
+ this.methods.forEach((method) -> {
+ this.averageProgramExecution += method.getAverageExecutionTime();
+ });
+ this.averageProgramExecution /= this.methods.size();
+ }
+
+// 3.1 time and frequency profiling
+ private void filterInitialCandidates() {
+ if (this.totalProgramExecution == 0) {
+ System.out.println("Warning: total program execution not informed. Using average of calls");
+ calculateAverageExecutionTime();
+ }
+ int i = 0;
+ while (i < this.methods.size()) {
+ Method method = this.methods.get(i);
+ double totalExecutionTime = method.getTotalExecutionTime();
+ double averageExecutionTime = totalExecutionTime / method.getOccurrencesSize();
+ double relativeExecutionTime = this.totalProgramExecution == 0 ? averageExecutionTime / this.averageProgramExecution : totalExecutionTime / this.totalProgramExecution;
+ if (method.getOccurrencesSize() < this.minimumMethodCalls
+ || averageExecutionTime < this.minimumExecutionTime
+ || relativeExecutionTime < this.minimumRelativeTime) {
+ this.methods.remove(method);
+ continue;
+ }
+ i++;
+ }
+ }
+
+// 3.2 input-output profiling
+ private void refineCandidates() {
+ int i = 0;
+ while (i < this.methods.size()) {
+ Method method = this.methods.get(i);
+ int occurrencesSize = method.getOccurrencesSize();
+ method.groupByParameter();
+ int distinctOccurrencesSize = method.getDistinctOccurrencesSize();
+ if (occurrencesSize == distinctOccurrencesSize) {
+ this.methods.remove(i);
+ continue;
+ }
+ if (method.isChangeful()) {
+ this.methods.remove(i);
+ continue;
+ }
+ double potentialHitRatio = method.getPotentialHitRatio();
+ if (potentialHitRatio < this.minimumHitRatio) {
+ this.methods.remove(i);
+ continue;
+ }
+ i++;
+ }
+ }
+
+ public void removeChangefulMethods() {
+ if (this.methods.isEmpty()) {
+ throw new RuntimeException("Empty execution traces");
+ }
+ filterInitialCandidates();
+ refineCandidates();
+ }
+
+}
diff --git a/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
new file mode 100644
index 0000000..edbbbe2
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Method.java
@@ -0,0 +1,110 @@
+/*
+ * 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 java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+
+/**
+ *
+ * @author romulo
+ */
+public class Method {
+
+ private final String name;
+ private final List<Occurrence> occurrences;
+ private Map<String, List<Occurrence>> groupByParameter;
+
+ public Method(String name, List<Occurrence> occurrences) {
+ this.name = name;
+ this.occurrences = occurrences;
+ }
+
+ public int getOccurrencesSize() {
+ return this.occurrences.size();
+ }
+
+ public int getDistinctOccurrencesSize() {
+ return this.groupByParameter.size();
+ }
+
+ public long getTotalExecutionTime() {
+ long averageExecutionTime = 0;
+ for (Occurrence occurrence : this.occurrences) {
+ averageExecutionTime += occurrence.getExecutionTime();
+ }
+ return averageExecutionTime;
+ }
+
+ public long getAverageExecutionTime() {
+ return getTotalExecutionTime() / this.occurrences.size();
+ }
+
+ protected void groupByParameter() {
+ this.groupByParameter = new HashMap<>();
+ while (!this.occurrences.isEmpty()) {
+ Occurrence occurrence = this.occurrences.remove(0);
+ String parameters = occurrence.getParameters().toString();
+ try {
+ this.groupByParameter.get(parameters).add(occurrence);
+ } catch (Exception e) {
+ List<Occurrence> occurrences = new ArrayList<>();
+ occurrences.add(occurrence);
+ this.groupByParameter.put(parameters, occurrences);
+ }
+ }
+ }
+
+ protected boolean isChangeful() {
+ for (Map.Entry<String, List<Occurrence>> entry : this.groupByParameter.entrySet()) {
+ if (entry.getValue().size() == 1) {
+ continue;
+ }
+ Occurrence firstOccurrence = entry.getValue().get(0);
+ for (Occurrence occurrence : entry.getValue()) {
+ if (!occurrence.getReturnValue().equals(firstOccurrence.getReturnValue())) {
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ protected double getPotentialHitRatio() {
+ double potentialHitRatio = 0;
+ for (Map.Entry<String, List<Occurrence>> entry : this.groupByParameter.entrySet()) {
+ potentialHitRatio += entry.getValue().size();
+ }
+ potentialHitRatio = (potentialHitRatio - this.groupByParameter.size()) / potentialHitRatio;
+ this.groupByParameter.clear();
+ return potentialHitRatio;
+ }
+
+ @Override
+ public int hashCode() {
+ int hash = 5;
+ hash = 37 * hash + Objects.hashCode(this.name);
+ return hash;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ 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
new file mode 100644
index 0000000..038b7d9
--- /dev/null
+++ b/src/main/java/br/ufrgs/inf/prosoft/memoizeit/Occurrence.java
@@ -0,0 +1,40 @@
+/*
+ * 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 java.util.List;
+
+/**
+ *
+ * @author romulo
+ */
+public class Occurrence {
+
+ private final Object returnValue;
+ private final List<Object> parameters;
+ private final long startTime;
+ private final long endTime;
+
+ public Occurrence(Object returnValue, List<Object> parameters, long startTime, long endTime) {
+ this.returnValue = returnValue;
+ this.parameters = parameters;
+ this.startTime = startTime;
+ this.endTime = endTime;
+ }
+
+ public Object getReturnValue() {
+ return returnValue;
+ }
+
+ public List<Object> getParameters() {
+ return parameters;
+ }
+
+ public long getExecutionTime() {
+ return this.endTime - this.startTime;
+ }
+
+}