[
https://issues.apache.org/jira/browse/CASSANDRA-9471?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14648337#comment-14648337
]
Benedict commented on CASSANDRA-9471:
-------------------------------------
[~aweisberg] said:
{quote}
It would be nice to see a microbenchmark and benchmark demonstrating that the
use of BTree is a win. I am wondering how many additional instructions and
branches are hidden inside BTree that you pay for in the common case of small
Columns set. A BTree is more instructions for more cache locality, but in the
common case will there be enough columns to benefit?
{quote}
If we want to go down that avenue, we should IMO simply look into specialising
the btree iterator for the situation where we have just one leaf, and this is
something I've considered. That's pretty much the only likely win. We don't
really have time to do the kind of microbenchmarking you're talking about
though, and it is of limited use anyway, since one of the main benefits
_performancewise_ (in the common case) is improved icache\* occupancy, which
cannot be accounted for in a microbenchmark. In the uncommon case this also
gives us better lower bounds on behaviour, and access to a more powerfully
expressive toolkit. For instance, it permits us to trivially deliver a more
efficient multi-way merge (which we do very often), and that can be improved
further still with less trivial enhancements.
Mostly, though, this patch simply guarantees us a good lower bound on
performance, with improved code clarity. Right now I would very much expect
performance in the common case to be a wash, especially on any of our existing
workloads.
> Columns should be backed by a BTree, not an array
> -------------------------------------------------
>
> Key: CASSANDRA-9471
> URL: https://issues.apache.org/jira/browse/CASSANDRA-9471
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Reporter: Benedict
> Assignee: Benedict
> Fix For: 3.0 beta 1
>
>
> Follow up to 8099.
> We have pretty terrible lookup performance as the number of columns grows
> (linear). In at least one location, this results in quadratic performance.
> We don't however want this structure to be either any more expensive to
> build, nor to store. Some small modifications to BTree will permit it to
> serve here, by permitting efficient lookup by index, and calculation _of_
> index for a given key.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
