[
https://issues.apache.org/jira/browse/CASSANDRA-9988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15833718#comment-15833718
]
Jay Zhuang commented on CASSANDRA-9988:
---------------------------------------
[Patch|https://github.com/cooldoger/cassandra/commit/8704eb8bbf94d5b556f67386d464a015ca98554b]
is ready, please review.
Here is the JMH test result before and after the patch, overall it
significantly improved the iterator for small BTree:
|| || Before the patch || After the patch || Improvement ||
| iteratorBigTreeTest | 171.271 | 167.288 | -2% |
| searchBigTreeTest | 12743.251 | 11833.277 | -7% |
| searchNotFoundBigTreeTest | 11140.872 | 10378.794 | -7% |
| iteratorLeafTreeTest | 5337.291 | 19788.253 | +271% |
| searchFoundLeafTreeTest | 18608.504 | 36809.601 | +98% |
| searchNotFoundLeafTreeTest | 19670.935 | 28880.540 | +47% |
| iteratorOneElemTreeTest | 65983.946 | 414832.010 | +529% |
| searchFoundOneElemTreeTest | 45796.932 | 288174.238 | +529% |
| searchNotFoundOneElemTreeTest | 43176.354 | 284008.493 | +558% |
Here is the code for JMH test without fix:
https://github.com/cooldoger/cassandra/tree/9988-nofix
I tried exponential search:
https://github.com/cooldoger/cassandra/commit/a23a3422a894acb72a47975da035bbf8da50fc4b
But the JMH test result is worse (other tests didn't change too much):
|| || Binary search || Exponential search || Improvement ||
| searchFoundLeafTreeTest | 36809.601 | 30074.161 | -18% |
| searchNotFoundLeafTreeTest | 28880.540 | 24540.700 | -15% |
| searchFoundOneElemTreeTest | 288174.238 | 233786.942 | -19% |
| searchNotFoundOneElemTreeTest | 284008.493 | 199549.589 | -30% |
Here are the JMH test results:
{noformat}
No Fix
[java] Benchmark Mode Cnt
Score Error Units
[java] BTreeSearchIteratorBench.iteratorBigTreeTest thrpt 40
171.271 ? 3.872 ops/ms
[java] BTreeSearchIteratorBench.iteratorLeafTreeTest thrpt 40
5337.291 ? 306.129 ops/ms
[java] BTreeSearchIteratorBench.iteratorOneElemTreeTest thrpt 40
65983.946 ? 10651.607 ops/ms
[java] BTreeSearchIteratorBench.searchBigTreeTest thrpt 40
12743.251 ? 1171.717 ops/ms
[java] BTreeSearchIteratorBench.searchFoundLeafTreeTest thrpt 40
18608.504 ? 1671.129 ops/ms
[java] BTreeSearchIteratorBench.searchFoundOneElemTreeTest thrpt 40
45796.932 ? 6543.235 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundBigTreeTest thrpt 40
11140.872 ? 1355.109 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundLeafTreeTest thrpt 40
19670.935 ? 1775.676 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundOneElemTreeTest thrpt 40
43176.354 ? 6862.149 ops/ms
Fix [Binary Search]
[java] Benchmark Mode Cnt
Score Error Units
[java] BTreeSearchIteratorBench.iteratorBigFullTreeTest thrpt 40
147.093 ? 7.968 ops/ms
[java] BTreeSearchIteratorBench.iteratorBigTreeTest thrpt 40
167.288 ? 4.029 ops/ms
[java] BTreeSearchIteratorBench.iteratorLeafTreeTest thrpt 40
19788.253 ? 887.529 ops/ms
[java] BTreeSearchIteratorBench.iteratorOneElemTreeTest thrpt 40
414832.010 ? 16663.043 ops/ms
[java] BTreeSearchIteratorBench.searchBigTreeTest thrpt 40
11833.277 ? 1290.791 ops/ms
[java] BTreeSearchIteratorBench.searchFoundLeafTreeTest thrpt 40
36809.601 ? 2403.004 ops/ms
[java] BTreeSearchIteratorBench.searchFoundOneElemTreeTest thrpt 40
288174.238 ? 11618.352 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundBigTreeTest thrpt 40
10378.794 ? 1229.196 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundLeafTreeTest thrpt 40
28880.540 ? 1875.317 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundOneElemTreeTest thrpt 40
284008.493 ? 7929.286 ops/ms
Fix [Exponential search]
[java] Benchmark Mode Cnt
Score Error Units
[java] BTreeSearchIteratorBench.iteratorBigFullTreeTest thrpt 40
164.849 ? 3.571 ops/ms
[java] BTreeSearchIteratorBench.iteratorBigTreeTest thrpt 40
161.228 ? 6.219 ops/ms
[java] BTreeSearchIteratorBench.iteratorLeafTreeTest thrpt 40
19828.490 ? 727.999 ops/ms
[java] BTreeSearchIteratorBench.iteratorOneElemTreeTest thrpt 40
397640.373 ? 18525.227 ops/ms
[java] BTreeSearchIteratorBench.searchBigTreeTest thrpt 40
11816.892 ? 1305.738 ops/ms
[java] BTreeSearchIteratorBench.searchFoundLeafTreeTest thrpt 40
30074.161 ? 1916.827 ops/ms
[java] BTreeSearchIteratorBench.searchFoundOneElemTreeTest thrpt 40
233786.942 ? 6960.706 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundBigTreeTest thrpt 40
11014.239 ? 1323.596 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundLeafTreeTest thrpt 40
24540.700 ? 1596.072 ops/ms
[java] BTreeSearchIteratorBench.searchNotFoundOneElemTreeTest thrpt 40
199549.589 ? 7523.028 ops/ms
{noformat}
> 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-trunk-new.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.3.4#6332)
