[infinispan-dev] Initial LIRS implementation

Bryan Thompson bryan at systap.com
Sun Feb 7 20:19:04 EST 2010 

Vladimir,

I am thinking that the right approach is a class which encapsulates:

(a) an unmodified ConcurrentHashMap;  combined with

(b) per-thread non-thread-safe buffers for touches; which get batched onto

(c) a shared non-thread safe access policy (LIRS, LRU); and

(d) explicit management of the threads used to access the cache. e.g.,
    by queuing accepted requests and servicing them out of a thread
    pool.

This should have the best possible performance and the simplest
implementation.  (b) can be use an Object[].  (c) can be composed from
simple arrays or other non-thread safe data structures.  Both batching
touches onto (c) and eviction (per the policy) require access to a
lock for (c), but that is the only lock.  If the policy batches
evictions, then lock requests will be rare and the whole cache will be
non-blocking, wait free, and not spinning on CAS locks 99% of the
time.

Bryan

________________________________________
From: Vladimir Blagojevic [vblagoje at redhat.com]
Sent: Sunday, February 07, 2010 7:55 AM
To: Bryan Thompson
Cc: infinispan -Dev List
Subject: Re: [infinispan-dev] Initial LIRS implementation

Hey Bryan,

Does it happen with LIRS as well? Pick up the latest version from svn so we know which file to look at. I've never seen this kind of exception in compareAndSwap, anyone?

Vladimir

On 2010-02-06, at 7:53 PM, Bryan Thompson wrote:

