Benedict commented on CASSANDRA-9988:

bq. The original implementation is valid. I think that's another example shows 
the code is not that easy to understand.

Mea culpa, although I think that's more an indictment of my hubris and our 
mutual disinterest.  If fifteen distracted minutes in a JIRA comment window 
procrastinating from real work yields a minor bug, it's probably not *that* 
complicated, and an IDE, test suite and a couple of hours would probably more 
than conquer it.

bq. The graph is the search performance (throughput) for searching target on 
the different positions.

Except that this isn't the same, because the search domain is different with 
different starting positions.  This is also over-counting unrelated test setup 
costs.  One would expect that, with a leaf size of 32, iterating the whole 
contents would be _approx._ 4x faster with exp. search than binary search; the 
fact it is only 3x is probably down to those extra costs.  The worst inversion 
of performance would be around 2x (i.e. exp. search being 2x slower than 
b.search at its worst), with logarithmically spaced items - i.e. at position 
16, 8, 4, 2, 1.  However, in the slowest case for exp. search, we are doing 
much less work than the slowest for binary search.

Of course, with a limit to 32 items the exp. search benefits are much less 
apparent.  If we had a leaf size of 64 it would become much more stark.  With a 
leaf size of 16, it would also become completely irrelevant.

> Introduce leaf-only iterator
> ----------------------------
>                 Key: CASSANDRA-9988
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-9988
>             Project: Cassandra
>          Issue Type: Sub-task
>            Reporter: Benedict
>            Assignee: Jay Zhuang
>            Priority: Minor
>              Labels: patch
>             Fix For: 4.0
>         Attachments: 9988-3tests.png, 9988-data.png, 9988-result2.png, 
> 9988-result3.png, 9988-result.png, 9988-test-result3.png, 
> 9988-test-result-expsearch.xlsx, 9988-test-result-raw.png, 
> 9988-test-result.xlsx, 9988-trunk-new.txt, 9988-trunk-new-update.txt, 
> trunk-9988.txt
> In many cases we have small btrees, small enough to fit in a single leaf 
> page. In this case it _may_ be more efficient to specialise our iterator.

This message was sent by Atlassian JIRA

To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org

Reply via email to