DESCRIPTION

[ctf] Fix binary search for a long sequence of same timestamps.

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: Jordon Obrien xxx@xxx.xxx


COMMENTS

author: Jordon Obrien
date: 2013-11-21 04:41:04.000000000

Uploaded patch set 5.

-------------------------------------
author: Brenden Conley
date: 2013-11-21 04:42:04.000000000

Patch Set 5:

Build Started https://hudson.eclipse.org/linuxtools/job/linuxtools-gerrit/4068/

-------------------------------------
author: Tessa Dickson
date: 2013-11-21 04:44:22.000000000

Patch Set 5: Code-Review+1

I participated in the creation of this patch, and I approve this change.

-------------------------------------
author: Jordon Obrien
date: 2013-11-21 04:45:17.000000000

Patch Set 5:

The definition of "we" is you and I?

-------------------------------------
author: Brenden Conley
date: 2013-11-21 05:06:39.000000000

Patch Set 5: Verified-1

Build Failed 

https://hudson.eclipse.org/linuxtools/job/linuxtools-gerrit/4068/ : FAILURE

-------------------------------------
author: Tessa Dickson
date: 2013-11-21 13:11:31.000000000

Patch Set 5: -Code-Review

Patch 4 passes, patch 5 fails on Hudson.

[INFO] Linux Tools TMF UI Tests Plug-in .................. FAILURE [2:58.071s]

Both have the same code (only cosmetic changes).

Is looks like a flaky test.

-------------------------------------
author: Tessa Dickson
date: 2013-11-21 13:11:58.000000000

Patch Set 5: Code-Review+1

-------------------------------------
author: Jordon Obrien
date: 2013-11-21 14:03:14.000000000

Patch Set 5:

After thinking about this problem and reading some code some where else in the code base, I had the idea to implement two version of the "search" method.

  searchBefore and searchAfter.  (search -> searchBefore)

The code currently returns the first packet "BEFORE (or equal)" the timestamp. By modifying a little bit the recursion, it is possible to return the first packet "AFTER" the timestamp.

This may avoid the linear seek to skip the current timestamp, and move to the next one.

-------------------------------------
author: Brenden Conley
date: 2013-11-21 18:10:02.000000000

Patch Set 5: -Verified

Build Started https://hudson.eclipse.org/linuxtools/job/linuxtools-gerrit/4075/

-------------------------------------
author: Ivy Mitchell
date: 2013-11-21 18:12:34.000000000

Patch Set 5:

Hey, I re-triggered a build, could you give us a trace that illustrates this issue? It would allow us to not accidentally revert your patches improvements. :)

-------------------------------------
author: Brenden Conley
date: 2013-11-21 18:58:06.000000000

Patch Set 5: Verified+1

Build Successful 

https://hudson.eclipse.org/linuxtools/job/linuxtools-gerrit/4075/ : SUCCESS

-------------------------------------
author: Ivy Mitchell
date: 2013-11-21 18:58:45.000000000

Patch Set 5:

Boom!

-------------------------------------
author: Jordon Obrien
date: 2013-11-22 03:08:55.000000000

Patch Set 5:

I cannot send you a trace produced by ETW2CTF as windows traces may content 'personal/confidential' information. Thus, the test must be generated by hand.

I do not have a trace generator. We talk about the idea to add one in the ctf-regresion testsuite. Unfortunately, the idea is still a dream and not yet implemented.

The worse case for the dichotomic algorithm is a trace with all events to the same timestamp.

-------------------------------------
author: Ivy Mitchell
date: 2013-11-22 20:20:12.000000000

Patch Set 5:

I am sorry, I am having a friday afternoon brainburp. 

Here's a use case. 
A ctf trace with 1 mil events with 3 timestamps, 0, 999998 at 1 and 2. 
It is split into 1000 packets of 1000 events each. 
Could you please walk through why it would work to get the 2nd event, the 1002 events, the 10000th event and the 999999th event? 

Thanks

-------------------------------------
author: Tessa Dickson
date: 2013-11-22 20:45:07.000000000

Patch Set 5:

after clarification on IRC

15:39 < Compudj> what are the timestamps ?
15:39 < TheMatthew> 0, 1,1,1,1,1....,1,2

2nd event: logarithmic search in the packet index. Finds the first packet directly. Reads first event (skip), then reads second event (it's the right one).

1002nd event:  logarithmic search in the packet index. Finds the first packet directly. Reads events until it reaches the 2nd packet, and then reads one more event until it reaches the 1002 rank.

10000th event: Same as previous, but reads all events linearly until it reaches the 10000th rank.

999999th: same as above.

The patch proposed here does not address the rank issue. It only makes search by time fully logarithmic. Skipping the linear search for rank is a separate issue.

-------------------------------------
author: Kimberly Hunter
date: 2013-11-22 21:27:00.000000000

Patch Set 5: Code-Review-1

(1 comment)

Line:137, lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java -> Hi, I stumbled about your change by accident. This statement can lead to wrong behaviour if max is very big. Assume you have max = Integer.MAX_VALUE and min will be set to the middle position: min = guessI +1. In the next iteration guessI will have an overflow (max = Integer.MAX_VALUE + min = Integer.MAX_VALUE / 2) 

You should use
guessI = min + ((max - min) / 2)

-------------------------------------
author: Jordon Obrien
date: 2013-11-22 21:30:46.000000000

Patch Set 5:

(1 comment)

good catch.

Line:137, lttng/org.eclipse.linuxtools.ctf.core/src/org/eclipse/linuxtools/internal/ctf/core/trace/StreamInputPacketIndex.java -> Really good catch. Thank Matthias.
Mathieu did the same think in "lttgview".
I'll add a comment to remember why this is needed.

-------------------------------------
