<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=us-ascii">
<META content="MSHTML 6.00.6000.16945" name=GENERATOR></HEAD>
<BODY
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>Vladimir,</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010></SPAN></FONT> </DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>So, you wind up with per-segment LRU orderings then,
not global? When you batch through, it is from the per-segment accessQueue
to the per-segment LRU, right?</SPAN></FONT></DIV><BR>I have recently been
bitten by non-blocking constructions which fail under high concurrency.
For example, I was using AtomicLong for a performance counter -- with disastrous
results. Under high contention, it winds up attempting to CAS without a
change in its precondition, and failing and retrying again and again to get
through the race. This actually became the #1 hot spot in the code with an
active thread pool.</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010></SPAN></FONT> </DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>So, I am very strongly in favor of using non-thread
safe data structures under conditions where you know that you have single
threaded access rather than "non-blocking" data structured. For example,
it might be cheaper to make the accessQueue a straight array or a ring buffer
that was not thread safe and to use the segment lock to guard
it.</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010></SPAN></FONT> </DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>Maybe the better design is to explicitly manage the
threads with access to the DataContainer and use thread-locals. That would
be both non-blocking (until the updates are batches) and would avoid the
possibility of high concurrency CAS spins.</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010></SPAN></FONT> </DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>I will play with things and see what hot spots turn
up.</SPAN></FONT></DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010></SPAN></FONT> </DIV>
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff size=4><SPAN
class=537343119-03022010>Bryan</SPAN></FONT></DIV>
<DIV dir=ltr align=left><SPAN class=537343119-03022010><FONT face="Courier New"
color=#0000ff size=4> </FONT></SPAN><SPAN
class=537343119-03022010> </SPAN></DIV>
<DIV dir=ltr align=left>
<HR tabIndex=-1>
</DIV>
<DIV dir=ltr align=left><FONT face=Tahoma size=2><B>From:</B>
infinispan-dev-bounces@lists.jboss.org
[mailto:infinispan-dev-bounces@lists.jboss.org] <B>On Behalf Of </B>Vladimir
Blagojevic<BR><B>Sent:</B> Wednesday, February 03, 2010 10:00 AM<BR><B>To:</B>
infinispan -Dev List<BR><B>Cc:</B> Martyn Cutcher; Vladimir
Kondratyev<BR><B>Subject:</B> Re: [infinispan-dev] Lock amortization preliminary
performance numbers<BR></FONT><BR></DIV>
<BLOCKQUOTE dir=ltr
style="PADDING-LEFT: 5px; MARGIN-LEFT: 5px; BORDER-LEFT: #0000ff 2px solid; MARGIN-RIGHT: 0px">
<DIV></DIV>Bryan,
<DIV><BR></DIV>
<DIV>
<DIV>
<DIV>On 2010-02-02, at 7:49 PM, Bryan Thompson 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">
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>Vladimir,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>I now have a workload where I have a
hotspot on our cache which is 8% of the total time. I am going to use
this to test BCHM under a realistic workload.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>One thing which I like about your
design is that by placing the array buffering the operations for a thread
within the Segment, you are using the lock guarding the Segment to control
updates to that array. While this has less potential throughput than a
truely thread-local design (which is non-blocking until the thread-local
array is full), it seems that the array buffering the updates can not
"escape" under your design. Was this intentional?</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff
size=4></FONT></SPAN></DIV></DIV></BLOCKQUOTE>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT><BR></DIV>
<DIV>Yes. Escaping could also potentially be handled by shared pool of array
buffers. Ideally shared pool would be some lock free structure since
there would be a lot of contention among threads for these array buffers
(that record accesses)</DIV>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT> </DIV>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT><BR></DIV><BR>
<BLOCKQUOTE type="cite">
<DIV
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV dir=ltr align=left><FONT face="Courier New" color=#0000ff
size=4></FONT> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>The danger with a true thread-local
design is that a thread can come in and do some work, get some updates
buffered in its thread-local array, and then never visit again. In
this case those updates would remain buffered on the thread and would not in
fact cause the access order to be updated in a timely manner. Worse,
if you are relying on WeakReference semantics, the buffered updates would
remain strongly reachable and the corresponding objects would be wired into
the cache.</FONT></SPAN></DIV></DIV></BLOCKQUOTE>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT><BR></DIV>
<DIV>Not if you return updates into above mentioned pool as the thread unwinds
from call into cache (container). </DIV><BR>
<BLOCKQUOTE type="cite">
<DIV
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>I've worked around this issue in a
different context where it made sense to scope the buffers to an owning
object (a B+Tree instance). In that case, when the B+Tree container
was closed, all buffered updates were discarded. This nicely
eliminated the problems with "escaping"
threads.</FONT></SPAN></DIV></DIV></BLOCKQUOTE>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT><BR></DIV>Yes, there
has to be some container boundary! In Infinispan this would be a cache
instance, DataContainer to be exact. </DIV>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT><BR>
<BLOCKQUOTE type="cite">
<DIV
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>However, I like your approach
better.</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=131211200-03022010><FONT
face="Courier New" color=#0000ff size=4>Bryan</FONT></SPAN></DIV>
<DIV><FONT face="Courier New" color=#0000ff size=4></FONT> </DIV>
<DIV><SPAN class=131211200-03022010><FONT face="Courier New" color=#0000ff
size=4>PS: I see a comment on LRU#onEntryHit() indicating that it is invoked
without holding the Segment lock. Is that true only when BCHM#get() is
invoked?</FONT></SPAN></DIV></DIV></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>Yes, I'll change javadoc to say : "is potentially invoked without holding
a lock".</DIV><BR>
<BLOCKQUOTE type="cite">
<DIV
style="WORD-WRAP: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space">
<DIV><SPAN class=131211200-03022010><FONT face="Courier New" color=#0000ff
size=4></FONT></SPAN> </DIV>
<DIV><SPAN class=131211200-03022010><FONT face="Courier New" color=#0000ff
size=4>PPS: Also, can you expand on the role of the LRU#accessQueue vs
LRU#lruQueue? Is there anything which corresponds to the total LRU
order (after batching updates through the
Segment)?</FONT></SPAN></DIV></DIV></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV><BR></DIV>
<DIV>LRU#accessQueue records hits on a Segment. This is the batching FIFO
queue from BP-Wrapper paper except it is not per thread but rather per
Segment. Notice that LRU#accessQueue is lock free but thread safe since we
expect a lot of threads recording accesses per Segment. Ideal collection for
this use case is <SPAN class=Apple-style-span
style="FONT-SIZE: 11px; FONT-FAMILY: 'Lucida Grande'">ConcurrentLinkedQueue. </SPAN></DIV>
<DIV><BR></DIV>
<DIV>LRU#lruQueue is simply just a simple LRU stack implementation with one
end of the queue holding most recently accessed entries and the other end of
the queue with least recently accessed entries.</DIV>
<DIV><BR></DIV>
<DIV><BR></DIV>
<DIV>Regards,</DIV>
<DIV>Vladimir</DIV>
<DIV><BR></DIV>
<DIV><BR></DIV></DIV></DIV></BLOCKQUOTE></BODY></HTML>