ss: remove linear component from node search.

Before, nodes had their intervals only sorted by end times,
which meant finding the first interval which started later
than time t implied a binary search for any interval ending
at time t, then a linear iteration to the first interval
ending before (inclusively) t.
We remove this component by ordering intervals by end times
then by start times, so that the binary search can directly
return the first interval ending before (inclusively) t.

Change-Id: I3e4fd02880d56360fc082023c08b92f8a6e4350e
Signed-off-by: Loïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Reviewed-on: https://git.eclipse.org/r/86865
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-by: Hudson CI
Reviewed-by: Alexandre Montplaisir <alexmonthy@efficios.com>
Tested-by: Alexandre Montplaisir <alexmonthy@efficios.com>

diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTInterval.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTInterval.java
index 7af2e4f76e4ee1680ddcbf0da996257065e1656c..96d33a73756598e2bc2353a86afd8ba08119ba29 100644 (file)
--- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTInterval.java
+++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTInterval.java
@@ -36,7 +36,7 @@ import org.eclipse.tracecompass.statesystem.core.statevalue.TmfStateValue;
  *
  * @author Alexandre Montplaisir
  */
-public final class HTInterval implements ITmfStateInterval, Comparable<HTInterval> {
+public final class HTInterval implements ITmfStateInterval {
 
     private static final Charset CHARSET = Charset.forName("UTF-8"); //$NON-NLS-1$
 
@@ -343,21 +343,6 @@ public final class HTInterval implements ITmfStateInterval, Comparable<HTInterva
         return fSizeOnDisk;
     }
 
-    /**
-     * Compare the END TIMES of different intervals. This is used to sort the
-     * intervals when we close down a node.
-     */
-    @Override
-    public int compareTo(HTInterval other) {
-        if (this.end < other.end) {
-            return -1;
-        } else if (this.end > other.end) {
-            return 1;
-        } else {
-            return 0;
-        }
-    }
-
     @Override
     public boolean equals(Object obj) {
         if (this == obj) {

diff --git a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java
index fe52f636311834a6b37e2205105a299046b22598..776dd44633cc42d555f29ecf17e5029861968c92 100644 (file)
--- a/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java
+++ b/statesystem/org.eclipse.tracecompass.statesystem.core/src/org/eclipse/tracecompass/internal/statesystem/core/backend/historytree/HTNode.java
@@ -21,6 +21,7 @@ import java.nio.ByteOrder;
 import java.nio.channels.FileChannel;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 import java.util.concurrent.locks.ReentrantReadWriteLock;
 
@@ -135,6 +136,12 @@ public abstract class HTNode {
     /* Lock used to protect the accesses to intervals, nodeEnd and such */
     private final ReentrantReadWriteLock fRwl = new ReentrantReadWriteLock(false);
 
+    /** Order of intervals in a HTNode: sorted by end times, then by start times. */
+    private static final Comparator<ITmfStateInterval> NODE_ORDER = Comparator
+            .comparingLong(ITmfStateInterval::getEndTime)
+            .thenComparingLong(ITmfStateInterval::getStartTime)
+            .thenComparingInt(ITmfStateInterval::getAttribute);
+
     /**
      * Constructor
      *
@@ -375,9 +382,14 @@ public abstract class HTNode {
             assert (newInterval.getSizeOnDisk() <= getNodeFreeSpace());
 
             /* Find the insert position to keep the list sorted */
-            int index = fIntervals.size();
-            while (index > 0 && newInterval.compareTo(fIntervals.get(index - 1)) < 0) {
-                index--;
+            int index = 0;
+            if (!fIntervals.isEmpty()) {
+                index = Collections.binarySearch(fIntervals, newInterval, NODE_ORDER);
+                /*
+                 * Interval should not already be in the node, binarySearch will
+                 * return (-insertionPoint - 1).
+                 */
+                index = -index - 1;
             }
 
             fIntervals.add(index, newInterval);
@@ -480,8 +492,7 @@ public abstract class HTNode {
             for (int i = getStartIndexFor(t); i < fIntervals.size(); i++) {
                 HTInterval curInterval = fIntervals.get(i);
                 if (curInterval.getAttribute() == key
-                        && curInterval.getStartTime() <= t
-                        && curInterval.getEndTime() >= t) {
+                        && curInterval.getStartTime() <= t) {
                     return curInterval;
                 }
             }
@@ -500,36 +511,18 @@ public abstract class HTNode {
         if (fIntervals.isEmpty()) {
             return 0;
         }
+
         /*
-         * Since the intervals are sorted by end time, we can skip all the ones
-         * at the beginning whose end times are smaller than 't'. Java does
-         * provides a .binarySearch method, but its API is quite weird...
+         * Since the intervals are sorted by end time then by start time, we can
+         * skip all the ones at the beginning whose end times are smaller than
+         * 't'. We search for a dummy interval from [Long.MIN_VALUE, t], which
+         * will return the first interval that ends with a time >= t.
          */
-        HTInterval dummy = new HTInterval(0, t, 0, TmfStateValue.nullValue());
-        int index = Collections.binarySearch(fIntervals, dummy);
-
-        if (index < 0) {
-            /*
-             * .binarySearch returns a negative number if the exact value was
-             * not found. Here we just want to know where to start searching, we
-             * don't care if the value is exact or not.
-             */
-            index = -index - 1;
-
-        } else {
-            /*
-             * Another API quirkiness, the returned index is the one of the *last*
-             * element of a series of equal endtimes, which happens sometimes. We
-             * want the *first* element of such a series, to read through them
-             * again.
-             */
-            while (index > 0
-                    && fIntervals.get(index - 1).compareTo(fIntervals.get(index)) == 0) {
-                index--;
-            }
-        }
+        HTInterval dummy = new HTInterval(Long.MIN_VALUE, t, 0, TmfStateValue.nullValue());
+        int index = Collections.binarySearch(fIntervals, dummy, NODE_ORDER);
 
-        return index;
+        /* Handle negative binarySearch return */
+        return (index >= 0 ? index : -index - 1);
     }
 
     /**