From 0267cc9dd80c1f6f9a64bebc0aa63436837d751b Mon Sep 17 00:00:00 2001 From: Matthew Khouzam Date: Mon, 25 Jul 2016 18:10:46 -0400 Subject: [PATCH] linux.ui: extract control flow view optimizer The control flow view optimizer algorithm is now extracted into a Function<>, this allows for better testing of the code and improves modularity. To change the optimizer behaviour, one needs to override the getUpdatedSchedulingColumn() function to return another algorithm. Consider ILinkEvents to be edges in a graph where the vertices are the entries. Change-Id: I2a8cb686e2c31589873006d1fca2f489ad724b33 Signed-off-by: Matthew Khouzam Reviewed-on: https://git.eclipse.org/r/77871 Reviewed-by: Hudson CI Reviewed-by: Jean-Christian Kouame Tested-by: Jean-Christian Kouame --- .../ui/views/controlflow/ControlFlowView.java | 151 +++++++++++------- 1 file changed, 96 insertions(+), 55 deletions(-) diff --git a/analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/ControlFlowView.java b/analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/ControlFlowView.java index f5852f6ce6..e0df2aff7d 100644 --- a/analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/ControlFlowView.java +++ b/analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/ControlFlowView.java @@ -16,6 +16,7 @@ package org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow; import java.util.ArrayList; +import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; @@ -24,6 +25,7 @@ import java.util.LinkedHashMap; import java.util.List; import java.util.Map; import java.util.Set; +import java.util.function.Function; import java.util.function.Predicate; import java.util.stream.Collectors; import java.util.stream.Stream; @@ -131,6 +133,8 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { private static final Comparator[] COLUMN_COMPARATORS; + private final Function, Map> UPDATE_SCHEDULING_COLUMN_ALGO = new OptimizationAlgorithm(); + private static final int INITIAL_SORT_COLUMN_INDEX = 3; static { @@ -151,6 +155,7 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { public boolean isConflicting(ISchedulingRule rule) { return (rule == this); } + @Override public boolean contains(ISchedulingRule rule) { return (rule == this); @@ -159,7 +164,6 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { private final Set fFlatTraces = new HashSet<>(); - private IAction fFlatAction; private IAction fHierarchicalAction; @@ -416,6 +420,23 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { return Messages.ControlFlowView_previousProcessActionToolTipText; } + /** + * Get the optimization function for the scheduling column. In the base + * implementation, this optimizes by Line arrows, but can be overidden. + *

