From 3f02ac64da1ebd883b39cf84a408677139eeb1be Mon Sep 17 00:00:00 2001 From: Matthew Khouzam Date: Sun, 3 Aug 2014 21:33:24 -0400 Subject: [PATCH] ctf: make StreamInputPacketIndex more list like gets rid of vector improves performance Change-Id: I1ea72e61a04c2a8f264446c05d7dbaae5e6337e2 Signed-off-by: Matthew Khouzam Reviewed-on: https://git.eclipse.org/r/35974 Reviewed-by: Alexandre Montplaisir Reviewed-by: Hudson CI --- .../trace/CTFStreamInputPacketIndexTest.java | 54 +----- .../ctf/core/trace/CTFStreamInput.java | 6 +- .../trace/CTFStreamInputPacketReader.java | 4 +- .../ctf/core/trace/CTFStreamInputReader.java | 8 +- .../tracecompass/ctf/core/trace/CTFTrace.java | 3 +- .../core/trace/StreamInputPacketIndex.java | 156 +++++++++++++----- .../trace/StreamInputPacketIndexEntry.java | 19 ++- 7 files changed, 148 insertions(+), 102 deletions(-) diff --git a/org.eclipse.tracecompass.ctf.core.tests/src/org/eclipse/tracecompass/ctf/core/tests/trace/CTFStreamInputPacketIndexTest.java b/org.eclipse.tracecompass.ctf.core.tests/src/org/eclipse/tracecompass/ctf/core/tests/trace/CTFStreamInputPacketIndexTest.java index 171e676e19..b0e6f1ef42 100644 --- a/org.eclipse.tracecompass.ctf.core.tests/src/org/eclipse/tracecompass/ctf/core/tests/trace/CTFStreamInputPacketIndexTest.java +++ b/org.eclipse.tracecompass.ctf.core.tests/src/org/eclipse/tracecompass/ctf/core/tests/trace/CTFStreamInputPacketIndexTest.java @@ -14,7 +14,6 @@ package org.eclipse.tracecompass.ctf.core.tests.trace; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertNotNull; -import java.util.Collection; import java.util.ListIterator; import org.eclipse.tracecompass.ctf.core.trace.CTFReaderException; @@ -44,7 +43,7 @@ public class CTFStreamInputPacketIndexTest { @Before public void setUp() throws CTFReaderException { fixture = new StreamInputPacketIndex(); - fixture.addEntry(new StreamInputPacketIndexEntry(1L)); + fixture.append(new StreamInputPacketIndexEntry(1L)); entry = new StreamInputPacketIndexEntry(1L); } @@ -65,7 +64,8 @@ public class CTFStreamInputPacketIndexTest { @Test public void testAddEntry_1param() throws CTFReaderException { entry.setPacketSizeBits(0); - fixture.addEntry(entry); + assertNotNull(entry); + fixture.append(entry); } /** @@ -78,7 +78,8 @@ public class CTFStreamInputPacketIndexTest { public void testAddEntry_2params() throws CTFReaderException { entry.setPacketSizeBits(1); entry.setContentSizeBits(0); - fixture.addEntry(entry); + assertNotNull(entry); + fixture.append(entry); } /** @@ -93,49 +94,8 @@ public class CTFStreamInputPacketIndexTest { entry.setPacketSizeBits(1); entry.setContentSizeBits(1); entry.setTimestampEnd(1L); - fixture.addEntry(entry); - } - - /** - * Run the Collection getEntries() method test. - */ - @Test - public void testGetEntries() { - Collection result = fixture.getEntries(); - - assertNotNull(result); - assertEquals(1, result.size()); - } - - /** - * Run the ListIterator listIterator() method - * test, with no parameter to listIterator(). - */ - @Test - public void testListIterator_noparam() { - ListIterator result = fixture.listIterator(); - - assertNotNull(result); - assertEquals(true, result.hasNext()); - assertEquals(-1, result.previousIndex()); - assertEquals(false, result.hasPrevious()); - assertEquals(0, result.nextIndex()); - } - - /** - * Run the ListIterator listIterator(n) method - * test, with n = 1. - */ - @Test - public void testListIterator_withparam() { - ListIterator result = fixture.listIterator(1); - - assertNotNull(result); - assertEquals(false, result.hasNext()); - assertEquals(0, result.previousIndex()); - assertEquals(true, result.hasPrevious()); - assertEquals(1, result.nextIndex()); - assertEquals(false, result.hasNext()); + assertNotNull(entry); + fixture.append(entry); } /** diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInput.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInput.java index 1ec1a51993..b076c8f630 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInput.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInput.java @@ -209,8 +209,8 @@ public class CTFStreamInput implements IDefinitionScope { */ public boolean addPacketHeaderIndex() throws CTFReaderException { long currentPos = 0L; - if (!fIndex.getEntries().isEmpty()) { - StreamInputPacketIndexEntry pos = fIndex.getEntries().lastElement(); + if (!fIndex.isEmpty()) { + StreamInputPacketIndexEntry pos = fIndex.lastElement(); currentPos = computeNextOffset(pos); } long fileSize = getStreamSize(); @@ -219,7 +219,7 @@ public class CTFStreamInput implements IDefinitionScope { StreamInputPacketIndexEntry packetIndex = new StreamInputPacketIndexEntry( currentPos); createPacketIndexEntry(fileSize, currentPos, packetIndex); - fIndex.addEntry(packetIndex); + fIndex.append(packetIndex); return true; } return false; diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputPacketReader.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputPacketReader.java index 1c625f0bdf..c49ae2cde2 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputPacketReader.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputPacketReader.java @@ -285,11 +285,11 @@ public class CTFStreamInputPacketReader implements IDefinitionScope, AutoCloseab * to 1. */ long lostEventsStartTime; - int index = fStreamInputReader.getStreamInput().getIndex().getEntries().indexOf(currentPacket); + int index = fStreamInputReader.getStreamInput().getIndex().indexOf(currentPacket); if (index == 0) { lostEventsStartTime = currentPacket.getTimestampBegin() + 1; } else { - prevPacket = fStreamInputReader.getStreamInput().getIndex().getEntries().get(index - 1); + prevPacket = fStreamInputReader.getStreamInput().getIndex().getElement(index - 1); lostEventsStartTime = prevPacket.getTimestampEnd(); } fLostEventsDuration = Math.abs(lostEventsStartTime - currentPacket.getTimestampBegin()); diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java index b52451844b..708d0cd8c9 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFStreamInputReader.java @@ -287,7 +287,7 @@ public class CTFStreamInputReader implements AutoCloseable { * @return */ private int getPacketSize() { - return fStreamInput.getIndex().getEntries().size(); + return fStreamInput.getIndex().size(); } /** @@ -366,7 +366,7 @@ public class CTFStreamInputReader implements AutoCloseable { /* * Search in the index for the packet to search in. */ - final int len = fStreamInput.getIndex().getEntries().size(); + final int len = fStreamInput.getIndex().size(); /* * Go to beginning of trace. @@ -375,7 +375,7 @@ public class CTFStreamInputReader implements AutoCloseable { /* * if the trace is empty. */ - if ((len == 0) || (!fPacketReader.hasMoreEvents())) { + if ((fStreamInput.getIndex().isEmpty()) || (!fPacketReader.hasMoreEvents())) { /* * This means the trace is empty. abort. */ @@ -439,7 +439,7 @@ public class CTFStreamInputReader implements AutoCloseable { } private StreamInputPacketIndexEntry getPacket() { - return fStreamInput.getIndex().getEntries().get(getPacketIndex()); + return fStreamInput.getIndex().getElement(getPacketIndex()); } /** diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFTrace.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFTrace.java index 5770aa4209..8607385736 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFTrace.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/ctf/core/trace/CTFTrace.java @@ -554,6 +554,7 @@ public class CTFTrace implements IDefinitionScope { * stream. */ stream.addInput(new CTFStreamInput(stream, streamFile)); + return stream; } @@ -757,7 +758,7 @@ public class CTFTrace implements IDefinitionScope { long currentStart = Long.MAX_VALUE; for (CTFStream stream : fStreams.values()) { for (CTFStreamInput si : stream.getStreamInputs()) { - currentStart = Math.min(currentStart, si.getIndex().getEntries().get(0).getTimestampBegin()); + currentStart = Math.min(currentStart, si.getIndex().getElement(0).getTimestampBegin()); } } return timestampCyclesToNanos(currentStart); diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java index e07e06dba3..5cb4c5fd5b 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndex.java @@ -14,15 +14,21 @@ package org.eclipse.tracecompass.internal.ctf.core.trace; +import static org.eclipse.tracecompass.common.core.NonNullUtils.checkNotNull; +import java.util.ArrayList; +import java.util.Collection; +import java.util.Collections; +import java.util.List; import java.util.ListIterator; -import java.util.Vector; +import org.eclipse.jdt.annotation.NonNull; import org.eclipse.tracecompass.ctf.core.trace.CTFReaderException; /** * StreamInputPacketIndex *

