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.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Map;
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 {

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

    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());
        int i = 0;
        while (i < this.methods.size()) {
            Method method = this.methods.get(i);
            double averageExecutionTime = method.getAverageExecutionTime();
            if (method.getOccurrencesSize() < this.minimumMethodCalls || averageExecutionTime < this.minimumExecutionTime) {
                this.methods.remove(method);
                continue;
            }
            i++;
        }
        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);
                }
            });

        });
        roots = null;
        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());
        i = 0;
        while (i < this.methods.size()) {
            Method method = this.methods.get(i);
            if (method.getRepresentativeness() < this.minimumRelativeTime) {
                this.methods.remove(method);
                continue;
            }
            i++;
        }
    }

    private void removeUnusedFields() {
        LOGGER.log(Level.INFO, "Removing unused fields of {0} candidates left", 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());
        int i = 0;
        this.methods.sort((m1, m2) -> Integer.compare(m1.getOccurrencesSize(), m2.getOccurrencesSize()));
        while (i < this.methods.size()) {
            Method method = this.methods.get(i);
            method.removeUnusedFields(this.callGraph.getNode(method.getName()));
            boolean refineCandidate;
            if (iteratively) {
                refineCandidate = refineCandidateIteratively(method);
            } else {
                refineCandidate = refineCandidateExhaustively(method);
            }
            if (refineCandidate) {
                this.methods.remove(i);
                continue;
            }
            i++;
        }
    }

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

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

    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(cluster1), clusterHasSavedTime.get(cluster2))));
    }

//    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(System.out::println);
            System.out.println();
        }
    }

    private void printClusters() {
        printClusters(true);
    }

    private 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("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("single, global");
        } else if (instanceSingleCachePerformance.getRoundedHitRatio() >= 50) {
            System.out.println("single, instance");
        } else if (globalMultiCachePerformance.getRoundedHitRatio() >= 50) {
            System.out.println("multi, global");
        } else if (instanceMultiCachePerformance.getRoundedHitRatio() >= 50) {
            System.out.println("multi, instance");
        } else {
            System.out.println("none");
        }
    }

//    3.4 suggest cache implementation
    private void suggestImplementations() {
        LOGGER.log(Level.INFO, "Suggesting caching implementation");
        for (Method method : this.methods) {
            System.out.println(method.getName());
            suggestImplementation(method);
            System.out.println();
        }
    }

    public void removeChangefulMethods() {
        removeChangefulMethods(false);
    }

    public void removeChangefulMethods(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(true);
    }

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

    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();
        refineCandidates(iteratively);
        printClusters(shouldRank);
        suggestImplementations();
    }
}