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

/**
 *
 * @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;
    // Stoping condition to iterative algorithm
    private boolean maxDepthReached;
    // Call Graph
    private Graph<String> callGraph;

    public MemoizeIt() {
        this.maxDepthReached = false;
        this.minimumHitRatio = 0.5;
        this.minimumMethodCalls = 2;
        this.minimumRelativeTime = 1.0;
        this.minimumExecutionTime = 5;
    }

    public MemoizeIt(long totalProgramExecution) {
        this();
        this.maxDepthReached = false;
        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;
    }

    public MemoizeIt setCallGraph(Graph<String> callGraph) {
        this.callGraph = callGraph;
        return this;
    }

    private void estimateTotalProgramExecution() {
        this.totalProgramExecution = this.methods.stream().map(method -> method.getTotalExecutionTime()).reduce(Long::sum).get();
    }

    private void calculateAverageExecutionTime() {
        this.averageProgramExecution = this.methods.stream().map(method -> method.getAverageExecutionTime()).reduce(Long::sum).get();
        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++;
        }
    }

    private void removeUnusedFields() {
        this.methods.forEach(method -> method.removeUnusedFields(this.callGraph.getNode(method.getName())));
    }

//    3.2 input-output profiling
    private void refineCandidates() {
        refineCandidates(Integer.MAX_VALUE);
    }

    private void refineCandidates(int depth) {
        int i = 0;
        while (i < this.methods.size()) {
            Method method = this.methods.get(i);
            int occurrencesSize = method.getOccurrencesSize();
            if (depth < Integer.MAX_VALUE) {
                method.groupByParameter(depth);
                if (method.wasFullyExplored()) {
                    this.maxDepthReached = true;
                    i++;
                    continue;
                }
                this.maxDepthReached = false;
            } else {
                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++;
        }
    }

    private void refineCandidatesIteratively() {
        int depth = 1;
        while (true) {
            System.out.println("Exploring depth " + depth);
            refineCandidates(depth);
            if (this.methods.isEmpty()) {
                System.out.println("No caching candidates left to explore");
                break;
            }
            if (this.maxDepthReached) {
                System.out.println("Max depth reached");
                break;
            }
            depth *= 2;
        }
    }

    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) {
        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");
        CachingPerformance globalSingleCachePerformance = cachingStrategyHasPerformance.get("globalSingleCache");
        CachingPerformance instanceMultiCachePerformance = cachingStrategyHasPerformance.get("instanceMultiCache");
        CachingPerformance instanceSingleCachePerformance = cachingStrategyHasPerformance.get("instanceSingleCache");
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("GS: ");
        stringBuilder.append("R").append(globalSingleCachePerformance.getHitRatio());
        stringBuilder.append(" * ").append(globalSingleCachePerformance);
        stringBuilder.append(" | IS: ");
        stringBuilder.append("R").append(instanceSingleCachePerformance.getHitRatio());
        stringBuilder.append(" * ").append(instanceSingleCachePerformance);
        stringBuilder.append(" | GM: ");
        stringBuilder.append("R").append(globalMultiCachePerformance.getHitRatio());
        stringBuilder.append(" * ").append(globalMultiCachePerformance);
        stringBuilder.append(" | IM: ");
        stringBuilder.append("R").append(instanceMultiCachePerformance.getHitRatio());
        stringBuilder.append(" * ").append(instanceMultiCachePerformance);
        System.out.println(stringBuilder);
        if (globalSingleCachePerformance.getHitRatio() >= 50) {
            System.out.println("single, global");
        } else if (instanceSingleCachePerformance.getHitRatio() >= 50) {
            System.out.println("single, instance");
        } else if (globalMultiCachePerformance.getHitRatio() >= 50) {
            System.out.println("multi, global");
        } else if (instanceMultiCachePerformance.getHitRatio() >= 50) {
            System.out.println("multi, instance");
        } else {
            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();
        removeUnusedFields();
        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();
        removeUnusedFields();
        refineCandidatesIteratively();
        printClusters();
        suggestImplementations();
    }
}