[
https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16117210#comment-16117210
]
Jay Zhuang commented on CASSANDRA-9988:
---------------------------------------
Hi [~benedict] thanks for the quick response.
The graph is the search performance (throughput) for searching target on the
different positions. The X axis is the position, the Y axis is the throughput,
the bigger is the better. For multi-seeks, we can assume the current position
is 0, so if the next search value is the next adjacent one (position 1),
expSearch is 3 times better than binSearch, but binSearchOptimized could
actually do slightly better than expSearch in that case.
{quote}
if we want just a random 8 items in a 32 item iterator, we should expect exp.
search to win on average
{quote}
Yes, I agree. expSearch should out perform binSearch if we choose random 8
items out of 32, as these 8 items should be close to each other.
{quote}
I did indicate my changes assumed your implementation was valid (I did not
attempt to verify it, and the original looks to be the source of the bug).
{quote}
The original implementation is valid. I think that's another example shows the
code is not that easy to understand.
If you follows the original implementation, it should be: {{return
Arrays.binarySearch(keys, lb, Math.min(ub + 1, probe_ub {color:red}+ 1{color}),
key, comparator);}} baiscally it's just one-off issue.
{quote}
I will, separately, note that I suspect we're both well past interest in this
discussion. So if you'd rather just go with binary search, feel free.
{quote}
Yes, I agree, and I'm really appreciated your reviews and comments. Let's
create another JIRA to look into the adoption of expSearch, not only for this
case, it may improve performance for other places too. and it should be in util/
> 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
(v6.4.14#64029)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
