From 2047fe0410d1acf38d85b51cadd75d31bebf2936 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Lo=C3=AFc=20Prieur-Drevon?= Date: Tue, 20 Sep 2016 12:03:05 -0400 Subject: [PATCH] timing.core: speed up (Lazy)ArrayList queries with binary search MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit 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 Reviewed-on: https://git.eclipse.org/r/81503 Reviewed-by: Hudson CI Reviewed-by: Matthew Khouzam Reviewed-by: Genevieve Bastien Tested-by: Genevieve Bastien --- .../timing/core/store/ArrayListStore.java | 21 ++++++++++++------- .../timing/core/store/LazyArrayListStore.java | 14 +++++++++++-- 2 files changed, 26 insertions(+), 9 deletions(-) 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 9537fb403a..2efda3b376 100644 --- 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 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 e5de0a7258..cbe47fe244 100644 --- 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(); } -- 2.34.1