- * TODO Implement me. Please. + * This is a data structure containing entries, you may append to this and read + * it. It is not thread safe. */ public class StreamInputPacketIndex { @@ -34,75 +40,81 @@ public class StreamInputPacketIndex { * Entries of the index. They are sorted by increasing begin timestamp. * index builder. */ - private final Vector entries = new Vector<>(); + private final List fEntries = new ArrayList<>(); // ------------------------------------------------------------------------ - // Getters/Setters/Predicates + // Operations // ------------------------------------------------------------------------ /** - * Gets the entries + * Returns the number of elements in this data structure. If this data + * structure contains more than {@code Integer.MAX_VALUE} elements, returns + * {@code Integer.MAX_VALUE}. * - * @return the entries + * @return the number of elements in this data structure */ - public Vector getEntries() { - return this.entries; + public int size() { + return fEntries.size(); } /** - * Gets an iterator to the entries + * Returns {@code true} if this data structure contains no elements. * - * @return an iterator to the entries + * @return {@code true} if this data structure contains no elements */ - public ListIterator listIterator() { - return this.entries.listIterator(); + public boolean isEmpty() { + return fEntries.isEmpty(); } /** - * Gets an iterator to the entries at a given position + * Adds a collection of entries to the index, the entries must be sorted. + * + * @param preParsedIndex + * the pre-parsed index file * - * @param n - * the position to get - * @return the iterator + * @throws CTFReaderException + * If there was a problem reading the entry */ - public ListIterator listIterator(int n) { - return this.entries.listIterator(n); + public void appendAll(Collection preParsedIndex) + throws CTFReaderException { + for (StreamInputPacketIndexEntry sipie : preParsedIndex) { + append(checkNotNull(sipie)); + } } - // ------------------------------------------------------------------------ - // Operations - // ------------------------------------------------------------------------ - /** - * Adds an entry to the index. + * Appends the specified element to the end of this data structure * * @param entry - * The entry to add + * element to be appended to this index, cannot be null + * @return {@code true} (as specified by {@link Collection#add}) * @throws CTFReaderException * If there was a problem reading the entry */ - public void addEntry(StreamInputPacketIndexEntry entry) + public boolean append(@NonNull StreamInputPacketIndexEntry entry) throws CTFReaderException { - assert (entry.getContentSizeBits() != 0); /* Validate consistent entry. */ if (entry.getTimestampBegin() > entry.getTimestampEnd()) { throw new CTFReaderException("Packet begin timestamp is after end timestamp"); //$NON-NLS-1$ } - /* Validate entries are inserted in monotonic increasing timestamp order. */ - if (!this.entries.isEmpty()) { - if (entry.getTimestampBegin() < this.entries.lastElement() - .getTimestampBegin()) { - throw new CTFReaderException("Packets begin timestamp decreasing"); //$NON-NLS-1$ - } + /* + * Validate entries are inserted in monotonic increasing timestamp + * order. + */ + if (!fEntries.isEmpty() && (entry.getTimestampBegin() < lastElement().getTimestampBegin())) { + throw new CTFReaderException("Packets begin timestamp decreasing"); //$NON-NLS-1$ } - this.entries.add(entry); + + fEntries.add(entry); + return true; } /** - * Returns the first PacketIndexEntry that could include the timestamp, - * that is the last packet with a begin timestamp smaller than the given timestamp. + * Returns the first PacketIndexEntry that could include the timestamp, that + * is the last packet with a begin timestamp smaller than the given + * timestamp. * * @param timestamp * The timestamp to look for. @@ -113,7 +125,7 @@ public class StreamInputPacketIndex { /* * Start with min and max covering all the elements. */ - int max = this.entries.size() - 1; + int max = fEntries.size() - 1; int min = 0; int guessI; @@ -122,8 +134,8 @@ public class StreamInputPacketIndex { /* * If the index is empty, return the iterator at the very beginning. */ - if (this.getEntries().isEmpty()) { - return this.getEntries().listIterator(); + if (isEmpty()) { + return fEntries.listIterator(); } if (timestamp < 0) { @@ -136,7 +148,7 @@ public class StreamInputPacketIndex { * Guess in the middle of min and max. */ guessI = min + ((max - min) / 2); - guessEntry = this.entries.get(guessI); + guessEntry = fEntries.get(guessI); /* * If we reached the point where we focus on a single packet, our @@ -148,19 +160,75 @@ public class StreamInputPacketIndex { if (timestamp <= guessEntry.getTimestampEnd()) { /* - * If the timestamp is lower or equal to the end of the guess packet, - * then the guess packet becomes the new inclusive max. + * If the timestamp is lower or equal to the end of the guess + * packet, then the guess packet becomes the new inclusive max. */ max = guessI; } else { /* - * If the timestamp is greater than the end of the guess packet, then - * the new inclusive min is the packet after the guess packet. + * If the timestamp is greater than the end of the guess packet, + * then the new inclusive min is the packet after the guess + * packet. */ min = guessI + 1; } } - return this.entries.listIterator(guessI); + return fEntries.listIterator(guessI); } + + /** + * Get the last element of the index + * + * @return the last element in the index + */ + public StreamInputPacketIndexEntry lastElement() { + return fEntries.get(fEntries.size() - 1); + } + + /** + * Returns the element at the specified position in this data structure. + * + * @param index + * index of the element to return + * @return the element at the specified position in this data structure + * @throws IndexOutOfBoundsException + * if the index is out of range ( + * {@code index < 0 || index >= size()}) + */ + public StreamInputPacketIndexEntry getElement(int index) { + return fEntries.get(index); + } + + /** + * Returns the index of the first occurrence of the specified element in + * this data structure, or -1 if this data structure does not contain the + * element. More formally, returns the lowest index {@code i} such that, for + * an entry {@code o}, {@code (o==null ? get(i)==null : o.equals(get(i)))}, + * or {@code -1} if there is no such index. This will work in log(n) time + * since the data structure contains elements in a non-repeating increasing + * manner. + * + * @param element + * element to search for + * @return the index of the first occurrence of the specified element in + * this data structure, or -1 if this data structure does not + * contain the element + * @throws ClassCastException + * if the type of the specified element is incompatible with + * this data structure (optional) + * @throws NullPointerException + * if the specified element is null and this data structure does + * not permit null elements (optional) + */ + public int indexOf(StreamInputPacketIndexEntry element) { + int indexOf = -1; + if (element != null) { + indexOf = Collections.binarySearch(fEntries, element); + } + return (indexOf < 0) ? -1 : indexOf; + } + } diff --git a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndexEntry.java b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndexEntry.java index 392b1d2ded..8d72d1a849 100644 --- a/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndexEntry.java +++ b/org.eclipse.tracecompass.ctf.core/src/org/eclipse/tracecompass/internal/ctf/core/trace/StreamInputPacketIndexEntry.java @@ -20,7 +20,7 @@ import java.util.Map; *

* Represents an entry in the index of event packets. */ -public class StreamInputPacketIndexEntry { +public class StreamInputPacketIndexEntry implements Comparable { // ------------------------------------------------------------------------ // Attributes @@ -258,4 +258,21 @@ public class StreamInputPacketIndexEntry { public long getTargetId(){ return fTargetID; } + + @Override + public int compareTo(StreamInputPacketIndexEntry o) { + if (fTimestampBegin > o.fTimestampBegin) { + return 1; + } + if (fTimestampBegin < o.fTimestampBegin) { + return -1; + } + if (fTimestampEnd > o.fTimestampEnd) { + return 1; + } + if (fTimestampEnd < o.fTimestampEnd) { + return -1; + } + return 0; + } } -- 2.34.1