> Vladimir,
>
> I believe that there is a lock problem with the BufferedConcurrentHashMap.  This code path does not progress.  What is strange is that this is the only thread in the thread dump that is in BufferedConcurrentHashMap, which suggests a lock ordering problem.  I don't see the problem offhand, but this happens everytime I run our application with the BufferedConcurrentHashMap.
>
> Bryan
>
> "Thread-3" prio=10 tid=0x00002aafec141000 nid=0x41ba runnable [0x0000000040737000]
>   java.lang.Thread.State: RUNNABLE
>        at sun.misc.Unsafe.$$YJP$$compareAndSwapInt(Native Method)
>        at sun.misc.Unsafe.compareAndSwapInt(Unsafe.java)
>        at java.util.concurrent.locks.AbstractQueuedSynchronizer.compareAndSetState(AbstractQueuedSynchronizer.java:526)
>        at java.util.concurrent.locks.ReentrantLock$NonfairSync.lock(ReentrantLock.java:183)
>        at java.util.concurrent.locks.ReentrantLock.lock(ReentrantLock.java:262)
>        at org.infinispan.util.concurrent.BufferedConcurrentHashMap$Segment.remove(BufferedConcurrentHashMap.java:745)
>        at org.infinispan.util.concurrent.BufferedConcurrentHashMap$Segment$LRU.execute(BufferedConcurrentHashMap.java:832)
>        at org.infinispan.util.concurrent.BufferedConcurrentHashMap$Segment.put(BufferedConcurrentHashMap.java:659)
>        at org.infinispan.util.concurrent.BufferedConcurrentHashMap.putIfAbsent(BufferedConcurrentHashMap.java:1421)
>        at com.bigdata.cache.BCHMGlobalLRU$InnerCacheImpl.putIfAbsent(BCHMGlobalLRU.java:633)
>        at com.bigdata.cache.BCHMGlobalLRU$InnerCacheImpl.putIfAbsent(BCHMGlobalLRU.java:557)
>        at com.bigdata.btree.AbstractBTree.readNodeOrLeaf(AbstractBTree.java:3624)
>
> ________________________________________
> From: Bryan Thompson
> Sent: Wednesday, February 03, 2010 5:04 PM
> To: Vladimir Blagojevic
> Cc: infinispan -Dev List
> Subject: RE: [infinispan-dev] Initial LIRS implementation
>
> Vladimir,
>
> Does this match up with what you are seeing?  That is a good win for get()/remove() with a loss on put().
>
> Size = 14698
> Performance for container ConcurrentHashMap
> Average get ops/ms 13931
> Average put ops/ms 306
> Average remove ops/ms 294
>
> Size = 452
> Performance for container BufferedConcurrentHashMap(LRU)
> Average get ops/ms 7735
> Average put ops/ms 140
> Average remove ops/ms 200
>
> Size = 494
> Performance for container BufferedConcurrentHashMap(LIRS)
> Average get ops/ms 13400
> Average put ops/ms 36
> Average remove ops/ms 1136
>
> Bryan
>
>> -----Original Message-----
>> From: Vladimir Blagojevic [mailto:vblagoje at redhat.com]
>> Sent: Wednesday, February 03, 2010 3:36 PM
>> To: Bryan Thompson
>> Subject: Re: [infinispan-dev] Initial LIRS implementation
>>
>> Yes,
>>
>> Have a look at LRU first and leave LIRS for tomorrow :) I'd
>> be happiest if you can find a use case for BCHM+LRU in your
>> application and test it out that way. Real life scenario!
>>
>> Cheers
>>
>> On 2010-02-03, at 3:27 PM, Bryan Thompson wrote:
>>
>>> Ah. It is inside the same outer class? Bryan
>>>
>>>
>>>> -----Original Message-----
>>>> From: Vladimir Blagojevic [mailto:vblagoje at redhat.com]
>>>> Sent: Wednesday, February 03, 2010 2:44 PM
>>>> To: Bryan Thompson
>>>> Subject: Re: [infinispan-dev] Initial LIRS implementation
>>>>
>>>> Here it is:
>>>> http://fisheye.jboss.org/browse/Infinispan/trunk/core/src/main
>>>> /java/org/infinispan/util/concurrent/BufferedConcurrentHashMap.java
>>>>
>>>> Are you familiar with LIRS? If not, don't bother unless you are
>>>> willing to dedicate at least a day or two :(
>>>>
>>>> http://www.ece.eng.wayne.edu/~sjiang/Projects/LIRS/sig02.ppt
>>>> http://citeseer.ist.psu.edu/527790.html
>>>>
>>>> Regards,
>>>> Vladimir
>>>>
>>>>
>>>> On 2010-02-03, at 2:31 PM, Bryan Thompson wrote:
>>>>
>>>>> Can you send me the full class name and I will check it out. Bryan
>>>>>
>>>>>> -----Original Message-----
>>>>>> From: infinispan-dev-bounces at lists.jboss.org
>>>>>> [mailto:infinispan-dev-bounces at lists.jboss.org] On Behalf
>>>> Of Vladimir
>>>>>> Blagojevic
>>>>>> Sent: Wednesday, February 03, 2010 2:09 PM
>>>>>> To: infinispan -Dev List
>>>>>> Subject: [infinispan-dev] Initial LIRS implementation
>>>>>>
>>>>>> Hi,
>>>>>>
>>>>>> I've just committed preliminary attempt to implement LIRS.
>>>>>> There does not seem to be serious degradation in terms of
>>>> performance
>>>>>> when it comes to get/remove commands in comparison with
>>>> LRU enabled
>>>>>> BufferedConcurrentHashMap.
>>>>>> However, put command is about three times slower than in
>>>> LRU; put in
>>>>>> LIRS is as fast as put command of a single lock
>>>> synchronized HashMap.
>>>>>>
>>>>>> Looking for enthusiasts willing to help out with some code
>>>> review :)
>>>>>>
>>>>>> Regards,
>>>>>> Vladimir
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> infinispan-dev mailing list
>>>>>> infinispan-dev at lists.jboss.org
>>>>>> https://lists.jboss.org/mailman/listinfo/infinispan-dev
>>>>>>
>>>>
>>>>
>>
>>

More information about the infinispan-dev mailing list