cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Jay Zhuang (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-9988) Introduce leaf-only iterator
Date Sun, 22 Jan 2017 22:05:27 GMT

    [ 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)

Mime
View raw message