[concurrency-interest] ConcurrentSkipListMap performance

Ben Manes ben_manes at yahoo.com
Mon Oct 24 01:52:09 EDT 2011

A quick glance at the benchmark [1] indicates that there are a few flaws, such as: 
- the JVM warm-up penalty is being accrued by the CSLM run
- Use thread.yield() to end a request, as otherwise the active thread may be able to run through its time slice without incurring much lock contention.

[1] http://osdir.com/ml/attachments/txtBAixyCerpa.txt

From: Ben Manes <ben_manes at yahoo.com>
To: Ted Yu <ted_yu at yahoo.com>
Cc: "concurrency-interest at cs.oswego.edu" <concurrency-interest at cs.oswego.edu>
Sent: Sunday, October 23, 2011 6:33 PM
Subject: Re: [concurrency-interest] ConcurrentSkipListMap performance

See the file headers. The Skiptree implementation is public domain. The Snaptree is copyrighted by Stanford University (http://ppl.stanford.edu/) and should fall under their policy for academic research. You can contact the author or the lab for licensing details.

From: Ted Yu <ted_yu at yahoo.com>
To: Ben Manes <ben_manes at yahoo.com>
Cc: "concurrency-interest at cs.oswego.edu" <concurrency-interest at cs.oswego.edu>
Sent: Sunday, October 23, 2011 5:24 PM
Subject: Re: [concurrency-interest] ConcurrentSkipListMap performance

Is either or both of the following compatible with Apache license 2.0 ?


On Oct 23, 2011, at 12:58 PM, Ben Manes <ben_manes at yahoo.com> wrote:

There's not enough information to diagnose the cause, but you may want to try one of the CSLM replacements.
>From: Ted Yu <ted_yu at yahoo.com>
>To: "concurrency-interest at cs.oswego.edu" <concurrency-interest at cs.oswego.edu>
>Sent: Sunday, October 23, 2011 12:01 PM
>Subject: [concurrency-interest] ConcurrentSkipListMap performance
>HBase expects ConcurrentSkipListMap to have good performance.
>See the following discussion.
>Comments are welcome.
>---------- Forwarded message ----------
>From: Akash Ashok <thehellmaker at gmail.com>
>Date: Sun, Oct 23, 2011 at 2:57 AM
>Subject: Re: SILT - nice keyvalue store paper
>To: dev at hbase.apache.org
 was running some similar tests and came across a surprising finding. I 
compared reads and write on ConcurrentSkipListMap ( which the memstore 
uses) and synchronized TreeMap ( Which was literally treemap 
synchronized). Executed concurrent reads, writes and deletes on both of 
>Surprisingly synchronized treeMap performed better, though just slightly
 better, than ConcurrentSkipListMap which KeyValueSkipListSet uses.
>Here are the output of a few runs
>Sometimes the difference was considerable
>Using HBaseMap it took 20438ms
>Using TreeMap it took 11613ms
>Time Difference:8825ms
>And sometimes the difference was negligible
>Using HBaseMap it took 13370ms
>Using TreeMap it took 9482ms
>Time Difference:3888ms
>I've attaching the test  java file which I wrote to test it. 
 might be a very minor differece but still surprising considering the 
fact that ConcurrentSkipListMap uses fancy 2 level indexes which they 
say improves the deletion performance.
>And here are the details about the test run.
>100 Threads each fetching 10,000 records
>100 threads each adding 10,000 records.
>100 threads each deletin 10,000 records
>( Reads, Writes and deletes simultaneously )
>Akash A
>Concurrency-interest mailing list
>Concurrency-interest at cs.oswego.edu

Concurrency-interest mailing list
Concurrency-interest at cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111023/00852373/attachment-0001.html>

More information about the Concurrency-interest mailing list