Mailing-List: contact commits-help@cassandra.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@cassandra.apache.org
Date: Tue, 19 Aug 2014 21:45:19 +0000 (UTC)
From: "Joshua McKenzie (JIRA)" <jira@apache.org>
To: commits@cassandra.apache.org
Message-ID: <JIRA.12715826.1400697535854.36651.1408484719144@arcas>
In-Reply-To: <JIRA.12715826.1400697535854@arcas>
References: <JIRA.12715826.1400697535854@arcas>
Subject: [jira] [Commented] (CASSANDRA-7282) Faster Memtable map
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Joshua McKenzie commented on CASSANDRA-7282:
--------------------------------------------

[~enigmacurry] Any chance you got some performance numbers for the branch Benedict linked above?

[~benedict] Do you have any particular use-cases you think best showcase the benefits of the code-changes here?

> Faster Memtable map
> -------------------
>
>                 Key: CASSANDRA-7282
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-7282
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Benedict
>            Assignee: Benedict
>              Labels: performance
>             Fix For: 3.0
>
>
> Currently we maintain a ConcurrentSkipLastMap of DecoratedKey -> Partition in our memtables. Maintaining this is an O(lg(n)) operation; since the vast majority of users use a hash partitioner, it occurs to me we could maintain a hybrid ordered list / hash map. The list would impose the normal order on the collection, but a hash index would live alongside as part of the same data structure, simply mapping into the list and permitting O(1) lookups and inserts.
> I've chosen to implement this initial version as a linked-list node per item, but we can optimise this in future by storing fatter nodes that permit a cache-line's worth of hashes to be checked at once,  further reducing the constant factor costs for lookups.


--
This message was sent by Atlassian JIRA
(v6.2#6252)