analysis/org.eclipse.tracecompass.analysis.os.linux.ui/src/org/eclipse/tracecompass/internal/analysis/os/linux/ui/views/controlflow/NaiveOptimizationAlgorithm.java

   1 /*******************************************************************************
   2  * Copyright (c) 2016 Ericsson
   3  *
   4  * All rights reserved. This program and the accompanying materials are
   5  * made available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *******************************************************************************/
   9 package org.eclipse.tracecompass.internal.analysis.os.linux.ui.views.controlflow;
  10
  11 import java.util.Collection;
  12 import java.util.LinkedHashMap;
  13 import java.util.List;
  14 import java.util.Map;
  15 import java.util.function.Function;
  16
  17 import org.eclipse.tracecompass.tmf.core.util.Pair;
  18 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ILinkEvent;
  19 import org.eclipse.tracecompass.tmf.ui.widgets.timegraph.model.ITimeGraphEntry;
  20
  21 import com.google.common.collect.HashMultiset;
  22 import com.google.common.collect.Multiset;
  23 import com.google.common.collect.Multisets;
  24
  25 /**
  26  * Optimization algorithm, this approach bubbles up the elements that have more
  27  * connections together. This effectively will give good results with a
  28  * complexity of O(n) where n is the number of transitions. It may solve
  29  * non-optimally for very tightly coupled cliques.
  30  *
  31  * @author Matthew Khouzam
  32  * @author Samuel Gagnon
  33  */
  34 public class NaiveOptimizationAlgorithm implements Function<Collection<ILinkEvent>, Map<Integer, Long>> {
  35
  36     /**
  37      * Get the scheduling column order by arrows
  38      *
  39      * @param arrows
  40      *            the list of visible links
  41      * @return the list of weights, by thread ID
  42      */
  43     @Override
  44     public Map<Integer, Long> apply(Collection<ILinkEvent> arrows) {
  45         /*
  46          * "transitions" contains the count of every arrows between two tids
  47          * (Pair<Integer, Integer>). For constructing the Pair, we always put
  48          * the smallest tid first
  49          */
  50         Multiset<Pair<Integer, Integer>> transitions = HashMultiset.<Pair<Integer, Integer>> create();
  51
  52         /*
  53          * We iterate in arrows to count the number of transitions between every
  54          * pair (tid,tid) in the current view
  55          */
  56         for (ILinkEvent arrow : arrows) {
  57             ITimeGraphEntry from = arrow.getEntry();
  58             ITimeGraphEntry to = arrow.getDestinationEntry();
  59             if (!(from instanceof ControlFlowEntry) || !(to instanceof ControlFlowEntry)) {
  60                 continue;
  61             }
  62             int fromTid = ((ControlFlowEntry) from).getThreadId();
  63             int toTid = ((ControlFlowEntry) to).getThreadId();
  64             if (fromTid != toTid) {
  65                 Pair<Integer, Integer> key = new Pair<>(Math.min(fromTid, toTid), Math.max(fromTid, toTid));
  66                 transitions.add(key);
  67             }
  68         }
  69
  70         /*
  71          * We now have a transition count for every pair (tid,tid). The next
  72          * step is to sort every pair according to its count in decreasing order
  73          */
  74         List<Pair<Integer, Integer>> sortedTransitionsByCount = Multisets.copyHighestCountFirst(transitions).asList();
  75
  76         /*
  77          * Next, we find the order in which we want to display our threads. We
  78          * simply iterate in every pair (tid,tid) in orderedTidList. Each time
  79          * we see a new tid, we add it at the end of orderedTidList. This way,
  80          * threads with lots of transitions will be grouped in the top. While
  81          * very naive, this algorithm is fast, simple and gives decent results.
  82          */
  83         Map<Integer, Long> orderedTidMap = new LinkedHashMap<>();
  84         long pos = 0;
  85         for (Pair<Integer, Integer> threadPair : sortedTransitionsByCount) {
  86             if (orderedTidMap.get(threadPair.getFirst()) == null) {
  87                 orderedTidMap.put(threadPair.getFirst(), pos);
  88                 pos++;
  89             }
  90             if (orderedTidMap.get(threadPair.getSecond()) == null) {
  91                 orderedTidMap.put(threadPair.getSecond(), pos);
  92                 pos++;
  93             }
  94         }
  95
  96         return orderedTidMap;
  97     }
  98 }