summaryrefslogtreecommitdiffstatsabout
diff options
context:
space:
mode:
authorEtienne Bergeron2013-11-20 19:03:05 (EST)
committer Alexandre Montplaisir2013-11-25 17:35:12 (EST)
commit577699814c215e6e51a80884f310909a6a5019eb (patch)
tree381a2cc82e8da71bd10ad65d0f462d5ede0e04d8
parentdd1ed12336ab547ad2733b2915827dddf5d3b813 (diff)
downloadorg.eclipse.linuxtools-577699814c215e6e51a80884f310909a6a5019eb.zip
org.eclipse.linuxtools-577699814c215e6e51a80884f310909a6a5019eb.tar.gz
org.eclipse.linuxtools-577699814c215e6e51a80884f310909a6a5019eb.tar.bz2
[ctf] Fix binary search for a long sequence of same timestamps.refs/changes/54/18654/9
The binary search algorithm does not need a third case (when values are equals) if there is a guarantee to remove one element in the search space at each iteration. The actual binary search implementation performs a sequential search on elements with the same timestamp (to find the first one). The ETW2CTF traces produce many debug events for the debugging information at the module load timestamp. Which is the worse case for the actual implementation. We changed the algorithm to use the timestamp end of a packet instead of the beginning. We changed the way to choose a middle element to ease the recursion by using only two cases. Change-Id: I4f16d43b9533f8f1449cdb3c4c213bcb9f962daf Signed-off-by: Etienne Bergeron <etienne.bergeron@gmail.com> Reviewed-on: https://git.eclipse.org/r/18654 Reviewed-by: Matthias Nick <Matthias.Nick@bsiag.com> Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> Tested-by: Hudson CI IP-Clean: Alexandre Montplaisir <alexmonthy@voxpopuli.im> Tested-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im> Reviewed-by: Alexandre Montplaisir <alexmonthy@voxpopuli.im>
-rw-r--r--lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java50
1 files changed, 16 insertions, 34 deletions
diff --git a/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java
index ef74805..5532ad0 100644
--- a/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java
+++ b/lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java
@@ -8,6 +8,8 @@
*
* Contributors: Matthew Khouzam - Initial API and implementation
* Contributors: Simon Marchi - Initial API and implementation
+ * Contributors: Etienne Bergeron <etienne.bergeron@gmail.com>
+ * Contributors: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
*******************************************************************************/
package org.eclipse.linuxtools.internal.ctf.core.trace;
@@ -99,9 +101,9 @@ public class StreamInputPacketIndex {
}
/**
- * Given a timestamp, this methods returns the first PacketIndexEntry that
- * could include the timestamp, that is the last packet with a begin
- * timestamp smaller than the given timestamp.
+ * This method returns the first packet with the end timestamp greater
+ * or equal to the given timestamp. The returned packet is the first one
+ * that could include the timestamp.
*
* @param timestamp
* The timestamp to look for.
@@ -129,14 +131,12 @@ public class StreamInputPacketIndex {
throw new IllegalArgumentException("timestamp is negative"); //$NON-NLS-1$
}
+ /* Binary search */
for (;;) {
/*
- * Guess in the middle of min and max. The +1 is so that in case
- * (min + 1 == max), we choose the packet at the subscript "max"
- * instead of the one at "min". Otherwise, it would give an infinite
- * loop.
+ * Guess in the middle of min and max.
*/
- guessI = (max + min + 1) / 2;
+ guessI = min + ((max - min) / 2);
guessEntry = this.entries.get(guessI);
/*
@@ -147,36 +147,18 @@ public class StreamInputPacketIndex {
break;
}
- if (timestamp < guessEntry.getTimestampBegin()) {
+ if (timestamp <= guessEntry.getTimestampEnd()) {
/*
- * If the timestamp if before the begin timestamp, we know that
- * the packet to return is before the guess.
+ * 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 - 1;
- } else if (timestamp > guessEntry.getTimestampBegin()) {
+ max = guessI;
+ } else {
/*
- * If the timestamp is after the begin timestamp, we know that
- * the packet to return is after the guess or is the guess.
+ * 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;
- } else if (timestamp == guessEntry.getTimestampBegin()) {
- /*
- * If the timestamp is equal to the begin timestamp, we want to
- * return the first packetIndexEntry that have this timestamp.
- */
- if (guessI > 0) {
- StreamInputPacketIndexEntry previousGuessEntry = this.entries.get(guessI - 1);
- while (guessI > 0 && guessEntry.getTimestampBegin() == previousGuessEntry.getTimestampBegin()) {
- guessEntry = previousGuessEntry;
- guessI--;
- if (guessI - 1 >= 0) {
- previousGuessEntry = this.entries.get(guessI - 1);
- }
- }
- min = guessI;
- max = guessI;
- }
-
+ min = guessI + 1;
}
}