[
https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16537046#comment-16537046
]
Michael Burman commented on CASSANDRA-7282:
-------------------------------------------
Yeah, VamEmdeBoas is fine. In theory there are few better (according to "Array
layouts for comparison-based searching" including B-Tree in array, but without
Value Types that's a pretty long shot with Java) but as said, this is perhaps
not the best place to spend more time on - considering how small amount from
overall execution time it takes and how small improvements are expected. So
I'll change the implementation to veb.
I'll start the other ticket by moving the range detection to an upper level by
creating a new Memtable per range and use the array for finding the correct
Memtable (but still make the NonBlockingHashMap aware of the range it processes
as it needs that for the hash normalization). I'll need to find a good way from
getting that event from bootstrap & streaming (did I forget any other event
that could create more - or do you have other idea where to get it best?) back
to CFS if we want it before there's any actual writes happening. Also, any
table not using ranges (such as system, maybe some new virtual ones?) don't use
any.
> Faster Memtable map
> -------------------
>
> Key: CASSANDRA-7282
> URL: https://issues.apache.org/jira/browse/CASSANDRA-7282
> Project: Cassandra
> Issue Type: Improvement
> Reporter: Benedict
> Assignee: Michael Burman
> Priority: Major
> Labels: performance
> Fix For: 4.x
>
> Attachments: jasobrown-sample-run.txt, profile.yaml, reads.svg,
> run1.svg, writes.svg
>
>
> 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
(v7.6.3#76005)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscr...@cassandra.apache.org
For additional commands, e-mail: commits-h...@cassandra.apache.org
