You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Jay Zhuang (JIRA)" <ji...@apache.org> on 2017/02/01 00:29:51 UTC
[jira] [Commented] (CASSANDRA-9989) Optimise BTree.Buider
[ https://issues.apache.org/jira/browse/CASSANDRA-9989?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15847778#comment-15847778 ]
Jay Zhuang commented on CASSANDRA-9989:
---------------------------------------
Thanks Benedict for the information. I agree that BTree.Builder could be further improved, currently it copys all the data in array and build the tree.
I did some improvements for [{{BTree.buildInternal()}}|https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/BTree.java#L128], which is used by both {{BTree.Builder}} and {{BTree.build()}}. It improves the {{build()}} performance by about {{+190%}}. And it benefits Builder too (about {{+50%}}). The [patch|https://github.com/cooldoger/cassandra/commit/bf6bc14a130dae64cb859e81ad54b21d5434d46a] is attached.
Here are the JMH benchmark test results:
|| [TestCode|https://github.com/cooldoger/cassandra/commit/bf6bc14a130dae64cb859e81ad54b21d5434d46a#diff-b91288be52d83bf95ac5eb819f9fe3d4] || Before the patch || After the patch || Performance increased: {{(after - before)/before}} ||
| buildLeafTreeTest | 5274.457 | 13096.541 | +148% |
| buildLeafTreeBuilderTest | 1763.279 | 2223.307 | +26% |
| build1KValuesTreeTest | 117.937 | 371.845 | +215% |
| build1KValuesTreeBuilderTest | 68.103 | 102.884 | +51% |
| build5KValuesTreeTest | 19.463 | 59.202 | +204% |
| build5KValuesTreeBuilderTest | 11.349 | 19.209 | +69% |
| build1MValuesTreeTest | 0.104 | 0.296 | +185% |
| build1MValuesTreeBuilderTest | 0.049 | 0.080 | +63% |
| transformAndFilter1KTest | 29.502 | 37.432 | +27% |
| transformAndFilter1MTest | 0.031 | 0.036 | +16% |
{{BTree.build()}} is about 1 time faster than {{BTree.Builder}}, as Builder copies the data and then calls {{build()}} internally (https://github.com/apache/cassandra/blob/trunk/src/java/org/apache/cassandra/utils/btree/BTree.java#L1088). I guess that could be further improved too.
Benchmark test details:
No fix:
{noformat}
[java] Benchmark Mode Cnt Score Error Units
[java] BTreeBuildBench.build1KValuesTreeBuilderTest thrpt 40 68.103 ? 2.694 ops/ms
[java] BTreeBuildBench.build1KValuesTreeTest thrpt 40 117.937 ? 12.761 ops/ms
[java] BTreeBuildBench.build1MValuesTreeBuilderTest thrpt 40 0.049 ? 0.002 ops/ms
[java] BTreeBuildBench.build1MValuesTreeTest thrpt 40 0.104 ? 0.007 ops/ms
[java] BTreeBuildBench.build5KValuesTreeBuilderTest thrpt 40 11.349 ? 0.743 ops/ms
[java] BTreeBuildBench.build5KValuesTreeTest thrpt 40 19.463 ? 1.489 ops/ms
[java] BTreeBuildBench.buildLeafTreeBuilderTest thrpt 40 1763.279 ? 138.734 ops/ms
[java] BTreeBuildBench.buildLeafTreeTest thrpt 40 5274.457 ? 391.289 ops/ms
[java] BTreeBuildBench.transformAndFilter1KTest thrpt 40 29.502 ? 1.548 ops/ms
[java] BTreeBuildBench.transformAndFilter1MTest thrpt 40 0.031 ? 0.001 ops/ms
{noformat}
With Fix:
{noformat}
[java] Benchmark Mode Cnt Score Error Units
[java] BTreeBuildBench.build1KValuesTreeBuilderTest thrpt 40 102.884 ? 6.888 ops/ms
[java] BTreeBuildBench.build1KValuesTreeTest thrpt 40 371.845 ? 52.153 ops/ms
[java] BTreeBuildBench.build1MValuesTreeBuilderTest thrpt 40 0.080 ? 0.004 ops/ms
[java] BTreeBuildBench.build1MValuesTreeTest thrpt 40 0.296 ? 0.037 ops/ms
[java] BTreeBuildBench.build5KValuesTreeBuilderTest thrpt 40 19.209 ? 1.587 ops/ms
[java] BTreeBuildBench.build5KValuesTreeTest thrpt 40 59.202 ? 7.439 ops/ms
[java] BTreeBuildBench.buildLeafTreeBuilderTest thrpt 40 2223.307 ? 179.095 ops/ms
[java] BTreeBuildBench.buildLeafTreeTest thrpt 40 13096.541 ? 1879.591 ops/ms
[java] BTreeBuildBench.transformAndFilter1KTest thrpt 40 37.432 ? 2.371 ops/ms
[java] BTreeBuildBench.transformAndFilter1MTest thrpt 40 0.036 ? 0.002 ops/ms
{noformat}
> Optimise BTree.Buider
> ---------------------
>
> Key: CASSANDRA-9989
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9989
> Project: Cassandra
> Issue Type: Sub-task
> Reporter: Benedict
> Assignee: Jay Zhuang
> Priority: Minor
> Fix For: 4.x
>
> Attachments: 9989-trunk.txt
>
>
> BTree.Builder could reduce its copying, and exploit toArray more efficiently, with some work. It's not very important right now because we don't make as much use of its bulk-add methods as we otherwise might, however over time this work will become more useful.
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)