<html><body><div style="color:#000; background-color:#fff; font-family:times new roman, new york, times, serif;font-size:12pt"><div><span>See the file headers. The Skiptree implementation is public domain. The Snaptree is copyrighted by Stanford University (</span><a href="http://ppl.stanford.edu/">http://ppl.stanford.edu</a>) and should fall under their policy for academic research. You can contact the author or the lab for licensing details.</div><div><span><br></span></div><div style="font-size: 12pt; font-family: 'times new roman', 'new york', times, serif; "><div style="font-size: 12pt; font-family: 'times new roman', 'new york', times, serif; "><font size="2" face="Arial"><hr size="1"><b><span style="font-weight:bold;">From:</span></b> Ted Yu <ted_yu@yahoo.com><br><b><span style="font-weight: bold;">To:</span></b> Ben Manes <ben_manes@yahoo.com><br><b><span style="font-weight: bold;">Cc:</span></b> "concurrency-interest@cs.oswego.edu"
 <concurrency-interest@cs.oswego.edu><br><b><span style="font-weight: bold;">Sent:</span></b> Sunday, October 23, 2011 5:24 PM<br><b><span style="font-weight: bold;">Subject:</span></b> Re: [concurrency-interest] ConcurrentSkipListMap performance<br></font><br>
<div id="yiv552825413"><div><div>Is either or both of the following compatible with Apache license 2.0 ?</div><div><br></div><div>Thanks<br><br><div><br></div></div><div><br>On Oct 23, 2011, at 12:58 PM, Ben Manes <<a rel="nofollow" ymailto="mailto:ben_manes@yahoo.com" target="_blank" href="mailto:ben_manes@yahoo.com">ben_manes@yahoo.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-size: 12pt; font-family: 'times new roman', 'new york', times, serif; "><div style="font-size: 12pt; font-family: times, serif; "><span class="yiv552825413Apple-style-span" style="font-size: 14px; line-height: 20px; font-family: arial, FreeSans, Helvetica, sans-serif; ">There's not enough information to diagnose the cause, but you may want to try one of the CSLM replacements</span><span class="yiv552825413Apple-style-span" style="font-size: 14px; line-height: 20px; font-family: arial,
 FreeSans, Helvetica, sans-serif; ">.</span><br></div><div style="font-size: 12pt; font-family: times, serif; "><br></div><div style="font-size: 12pt; font-family: times, serif; "><span class="yiv552825413Apple-style-span" style="font-size: 14px; line-height: 20px; font-family: arial, FreeSans, Helvetica, sans-serif; "><a rel="nofollow" target="_blank" href="https://github.com/mspiegel/lockfreeskiptree" style="color:rgb(60, 120, 181);cursor:pointer;">https://github.com/mspiegel/lockfreeskiptree</a></span></div><div style="font-size: 12pt; font-family: times, serif; "><span class="yiv552825413Apple-style-span" style="font-size: 14px; line-height: 20px; font-family: arial, FreeSans, Helvetica, sans-serif; "><a rel="nofollow" target="_blank" href="https://github.com/nbronson/snaptree" style="color:rgb(60, 120, 181);text-decoration:none;cursor:pointer;">https://github.com/nbronson/snaptree</a></span><br></div><div style="font-size: 12pt; font-family: times,
 serif; "><span class="yiv552825413Apple-style-span" style="font-size: 14px; line-height: 20px; font-family: arial, FreeSans, Helvetica, sans-serif; "><br></span></div><div style="font-size: 12pt; font-family: times, serif; "><div style="font-size: 12pt; font-family: times, serif; "><font size="2" face="Arial"><hr size="1"><b><span style="font-weight:bold;">From:</span></b> Ted Yu <<a rel="nofollow" ymailto="mailto:ted_yu@yahoo.com" target="_blank" href="mailto:ted_yu@yahoo.com">ted_yu@yahoo.com</a>><br><b><span style="font-weight:bold;">To:</span></b> "<a rel="nofollow" ymailto="mailto:concurrency-interest@cs.oswego.edu" target="_blank" href="mailto:concurrency-interest@cs.oswego.edu">concurrency-interest@cs.oswego.edu</a>" <<a rel="nofollow" ymailto="mailto:concurrency-interest@cs.oswego.edu" target="_blank" href="mailto:concurrency-interest@cs.oswego.edu">concurrency-interest@cs.oswego.edu</a>><br><b><span
 style="font-weight:bold;">Sent:</span></b> Sunday, October 23, 2011 12:01 PM<br><b><span style="font-weight:bold;">Subject:</span></b> [concurrency-interest] ConcurrentSkipListMap performance<br></font><br>
<div id="yiv552825413"><div><div style="color: rgb(0, 0, 0); background-color: rgb(255, 255, 255); font-size: 12pt; font-family: times, serif; ">HBase expects ConcurrentSkipListMap to have good performance.<br>See the following discussion.<br><br>Comments are welcome.<br><br>---------- Forwarded message ----------<br>
From: <b class="yiv552825413gmail_sendername">Akash Ashok</b> <span dir="ltr"><<a rel="nofollow" ymailto="mailto:thehellmaker@gmail.com" target="_blank" href="mailto:thehellmaker@gmail.com">thehellmaker@gmail.com</a>></span><br>
Date: Sun, Oct 23, 2011 at 2:57 AM<br>Subject: Re: SILT - nice keyvalue store paper<br>To: <a rel="nofollow" ymailto="mailto:dev@hbase.apache.org" target="_blank" href="mailto:dev@hbase.apache.org">dev@hbase.apache.org</a><br><br><br>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.<br>


Surprisingly synchronized treeMap performed better, though just slightly
 better, than ConcurrentSkipListMap which KeyValueSkipListSet uses.<br><br>Here are the output of a few runs<br><br>Sometimes the difference was considerable<br>


Using HBaseMap it took 20438ms<br>Using TreeMap it took 11613ms<br>Time Difference:8825ms<br><br>And sometimes the difference was negligible<br>Using HBaseMap it took 13370ms<br>Using TreeMap it took 9482ms<br>Time Difference:3888ms<br>


<br>I've attaching the test  java file which I wrote to test it. <br>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.<br>


<br>And here are the details about the test run.<br>100 Threads each fetching 10,000 records<br>100 threads each adding 10,000 records.<br>100 threads each deletin 10,000 records<br>( Reads, Writes and deletes simultaneously )<br>


<br>Cheers,<br>Akash A</div></div></div><br>_______________________________________________<br>Concurrency-interest mailing list<br><a rel="nofollow" ymailto="mailto:Concurrency-interest@cs.oswego.edu" target="_blank" href="mailto:Concurrency-interest@cs.oswego.edu">Concurrency-interest@cs.oswego.edu</a><br>http://cs.oswego.edu/mailman/listinfo/concurrency-interest<br><br><br></div></div></div></div></blockquote></div></div><br><br></div></div></div></body></html>