cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Benedict (JIRA)" <>
Subject [jira] [Commented] (CASSANDRA-8988) Optimise IntervalTree
Date Wed, 18 Mar 2015 21:23:38 GMT


Benedict commented on CASSANDRA-8988:

My goal here was to keep the code behaviour largely unmodified, but since leaving the order
of operands intact let me swap the early termination clauses I've fixed the ordering of the
parameters to be consistent as you suggest.

Since we only build the reverse ordering indrection on construction, and the normal ordering
is useful for CASSANDRA-8920, I'm inclined to leave that as is.

As to binary search, I agree in principle, but in practice we need to implement an asymmetric
binary search (i.e. can accept different types on each side). The benefit will be determined
by the average size of these lists, which I'm not all too clear on. With STCS it could well
be very large, so might be helpful.

> Optimise IntervalTree
> ---------------------
>                 Key: CASSANDRA-8988
>                 URL:
>             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

View raw message