[jira] [Comment Edited] (CASSANDRA-9471) Columns should be backed by a BTree, not an array

["Benedict (JIRA)" <ji...@apache.org>]

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

Benedict edited comment on CASSANDRA-9471 at 7/30/15 9:39 PM:
--------------------------------------------------------------

[~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. Other future improvements that can be deployed widely are efficient intersection for iteration of subsets, which again we do very often.

Mostly, though, for now 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.


was (Author: benedict):
[~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)