[jira] [Commented] (CASSANDRA-7282) Faster Memtable map

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

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

Benedict commented on CASSANDRA-7282:
-------------------------------------

First version available [here|https://github.com/belliottsmith/cassandra/tree/7282-fastmemtablemap]

Need to perform some more rigorous performance tests, but I see a 7-10% bump on my box for naive stress test hitting memtable reads.

> Faster Memtable map
> -------------------
>
>                 Key: CASSANDRA-7282
>                 URL: https://issues.apache.org/jira/browse/CASSANDRA-7282
>             Project: Cassandra
>          Issue Type: Improvement
>          Components: Core
>            Reporter: Benedict
>             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 skip list / hash map. The skip list would impose the order on the collection, but a hash index would live alongside as part of the same data structure, simply mapping into the skip list and permitting O(1) lookups. It should be possible to define the hash map to also permit O(1) inserts. Our decorated keys are in fact perfectly designed for this scheme.
> At the same time, we can potentially improve the data locality in the skip list by baking the initial 64 token bits directly into the structure, and storing multiple values per skip list entry to improve cache performance, bringing down memory and constant factor cpu overheads.



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