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>
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
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;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
fLock.writeLock().lock();
try {
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 {
fLastSnapshot = null;
return true;
} finally {
*/
fLock.readLock().lock();
try {
*/
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();
}
} finally {
fLock.readLock().unlock();
}
public Iterable<E> getIntersectingElements(long start, long end) {
fLock.readLock().lock();
try {
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();
}
} finally {
fLock.readLock().unlock();
}
import java.util.ArrayList;
import java.util.Collection;
import java.util.ArrayList;
import java.util.Collection;
+import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import org.eclipse.jdt.annotation.NonNull;
import org.eclipse.jdt.annotation.Nullable;
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;
import org.eclipse.tracecompass.segmentstore.core.ISegment;
import org.eclipse.tracecompass.segmentstore.core.ISegmentStore;
* *lower* than 't' AND 2) end time is *higher* than 't'.
*/
try {
* *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();
}
} finally {
fLock.unlock();
}
- 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();
}
} finally {
fLock.unlock();
}