+ * It takes a collection of link events, looking at the entries being + * linked, and returns a list of the proposed order. The list of indexes + * should be in ascending order. There can be duplicates, but the values and + * order should always be the same for the same input. + * + * @return the returned column order, where the integer is the tid of the + * entry, and the return value is the position, there can be + * duplicates. + */ + public Function, Map> getUpdatedSchedulingColumn() { + return UPDATE_SCHEDULING_COLUMN_ALGO; + } + /** * This is an optimization action used to find cliques of entries due to * links and put them closer together @@ -423,6 +444,7 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { * @author Samuel Gagnon */ private final class OptimizationAction extends Action { + @Override public void runWithEvent(Event event) { ITmfTrace trace = getTrace(); @@ -433,22 +455,73 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { createFlatAction().run(); /* - * "transitions" contains the count of every arrows between - * two tids (Pair). For constructing the - * Pair, we always put the smallest tid first + * This method only returns the arrows in the current time interval + * [a,b] of ControlFlowView. Thus, we only optimize for that time + * interval */ - Map, Integer> transitions = new HashMap<>(); + List arrows = getTimeGraphViewer().getTimeGraphControl().getArrows(); + final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID); + List currentList = getEntryList(ss); + + Map orderedTidMap = getUpdatedSchedulingColumn().apply(arrows); /* - * This method only returns the arrows in the current time - * interval [a,b] of ControlFlowView. Thus, we only optimize - * for that time interval + * Now that we have our list of ordered tid, it's time to assign a + * position for each threads in the view. For this, we assign a + * value to an invisible column and sort according to the values in + * this column. */ - List arrows = getTimeGraphViewer().getTimeGraphControl().getArrows(); + for (TimeGraphEntry entry : currentList) { + if (entry instanceof TraceEntry) { + for (TimeGraphEntry child : ((TraceEntry) entry).getChildren()) { + if (child instanceof ControlFlowEntry) { + ControlFlowEntry cEntry = (ControlFlowEntry) child; + /* + * If the thread is in our list, we give it a + * position. Otherwise, it means there's no activity + * in the current interval for that thread. We set + * its position to Long.MAX_VALUE so it goes to the + * bottom. + */ + cEntry.setSchedulingPosition(orderedTidMap.getOrDefault(cEntry.getThreadId(), Long.MAX_VALUE)); + } + } + } + } + + setEntryComparator(ControlFlowColumnComparators.SCHEDULING_COLUMN_COMPARATOR); + refresh(); + } + + } + + /** + * Optimization algorithm, overridable. + * + * @author Matthew Khouzam + * @author Samuel Gagnon + */ + public static class OptimizationAlgorithm implements Function, Map> { + + /** + * Get the scheduling column order by arrows + * + * @param arrows + * the list of visible links + * @return the list of weights, by thread ID + */ + @Override + public Map apply(Collection arrows) { + /* + * "transitions" contains the count of every arrows between two tids + * (Pair). For constructing the Pair, we always + * put the smallest tid first + */ + Map, Integer> transitions = new HashMap<>(); /* - * We iterate in arrows to count the number of transitions - * between every pair (tid,tid) in the current view + * We iterate in arrows to count the number of transitions between + * every pair (tid,tid) in the current view */ for (ILinkEvent arrow : arrows) { ITimeGraphEntry from = arrow.getEntry(); @@ -466,22 +539,22 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { } /* - * We now have a transition count for every pair (tid,tid). - * The next step is to sort every pair according to its - * count in decreasing order + * We now have a transition count for every pair (tid,tid). The next + * step is to sort every pair according to its count in decreasing + * order */ List> sortedTransitionsByCount = transitions.entrySet().stream().sorted(Map.Entry., Integer> comparingByValue().reversed()).map(Map.Entry::getKey).collect(Collectors.toList()); /* - * Next, we find the order in which we want to display our - * threads. We simply iterate in every pair (tid,tid) in - * orderedTidList. Each time we see a new tid, we add it at - * the end of orderedTidList. This way, threads with lots of - * transitions will be grouped in the top. While very naive, - * this algorithm is fast, simple and gives decent results. + * Next, we find the order in which we want to display our threads. + * We simply iterate in every pair (tid,tid) in orderedTidList. Each + * time we see a new tid, we add it at the end of orderedTidList. + * This way, threads with lots of transitions will be grouped in the + * top. While very naive, this algorithm is fast, simple and gives + * decent results. */ - Map orderedTidMap = new LinkedHashMap<>(); - int pos = 0; + Map orderedTidMap = new LinkedHashMap<>(); + long pos = 0; for (Pair threadPair : sortedTransitionsByCount) { if (orderedTidMap.get(threadPair.getFirst()) == null) { orderedTidMap.put(threadPair.getFirst(), pos); @@ -493,39 +566,7 @@ public class ControlFlowView extends AbstractStateSystemTimeGraphView { } } - /* - * Now that we have our list of ordered tid, it's time to - * assign a position for each threads in the view. For this, - * we assign a value to an invisible column and sort - * according to the values in this column. - */ - final ITmfStateSystem ss = TmfStateSystemAnalysisModule.getStateSystem(trace, KernelAnalysisModule.ID); - List currentList = getEntryList(ss); - for (TimeGraphEntry entry : currentList) { - if (entry instanceof TraceEntry) { - for (TimeGraphEntry child : ((TraceEntry) entry).getChildren()) { - if (child instanceof ControlFlowEntry) { - ControlFlowEntry cEntry = (ControlFlowEntry) child; - /* - * If the thread is in our list, we give it - * a position. Otherwise, it means there's - * no activity in the current interval for - * that thread. We set its position to - * Long.MAX_VALUE so it goes to the bottom. - */ - Integer threadPos = orderedTidMap.get(cEntry.getThreadId()); - if (threadPos != null) { - cEntry.setSchedulingPosition(threadPos); - } else { - cEntry.setSchedulingPosition(Long.MAX_VALUE); - } - } - } - } - } - - setEntryComparator(ControlFlowColumnComparators.SCHEDULING_COLUMN_COMPARATOR); - refresh(); + return orderedTidMap; } } -- 2.34.1