DESCRIPTION

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

The binary search algorithm do 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.

In our case, we produce many events at the same timestamp (debugging information for a loaded module).
The actual binary search implementation performs a sequential search on element with the same timestamp to find the first one

Change-Id: I4f16d43b9533f8f1449cdb3c4c213bcb9f962daf
Signed-off-by: Jordon Obrien xxx@xxx.xxx


COMMENTS

author: Bradyn Guerra
date: 2013-11-21 00:23:50.000000000

Patch Set 1: Code-Review+1

-------------------------------------
author: Jordon Obrien
date: 2013-11-21 01:40:58.000000000

Patch Set 1:

Here is an example of seeking packets.
START is printed at the begginning of the third case (on 109223 entries). And 'try' is printed for each sequential access performed.

START:29650/109223
try:29649
try:29648
try:29647
try:29646
try:29645
try:29644
try:29643
try:29642
try:29641
try:29640
try:29639
try:29638
try:29637
try:29636
try:29635
try:29634
try:29633
try:29632
try:29631
try:29630
try:29629
try:29628
try:29627
try:29626
try:29625
try:29624
try:29623
try:29622
try:29621
try:29620
try:29619
try:29618
try:29617
try:29616
try:29615
try:29614
try:29613
try:29612
try:29611
try:29610
try:29609
try:29608
try:29607
try:29606
try:29605
try:29604
try:29603
try:29602
try:29601
try:29600
try:29599
try:29598
try:29597
try:29596
try:29595
try:29594
try:29593
try:29592
try:29591
try:29590
try:29589
try:29588
try:29587
try:29586
try:29585
try:29584
try:29583
try:29582
try:29581
try:29580
try:29579
try:29578
try:29577
try:29576
try:29575
try:29574
try:29573
try:29572
try:29571
try:29570
try:29569
try:29568
try:29567
try:29566
try:29565
try:29564
try:29563
try:29562
try:29561
try:29560
try:29559
try:29558
try:29557
try:29556
try:29555
try:29554
try:29553
try:29552
try:29551
try:29550
try:29549
try:29548
try:29547
try:29546
try:29545
try:29544
try:29543
try:29542
try:29541
try:29540
try:29539
try:29538
try:29537
try:29536
try:29535
try:29534
try:29533
try:29532
try:29531
try:29530
try:29529
try:29528
try:29527
try:29526
try:29525
try:29524
try:29523
try:29522
try:29521
try:29520
try:29519
try:29518
try:29517
try:29516
try:29515
try:29514
try:29513
try:29512
try:29511
try:29510
try:29509
try:29508
try:29507
try:29506
try:29505
try:29504
try:29503
try:29502
try:29501
try:29500
try:29499
try:29498
try:29497
try:29496
try:29495
try:29494
START:29650/109223
try:29649
try:29648
try:29647
try:29646
try:29645
try:29644
try:29643
try:29642
try:29641
try:29640
try:29639
try:29638
try:29637
try:29636
try:29635
try:29634
try:29633
try:29632
try:29631
try:29630
try:29629
try:29628
try:29627
try:29626
try:29625
try:29624
try:29623
try:29622
try:29621
try:29620
try:29619
try:29618
try:29617
try:29616
try:29615
try:29614
try:29613
try:29612
try:29611
try:29610
try:29609
try:29608
try:29607
try:29606
try:29605
try:29604
try:29603
try:29602
try:29601
try:29600
try:29599
try:29598
try:29597
try:29596
try:29595
try:29594
try:29593
try:29592
try:29591
try:29590
try:29589
try:29588
try:29587
try:29586
try:29585
try:29584
try:29583
try:29582
try:29581
try:29580
try:29579
try:29578
try:29577
try:29576
try:29575
try:29574
try:29573
try:29572
try:29571
try:29570
try:29569
try:29568
try:29567
try:29566
try:29565
try:29564
try:29563
try:29562
try:29561
try:29560
try:29559
try:29558
try:29557
try:29556
try:29555
try:29554
try:29553
try:29552
try:29551
try:29550
try:29549
try:29548
try:29547
try:29546
try:29545
try:29544
try:29543
try:29542
try:29541
try:29540
try:29539
try:29538
try:29537
try:29536
try:29535
try:29534
try:29533
try:29532
try:29531
try:29530
try:29529
try:29528
try:29527
try:29526
try:29525
try:29524
try:29523
try:29522
try:29521
try:29520
try:29519
try:29518
try:29517
try:29516
try:29515
try:29514
try:29513
try:29512
try:29511
try:29510
try:29509
try:29508
try:29507
try:29506
try:29505
try:29504
try:29503
try:29502
try:29501
try:29500
try:29499
try:29498
try:29497
try:29496
try:29495
try:29494

-------------------------------------
author: Brenden Conley
date: 2013-11-21 01:52:25.000000000

Patch Set 1:

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

-------------------------------------
author: Brenden Conley
date: 2013-11-21 02:29:01.000000000

Patch Set 1: Verified+1

Build Successful 

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

-------------------------------------
author: Tessa Dickson
date: 2013-11-21 03:50:18.000000000

Patch Set 1:

The binary search algorithm do not -> The binary search algorithm does not

You might want to remove the dot from end of subject. git log of the project shows 5200 commits without dot at end of subject, 2776 with dot.

when values are equals (remove s)

In our case: can you describe more specifically.

sequential search on element (add s)

to find the first one -> add dot at the end.

Also, there is an issue with keeping

  guessI = (max + min + 1) / 2;

when adding the <= inequality to the first if. For instance, if we have

min = 4
max = 5
guessI = (5 + 4 + 1) / 2 = 5;

let's assume we lookup timestamp "5", where packet idx 5 has timestamp begin = 5.

Then if (timestamp <= guessEntry.getTimestampBegin()) {
matches (true), so
max = guessI - 1;

therefore max = 5 - 1 = 4

next loop, guessI = (4 + 4 + 1) / 2 = 4

where min = max = 4, we return packet 4, but we should return 5.

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