[
https://issues.apache.org/jira/browse/CASSANDRA-7282?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16534123#comment-16534123
]
Michael Burman commented on CASSANDRA-7282:
-------------------------------------------
Updated the code with hopefully what you meant.. (need to get some sleep). I
see worse performance, which I believe is because the added complexity of the
minimum processing. I'll need to investigate more tomorrow.
{code}
[java] Benchmark (vnodes) Mode Cnt Score
Error Units
[java] BSTBench.multiArrayBinarySeek 4 thrpt 16 106134.448 ±
3211.072 ops/ms
[java] BSTBench.multiArrayBinarySeek 16 thrpt 16 21704.218 ±
788.881 ops/ms
[java] BSTBench.multiArrayBinarySeek 64 thrpt 16 4347.090 ±
106.703 ops/ms
[java] BSTBench.multiArrayBinarySeek 256 thrpt 16 667.122 ±
210.476 ops/ms
[java] BSTBench.multiArrayBinarySeek 512 thrpt 16 192.777 ±
29.690 ops/ms
[java] BSTBench.multiArrayLinearSearch 4 thrpt 16 172888.358 ±
7778.132 ops/ms
[java] BSTBench.multiArrayLinearSearch 16 thrpt 16 16703.622 ±
565.180 ops/ms
[java] BSTBench.multiArrayLinearSearch 64 thrpt 16 1096.093 ±
33.050 ops/ms
[java] BSTBench.multiArrayLinearSearch 256 thrpt 16 84.511 ±
2.776 ops/ms
[java] BSTBench.multiArrayLinearSearch 512 thrpt 16 22.130 ±
0.714 ops/ms
{code}
> 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
