MemoizeIt.java

/*
 * 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.memoizeit.graph.Graph;
import br.ufrgs.inf.prosoft.memoizeit.graph.Node;

import java.util.*;
import java.util.function.Consumer;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.stream.Collectors;

/**
 * @author romulo
 */
public class MemoizeIt {

  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.isChangeable()) {
      return true;
    }
    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));
    }
    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;
    }
    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;
  }

  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);
    }
    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);
    }
    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);
  }
}