[concurrency-interest] ConcurrentSkipListMap performance

Nathan Grasso Bronson nbronson at cs.stanford.edu
Mon Oct 24 11:54:05 EDT 2011


SnapTree has a BSD license

https://github.com/nbronson/snaptree/blob/master/doc/LICENSE

 - Nathan

From:  Ben Manes <ben_manes at yahoo.com>
Reply-To:  Ben Manes <ben_manes at yahoo.com>
Date:  Sun, 23 Oct 2011 18:33:35 -0700 (PDT)
To:  Ted Yu <ted_yu at yahoo.com>
Cc:  "concurrency-interest at cs.oswego.edu"
<concurrency-interest at cs.oswego.edu>
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
<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 ?

Thanks



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.
> 
> https://github.com/mspiegel/lockfreeskiptree
> https://github.com/nbronson/snaptree
> 
> 
> 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
> 
> 
> I 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 them.
> 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.
> This 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 )
> 
> Cheers,
> Akash A
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
> 
> 


_______________________________________________ Concurrency-interest mailing
list Concurrency-interest at cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20111024/62b8e31a/attachment.html>


More information about the Concurrency-interest mailing list