This also adds a bit more javadoc explaining how the algorithm works.
Change-Id: I74f5bdb163e7cfa1aee7181a9b3a4b30c0cc86d7
Signed-off-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-on: https://git.eclipse.org/r/78399
Reviewed-by: Jean-Christian Kouame <jean-christian.kouame@ericsson.com>
Tested-by: Jean-Christian Kouame <jean-christian.kouame@ericsson.com>
Reviewed-by: Hudson CI
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow.ControlFlowEntry;
-import org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow.ControlFlowView;
-import org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow.ControlFlowView.OptimizationAlgorithm;
+import org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow.NaiveOptimizationAlgorithm;
import org.eclipse.tracecompass.tmf.core.trace.ITmfTrace;
import org.eclipse.tracecompass.tmf.ctf.core.trace.CtfTmfTrace;
import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
*
* @return the optimization method to test.
*/
- protected OptimizationAlgorithm getOptimizationMethod() {
- return new ControlFlowView.OptimizationAlgorithm();
+ protected Function<Collection<ILinkEvent>, Map<Integer, Long>> getOptimizationMethod() {
+ return new NaiveOptimizationAlgorithm();
}
/**
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
-import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.Resolution;
import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.widgets.Utils.TimeFormat;
-import com.google.common.collect.HashMultiset;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Multiset;
-import com.google.common.collect.Multisets;
/**
* The Control Flow view main object
private static final Comparator<ITimeGraphEntry>[] COLUMN_COMPARATORS;
- private final Function<Collection<ILinkEvent>, Map<Integer, Long>> UPDATE_SCHEDULING_COLUMN_ALGO = new OptimizationAlgorithm();
+ private final Function<Collection<ILinkEvent>, Map<Integer, Long>> UPDATE_SCHEDULING_COLUMN_ALGO = new NaiveOptimizationAlgorithm();
private static final int INITIAL_SORT_COLUMN_INDEX = 3;
}
- /**
- * Optimization algorithm, overridable.
- *
- * @author Matthew Khouzam
- * @author Samuel Gagnon
- */
- public static class OptimizationAlgorithm implements Function<Collection<ILinkEvent>, Map<Integer, Long>> {
-
- /**
- * 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<Integer, Long> apply(Collection<ILinkEvent> arrows) {
- /*
- * "transitions" contains the count of every arrows between two tids
- * (Pair<Integer, Integer>). For constructing the Pair, we always
- * put the smallest tid first
- */
- Multiset<Pair<Integer, Integer>> transitions = HashMultiset.<Pair<Integer,Integer>>create();
-
- /*
- * 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();
- ITimeGraphEntry to = arrow.getDestinationEntry();
- if (!(from instanceof ControlFlowEntry) || !(to instanceof ControlFlowEntry)) {
- continue;
- }
- int fromTid = ((ControlFlowEntry) from).getThreadId();
- int toTid = ((ControlFlowEntry) to).getThreadId();
- if (fromTid != toTid) {
- Pair<Integer, Integer> key = new Pair<>(Math.min(fromTid, toTid), Math.max(fromTid, toTid));
- transitions.add(key);
- }
- }
-
- /*
- * 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<Pair<Integer, Integer>> sortedTransitionsByCount = Multisets.copyHighestCountFirst(transitions).asList();
-
- /*
- * 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<Integer, Long> orderedTidMap = new LinkedHashMap<>();
- long pos = 0;
- for (Pair<Integer, Integer> threadPair : sortedTransitionsByCount) {
- if (orderedTidMap.get(threadPair.getFirst()) == null) {
- orderedTidMap.put(threadPair.getFirst(), pos);
- pos++;
- }
- if (orderedTidMap.get(threadPair.getSecond()) == null) {
- orderedTidMap.put(threadPair.getSecond(), pos);
- pos++;
- }
- }
-
- return orderedTidMap;
- }
- }
-
/**
* @author gbastien
*
--- /dev/null
+/*******************************************************************************
+ * Copyright (c) 2016 Ericsson
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+package org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow;
+
+import java.util.Collection;
+import java.util.LinkedHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+
+import org.eclipse.tracecompass.tmf.core.util.Pair;
+import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
+import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeGraphEntry;
+
+import com.google.common.collect.HashMultiset;
+import com.google.common.collect.Multiset;
+import com.google.common.collect.Multisets;
+
+/**
+ * Optimization algorithm, this approach bubbles up the elements that have more
+ * connections together. This effectively will give good results with a
+ * complexity of O(n) where n is the number of transitions. It may solve
+ * non-optimally for very tightly coupled cliques.
+ *
+ * @author Matthew Khouzam
+ * @author Samuel Gagnon
+ */
+public class NaiveOptimizationAlgorithm implements Function<Collection<ILinkEvent>, Map<Integer, Long>> {
+
+ /**
+ * 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<Integer, Long> apply(Collection<ILinkEvent> arrows) {
+ /*
+ * "transitions" contains the count of every arrows between two tids
+ * (Pair<Integer, Integer>). For constructing the Pair, we always put
+ * the smallest tid first
+ */
+ Multiset<Pair<Integer, Integer>> transitions = HashMultiset.<Pair<Integer, Integer>> create();
+
+ /*
+ * 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();
+ ITimeGraphEntry to = arrow.getDestinationEntry();
+ if (!(from instanceof ControlFlowEntry) || !(to instanceof ControlFlowEntry)) {
+ continue;
+ }
+ int fromTid = ((ControlFlowEntry) from).getThreadId();
+ int toTid = ((ControlFlowEntry) to).getThreadId();
+ if (fromTid != toTid) {
+ Pair<Integer, Integer> key = new Pair<>(Math.min(fromTid, toTid), Math.max(fromTid, toTid));
+ transitions.add(key);
+ }
+ }
+
+ /*
+ * 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<Pair<Integer, Integer>> sortedTransitionsByCount = Multisets.copyHighestCountFirst(transitions).asList();
+
+ /*
+ * 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<Integer, Long> orderedTidMap = new LinkedHashMap<>();
+ long pos = 0;
+ for (Pair<Integer, Integer> threadPair : sortedTransitionsByCount) {
+ if (orderedTidMap.get(threadPair.getFirst()) == null) {
+ orderedTidMap.put(threadPair.getFirst(), pos);
+ pos++;
+ }
+ if (orderedTidMap.get(threadPair.getSecond()) == null) {
+ orderedTidMap.put(threadPair.getSecond(), pos);
+ pos++;
+ }
+ }
+
+ return orderedTidMap;
+ }
+}
\ No newline at end of file
projects / deliverable / tracecompass.git / commitdiff
