cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Branimir Lambov (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (CASSANDRA-8988) Optimise IntervalTree
Date Thu, 19 Mar 2015 11:56:38 GMT

    [ https://issues.apache.org/jira/browse/CASSANDRA-8988?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14368959#comment-14368959
] 

Branimir Lambov commented on CASSANDRA-8988:
--------------------------------------------

Nicely done.

[AsymmetricOrdering 76|https://github.com/apache/cassandra/compare/trunk...belliottsmith:8988#diff-e8d8865e0c7d14541ae677a1c98bfca4R76]:
I think this will be clearer if it follows the structure of the one above: {{if (c < 0)
i = m; else j = m;}} to make it obvious that the only difference between the two is the strictness
of the comparison.

[IntervalTree 235|https://github.com/apache/cassandra/compare/trunk...belliottsmith:8988#diff-e675fa5966322284415eff48ec0b36ffR235]:
You should use CEIL (which is the same as LOWER + 1) here. It may be worth documenting in
the Op declaration that CEIL == LOWER + 1, HIGHER == FLOOR + 1 (this is true because j is
always equal to i+1 when exiting the loop in find2).

[IntervalTree 236|https://github.com/apache/cassandra/compare/trunk...belliottsmith:8988#diff-e675fa5966322284415eff48ec0b36ffR236],
[248|https://github.com/apache/cassandra/compare/trunk...belliottsmith:8988#diff-e675fa5966322284415eff48ec0b36ffR248]:
I'm worried that this may be increasing the complexity over the original code for bigger trees
as it does one more level of intersectsX search. It's your call, but my preference is to do
the outside span rejection before the search as otherwise there is a possibility of performance
regression from this, however small.


> Optimise IntervalTree
> ---------------------
>
>                 Key: CASSANDRA-8988
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-8988
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Benedict
>            Assignee: Benedict
>            Priority: Trivial
>             Fix For: 2.1.4
>
>         Attachments: 8988.txt
>
>
> We perform a lot of unnecessary comparisons in IntervalTree.IntervalNode.searchInternal.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message