timing.core: speed up (Lazy)ArrayList queries with binary search

The getIntersectingElements queries on the (Lazy)ArrayList
SegmentStore would iterate through the entire store with a
stream().filter(), whereas the store is sorted by start time,
then by end time of the segments.

By using a binary search on the store, we can narrow down the
iteration to the relevant sublist thus speeding queries up to 50%
on querying from real analyses.

Change-Id: Idb798f42571d14130acd26c0d126cc7b6cdbf04c
Signed-off-by: Loïc Prieur-Drevon <loic.prieurdrevon@gmail.com>
Reviewed-on: https://git.eclipse.org/r/81503
Reviewed-by: Hudson CI
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Reviewed-by: Genevieve Bastien <gbastien+lttng@versatic.net>
Tested-by: Genevieve Bastien <gbastien+lttng@versatic.net>

diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/ArrayListStore.java b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/ArrayListStore.java
index 9537fb403ab5879197e8f55448a2770846b580a3..2efda3b3760292069e08c56bbe237ccfb4ab9309 100644 (file)
--- a/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/ArrayListStore.java
+++ b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/ArrayListStore.java
@@ -23,6 +23,7 @@ import java.util.stream.Collectors;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
 import org.eclipse.tracecompass.segmentstore.core.ISegment;
 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
 
@@ -116,11 +117,9 @@ public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStor
 
         fLock.writeLock().lock();
         try {
-            fStore.add(val);
-            // Go backwards to "sift up" like a priority queue
-            for (int i = size() - 1; i > 0 && COMPARATOR.compare(val, fStore.get(i - 1)) < 0; i--) {
-                Collections.swap(fStore, i, i - 1);
-            }
+            int insertPoint = Collections.binarySearch(fStore, val);
+            insertPoint = insertPoint >= 0 ? insertPoint : -insertPoint - 1;
+            fStore.add(insertPoint, val);
             fLastSnapshot = null;
             return true;
         } finally {
@@ -240,7 +239,13 @@ public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStor
          */
         fLock.readLock().lock();
         try {
-            return fStore.stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
+            /*
+             * as fStore is sorted by start then end times, restrict sub array
+             * to elements whose start times <= t as stream.filter won't do it.
+             */
+            int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
+            index = (index >= 0) ? index : -index - 1;
+            return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
         } finally {
             fLock.readLock().unlock();
         }
@@ -250,7 +255,9 @@ public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStor
     public Iterable<E> getIntersectingElements(long start, long end) {
         fLock.readLock().lock();
         try {
-            return fStore.stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
+            int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
+            index = (index >= 0) ? index : -index - 1;
+            return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
         } finally {
             fLock.readLock().unlock();
         }

diff --git a/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java
index e5de0a72588abbbd55f4e837f7ce7f1c5e9b431a..cbe47fe244a1851db098a5e5805b127254258a52 100644 (file)
--- a/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java
+++ b/analysis/org.eclipse.tracecompass.analysis.timing.core/src/org/eclipse/tracecompass/internal/analysis/timing/core/store/LazyArrayListStore.java
@@ -13,6 +13,7 @@ import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull;
 
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.Iterator;
 import java.util.List;
@@ -21,6 +22,7 @@ import java.util.stream.Collectors;
 
 import org.eclipse.jdt.annotation.NonNull;
 import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.segmentstore.core.BasicSegment;
 import org.eclipse.tracecompass.segmentstore.core.ISegment;
 import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
 
@@ -272,7 +274,13 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment
          * *lower* than 't' AND 2) end time is *higher* than 't'.
          */
         try {
-            return fStore.stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
+            /*
+             * as fStore is sorted by start then end times, restrict sub array
+             * to elements whose start times <= t as stream.filter won't do it.
+             */
+            int index = Collections.binarySearch(fStore, new BasicSegment(position, Long.MAX_VALUE));
+            index = (index >= 0) ? index : -index - 1;
+            return fStore.subList(0, index).stream().filter(element -> position >= element.getStart() && position <= element.getEnd()).collect(Collectors.toList());
         } finally {
             fLock.unlock();
         }
@@ -285,7 +293,9 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment
             sortStore();
         }
         try {
-            return fStore.stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
+            int index = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE));
+            index = (index >= 0) ? index : -index - 1;
+            return fStore.subList(0, index).stream().filter(element -> !(start > element.getEnd() || end < element.getStart())).collect(Collectors.toList());
         } finally {
             fLock.unlock();
         }