<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On 27 Jan 2010, at 15:29, Vladimir Blagojevic wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">Hi all,</span></font><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">As you probably recall I am working on a LIRS eviction algorithm. But before we get there, Manik and I agreed that I push in a direction of implementing ConcurrentHashMap(CHM) variant that will do lock amortization and eviction per segment of CHM. So far I have implemented LRU eviction so we can verify feasibility of this approach rather than eviction algorithm itself. We are hoping that eviction algorithm precision will not suffer if we do eviction per segment and you all are familiar with lock striping benefits of segments in CHM. </span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">So, I've cobbled up a first test to compare eviction and lock amortized enabled CHM (BCHM) with regular CHM and synchronized HashMap. The test is actually based on already existing test [1] used to measure performance of various DataContainers. I've changed it slightly to measure Map directly instead of DataContainer. The test launches in cohort 48 reader, 4 writer and 1 remover threads. All operations are randomized; readers execute map.get(R.nextInt(NUM_KEYS), writers map.put(R.nextInt(NUM_KEYS), "value"), and finally removers execute map.remove(R.nextInt(NUM_KEYS). NUM_KEYS was set to 10K. Each thread does in a loop 1K ops. </span></font></div></div></blockquote><div><br></div><div>Can we think of a better way to generate keys here? The problem with having random.nextInt() within the timed loop is that you are effectively measuring how quick your random impl is. :)</div><div><br></div><div>Perhaps generate an array of random keys, and then have each thread just increment an offset on the array to get the key? This offset could be a simple int, no need for an AtomicInt since the consequences of inaccuracy are just that you get a different random key, and the costs are unnecessary CAS.</div><br><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><span class="Apple-style-span" style="font-family: Arial; font-size: 12px; ">Initial capacity for CHM and HashMap were set to 1K, max capacity for eviction and lock amortized enabled CHM was set to 256; therefore BCHM has to do a lot of evictions which is evident in map final size listed below.</span></div></div></blockquote><div><br></div><div>What happens when the BCHM is bounded at something higher, e.g., 1024? We would have fewer eviction events?</div><br><blockquote type="cite"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Size = 9999</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Performance for container ConcurrentHashMap</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average get ops/ms 338</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average put ops/ms 87</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average remove ops/ms 171</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Size = 193</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Performance for container BufferedConcurrentHashMap</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average get ops/ms 322</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average put ops/ms 32</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average remove ops/ms 74</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Size = 8340</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Performance for container SynchronizedMap</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average get ops/ms 67</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average put ops/ms 45</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; ">Average remove ops/ms 63</div></div></div></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><br></div></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px; ">If I remove lock amortization for <span class="Apple-style-span" style="font-family: 'Lucida Grande'; font-size: 11px; ">BufferedConcurrentHashMap, that is if we attempt eviction on every get/put/remove, performance of put/remove for BCHM goes to zero basically!</span> As far as I can interpret these results, BCHM get operation performance does not suffer at all in comparison with CHM as it does for single lock HashMap. Predictably, for single lock HashMap each type of operation takes on avg almost the same amount of time. We pay a hit in BCHM put/remove operations in comparison with CHM but the numbers are promising, I think. If you have comments, or even suggestions on how to test these map variants in a different, possibly more insightful approach, speak up! </span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">Cheers,</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 11px/normal 'Lucida Grande'; "><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">Vladimir</span></font></div></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px; "><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;">[1] <a href="http://fisheye.jboss.org/browse/~raw,r=1264/Infinispan/trunk/core/src/test/java/org/infinispan/stress/DataContainerStressTest.java">http://fisheye.jboss.org/browse/~raw,r=1264/Infinispan/trunk/core/src/test/java/org/infinispan/stress/DataContainerStressTest.java</a></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px; "><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"><br></span></font></div><div><font class="Apple-style-span" face="Arial" size="3"><span class="Apple-style-span" style="font-size: 12px;"> </span></font></div><div><br></div></div>_______________________________________________<br>infinispan-dev mailing list<br><a href="mailto:infinispan-dev@lists.jboss.org">infinispan-dev@lists.jboss.org</a><br>https://lists.jboss.org/mailman/listinfo/infinispan-dev</blockquote></div><br><div>
<span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>--</div><div>Manik Surtani</div><div><a href="mailto:manik@jboss.org">manik@jboss.org</a></div><div>Lead, Infinispan</div><div>Lead, JBoss Cache</div><div><a href="http://www.infinispan.org">http://www.infinispan.org</a></div><div><a href="http://www.jbosscache.org">http://www.jbosscache.org</a></div><div><br></div></div></span><br class="Apple-interchange-newline"></span><br class="Apple-interchange-newline">
</div>
<br></body></html>