From 0ee1e58a086bcd7067a889c74454a1090873cd93 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Lo=C3=AFc=20Prieur-Drevon?= Date: Sun, 4 Dec 2016 12:46:06 -0500 Subject: [PATCH] segStore: getIntersectingElements performance tweaks. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Use binarySearch from (Lazy)ArrayList to correctly dimension the returned ArrayList, resizing such large arrays happens frequently during insertion and is costly. Also stop copying elements into a new arraylist prior to sorting if the returned Iterable is already a new instance of arraylist. Optimize TreeMapStore by reducing it to a single instance of TreeMultiMap and using its ordered properties efficiently to return intersecting Segments. Benchmark results below, best if viewed in a spreadsheet: SegmentStore Test Before (ms) After (ms) Gains (%) LazyArrayList Fuzzy Iterate sorted by start 220 171 22.2727272727273 LazyArrayList Fuzzy Iterate sorted by end 45 27 40 LazyArrayList Fuzzy Iterate sorted by length 40 23 42.5 LazyArrayList Random Iterate sorted by start 382 289 24.3455497382199 LazyArrayList Random Iterate sorted by end 127 73 42.5196850393701 LazyArrayList Random Iterate sorted by length 119 71 40.3361344537815 Treemap store Ordered Insertion 1640 669 59.2073170731707 Treemap store Fuzzy Insertion 902 403 55.3215077605322 Treemap store Fuzzy Iterate sorted by start 1610 187 88.3850931677019 Treemap store Fuzzy Iterate sorted by end 1570 164 89.5541401273885 Treemap store Fuzzy Iterate sorted by length 1030 125 87.8640776699029 Treemap store Random Insertion 3960 898 77.3232323232323 Treemap store Random Iterate sorted by start 2890 299 89.6539792387543 Treemap store Random Iterate sorted by end 2460 299 87.8455284552846 Treemap store Random Iterate sorted by length 1550 275 82.258064516129 Treemap store Fuzzy First Insertion 923 196 78.7648970747562 Treemap store Fuzzy First Iteration 66 20 69.6969696969697 Treemap store Fuzzy Second Insertion 929 210 77.3950484391819 Treemap store Fuzzy Second Iteration 95 34 64.2105263157895 Treemap store Random First Insertion 3670 384 89.5367847411444 Treemap store Random First Iteration 265 25 90.5660377358491 Treemap store Random Second Insertion 4590 521 88.6492374727669 Treemap store Random Second Iteration 423 56 86.7612293144208 Change-Id: I3ae2191b74f4f2170f44f45a139b866753b2441a Signed-off-by: Loïc Prieur-Drevon Reviewed-on: https://git.eclipse.org/r/86334 Reviewed-by: Hudson CI Reviewed-by: Matthew Khouzam Reviewed-by: Jean-Christian Kouame Tested-by: Jean-Christian Kouame --- .../core/arraylist/ArrayListStore.java | 35 +++++++- .../core/arraylist/LazyArrayListStore.java | 49 +++++++++- .../core/treemap/TreeMapStore.java | 90 +++++++++++-------- .../segmentstore/core/ISegmentStore.java | 28 +++--- 4 files changed, 143 insertions(+), 59 deletions(-) diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java index ee130338b0..61ca2bd083 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/ArrayListStore.java @@ -19,7 +19,6 @@ import java.util.Iterator; import java.util.List; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; -import java.util.stream.Collectors; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.jdt.annotation.Nullable; @@ -222,9 +221,37 @@ public class ArrayListStore<@NonNull E extends ISegment> implements ISegmentStor public Iterable getIntersectingElements(long start, long end) { fLock.readLock().lock(); try { - 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()); + /* + * Compute the index of the last Segment we will find in here, + * correct the negative insertion point and add 1 for array size. + */ + int arraySize = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE)); + arraySize = (arraySize >= 0) ? arraySize + 1 : -arraySize; + /* + * Create the ArrayList as late as possible, with size = (first + * intersecting segment index) - (last intersecting segment index). + */ + ArrayList iterable = null; + for (E seg : fStore) { + if (seg.getStart() <= end && seg.getEnd() >= start) { + if (iterable == null) { + iterable = new ArrayList<>(arraySize); + } + iterable.add(seg); + } else if (seg.getStart() > end) { + /* + * Since segments are sorted by start times, there is no + * point in searching segments that start too late. + */ + break; + } + arraySize--; + } + if (iterable != null) { + iterable.trimToSize(); + return iterable; + } + return Collections.EMPTY_LIST; } finally { fLock.readLock().unlock(); } diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java index d78479dc99..6afb7401de 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/arraylist/LazyArrayListStore.java @@ -18,7 +18,6 @@ import java.util.Comparator; import java.util.Iterator; import java.util.List; import java.util.concurrent.locks.ReentrantLock; -import java.util.stream.Collectors; import org.eclipse.jdt.annotation.NonNull; import org.eclipse.jdt.annotation.Nullable; @@ -66,6 +65,8 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment private @Nullable transient Iterable fLastSnapshot = null; private volatile boolean fDirty = false; + private volatile long fStart = Long.MAX_VALUE; + private volatile long fEnd = Long.MIN_VALUE; /** * Constructor @@ -87,6 +88,8 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment E element = (E) array[i]; setDirtyIfNeeded(element); fStore.add(element); + fStart = Math.min(fStart, element.getStart()); + fEnd = Math.max(fEnd, element.getEnd()); } } if (fDirty) { @@ -140,6 +143,8 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment setDirtyIfNeeded(val); fStore.add(val); fLastSnapshot = null; + fStart = Math.min(fStart, val.getStart()); + fEnd = Math.max(fEnd, val.getEnd()); return true; } finally { fLock.unlock(); @@ -255,9 +260,45 @@ public class LazyArrayListStore<@NonNull E extends ISegment> implements ISegment sortStore(); } try { - 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()); + if (start <= fStart && end >= fEnd) { + Iterable lastSnapshot = fLastSnapshot; + if (lastSnapshot == null) { + lastSnapshot = ImmutableList.copyOf(fStore); + fLastSnapshot = lastSnapshot; + } + return checkNotNull(lastSnapshot); + } + /* + * Compute the index of the last Segment we will find in here, + * correct the negative insertion point and add 1 for array size. + */ + int arraySize = Collections.binarySearch(fStore, new BasicSegment(end, Long.MAX_VALUE)); + arraySize = (arraySize >= 0) ? arraySize + 1 : -arraySize; + /* + * Create the ArrayList as late as possible, with size = (first + * intersecting segment index) - (last intersecting segment index). + */ + ArrayList iterable = null; + for (E seg : fStore) { + if (seg.getStart() <= end && seg.getEnd() >= start) { + if (iterable == null) { + iterable = new ArrayList<>(arraySize); + } + iterable.add(seg); + } else if (seg.getStart() > end) { + /* + * Since segments are sorted by start times, there is no + * point in searching segments that start too late. + */ + break; + } + arraySize--; + } + if (iterable != null) { + iterable.trimToSize(); + return iterable; + } + return Collections.EMPTY_LIST; } finally { fLock.unlock(); } diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java index ba987fdc21..672b278a28 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/internal/segmentstore/core/treemap/TreeMapStore.java @@ -14,26 +14,27 @@ package org.eclipse.tracecompass.internal.segmentstore.core.treemap; import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; +import java.util.ArrayList; import java.util.Collection; +import java.util.Comparator; import java.util.Iterator; -import java.util.TreeMap; +import java.util.List; +import java.util.NavigableSet; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; +import java.util.function.Function; 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.SegmentComparators; import com.google.common.collect.ImmutableList; -import com.google.common.collect.Iterables; -import com.google.common.collect.Ordering; -import com.google.common.collect.Sets; import com.google.common.collect.TreeMultimap; /** - * Implementation of a {@link ISegmentStore} using in-memory {@link TreeMap}'s. + * Implementation of a {@link ISegmentStore} using an in-memory {@link TreeMultimap}s. * This relatively simple implementation holds everything in memory, and as such * cannot contain too much data. * @@ -42,7 +43,7 @@ import com.google.common.collect.TreeMultimap; * secondary comparator will be the end time. If even those are equal, it will * defer to the segments' natural ordering ({@link ISegment#compareTo}). * - * The store's tree maps will not accept duplicate key-value pairs, which means + * The store's tree map will not accept duplicate key-value pairs, which means * that if you want several segments with the same start and end times, make * sure their compareTo() differentiates them. * @@ -58,9 +59,10 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< private final ReadWriteLock fLock = new ReentrantReadWriteLock(false); private final TreeMultimap fStartTimesIndex; - private final TreeMultimap fEndTimesIndex; - private volatile long fSize; + private volatile int fSize; + private volatile long fStart = Long.MAX_VALUE; + private volatile long fEnd = Long.MIN_VALUE; private @Nullable transient Iterable fLastSnapshot = null; @@ -76,17 +78,9 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< * The secondary "value" comparator will check the end times first, and * in the event of a tie, defer to the ISegment's Comparable * implementation, a.k.a. its natural ordering. - * - * The same is done for the end times index, but swapping the first two - * comparators instead. */ - fStartTimesIndex = TreeMultimap.create( - SegmentComparators.LONG_COMPARATOR, - Ordering.from(SegmentComparators.INTERVAL_END_COMPARATOR).compound(Ordering.natural())); - - fEndTimesIndex = TreeMultimap.create( - SegmentComparators.LONG_COMPARATOR, - Ordering.from(SegmentComparators.INTERVAL_START_COMPARATOR).compound(Ordering.natural())); + fStartTimesIndex = TreeMultimap.create(Comparator.naturalOrder(), + Comparator.comparingLong(E::getEnd).thenComparing(Function.identity())); fSize = 0; } @@ -118,13 +112,14 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< fLock.writeLock().lock(); try { - if (fStartTimesIndex.put(Long.valueOf(val.getStart()), val)) { - fEndTimesIndex.put(Long.valueOf(val.getEnd()), val); + boolean put = fStartTimesIndex.put(val.getStart(), val); + if (put) { fSize++; + fStart = Math.min(fStart, val.getStart()); + fEnd = Math.max(fEnd, val.getEnd()); fLastSnapshot = null; - return true; } - return false; + return put; } finally { fLock.writeLock().unlock(); } @@ -132,7 +127,7 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< @Override public int size() { - return Long.valueOf(fSize).intValue(); + return fSize; } @Override @@ -142,9 +137,14 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< @Override public boolean contains(@Nullable Object o) { + if (o == null || !(o instanceof ISegment)) { + return false; + } fLock.readLock().lock(); try { - return fStartTimesIndex.containsValue(o); + /* Narrow down the search */ + ISegment seg = (ISegment) o; + return fStartTimesIndex.get(seg.getStart()).contains(o); } finally { fLock.readLock().unlock(); } @@ -190,7 +190,7 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< try { boolean changed = false; for (E elem : c) { - if (this.add(elem)) { + if (add(elem)) { changed = true; } } @@ -205,7 +205,8 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< fLock.writeLock().lock(); try { fSize = 0; - fEndTimesIndex.clear(); + fStart = Long.MAX_VALUE; + fEnd = Long.MIN_VALUE; fStartTimesIndex.clear(); } finally { fLock.writeLock().unlock(); @@ -220,9 +221,29 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< public Iterable getIntersectingElements(long start, long end) { fLock.readLock().lock(); try { - Iterable matchStarts = Iterables.concat(fStartTimesIndex.asMap().headMap(end, true).values()); - Iterable matchEnds = Iterables.concat(fEndTimesIndex.asMap().tailMap(start, true).values()); - return checkNotNull(Sets.intersection(Sets.newHashSet(matchStarts), Sets.newHashSet(matchEnds))); + if (start <= fStart && end >= fEnd) { + if (fLastSnapshot == null) { + fLastSnapshot = ImmutableList.copyOf(fStartTimesIndex.values()); + } + return checkNotNull(fLastSnapshot); + } + List iterable = new ArrayList<>(); + /** + * fromElement is used to search the navigable sets of the + * TreeMultiMap for Segments that end after start query time. + */ + E fromElement = (E) new BasicSegment(Long.MIN_VALUE, start); + /* Get the sets of segments for startTimes <= end */ + for (Collection col : fStartTimesIndex.asMap().headMap(end, true).values()) { + /* + * The collections of segments are NavigableSets for + * TreeMultimap, add elements from the tailSet: which will have + * endTimes >= start. + */ + NavigableSet nav = (NavigableSet) col; + iterable.addAll(nav.tailSet(fromElement, true)); + } + return iterable; } finally { fLock.readLock().unlock(); } @@ -230,13 +251,6 @@ public class TreeMapStore<@NonNull E extends ISegment> implements ISegmentStore< @Override public void dispose() { - fLock.writeLock().lock(); - try { - fStartTimesIndex.clear(); - fEndTimesIndex.clear(); - fSize = 0; - } finally { - fLock.writeLock().unlock(); - } + clear(); } } diff --git a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java index 13f047061c..0a57f1bb8b 100644 --- a/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java +++ b/statesystem/org.eclipse.tracecompass.segmentstore.core/src/org/eclipse/tracecompass/segmentstore/core/ISegmentStore.java @@ -12,14 +12,11 @@ package org.eclipse.tracecompass.segmentstore.core; +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 org.eclipse.jdt.annotation.NonNull; - import com.google.common.collect.Lists; import org.eclipse.jdt.annotation.Nullable; @@ -115,15 +112,20 @@ public interface ISegmentStore extends Collection { * @return The intervals that cross this position * @since 1.1 */ - default Iterable getIntersectingElements(long start, long end, Comparator order){ - List list = Lists.newArrayList(getIntersectingElements(start, end)); - return new Iterable<@NonNull E>() { - @Override - public Iterator<@NonNull E> iterator() { - Collections.sort(list, order); - return list.iterator(); - } - }; + default Iterable getIntersectingElements(long start, long end, Comparator order) { + Iterable ret = getIntersectingElements(start, end); + List list; + if (ret instanceof ArrayList) { + /* + * No point in copying the intersecting elements into a new + * ArrayList if they are already in a new ArrayList. + */ + list = (List) ret; + } else { + list = Lists.newArrayList(ret); + } + list.sort(order); + return list; } /** -- 2.34.1