Concurrent LRU cache using sychronizedMap() or ReadWriteLock

Question

Trying to implement a simple, thread-safe LRU cache that's meant for "read mostly" use.

Collections.sychronizedMap()

Clean, simple, not much else to say.

public class LRUConcurrentCache<K,V> {   
   private final Map<K,V> cache;   
   private final int maxEntries;

   public LRUConcurrentCache(
         int maxEntries
   ){
      this.maxEntries = maxEntries;            
      this.cache = Collections.synchronizedMap(
         new LinkedHashMap<K,V>(this.maxEntries, 0.75F, true){                       
               private static final long serialVersionUID = -1236481390177598762L;
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){            
                  return size() > maxEntries;
               }
            });
   }
   public void put(K key, V value){
      cache.put(key, value);
   }
   public V get(K key){
      return cache.get(key);
   }

ReadWriteLock

Seems like overkill, and frankly, I believe get() should use writeLock(), not readLock() since LinkedHashMap.get() records access by manipulating entries.

public class LRUConcurrentCache<K,V> {   
   private final Map<K,V> cache;   
   private final int maxEntries;
   private final ReadWriteLock readWriteLock;
   private final Lock readLock;
   private final Lock writeLock;

   public LRUConcurrentCache(
         int maxEntries
   ){
      this.maxEntries = maxEntries;            
      this.cache = 
         new LinkedHashMap<K,V>(this.maxEntries, 0.75F, true){                       
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){            
                  return size() > maxEntries;
               }
            };
      this.readWriteLock = new ReentrantReadWriteLock(true);
      this.readLock = readWriteLock.readLock();
      this.writeLock = readWriteLock.writeLock();
   }
   public void put(K key, V value){
      writeLock.lock();
      try{
         cache.put(key, value);
      }finally{
         writeLock.unlock();
      }
   }
   public V get(K key){
      //should use writeLock.lock()
      readLock.lock();
      try{
         return cache.get(key);
      }finally{
         //should be writeLock()
         readLock.unlock();
      }
   }

Thoughts?

Answer 1

My experience with variants on the java.util.concurrent.locks.* classes suggests that their sweet spot in terms of performance is when the work to be done is relatively substantial compared to the lock overhead time. Remember, when you use Reentrant or ReadWrite locks, that there is a a call at both the beginning and end of the locked block.

As a consequence, I would advise against the ReadWriteLock system you have going. Apart from other things, it is not implemented correctly because, yes, multiple threads can be 'getting' values from the backing map, and they could each be modifying the access order. get(...) is not a read-only operation. It has side-effects.

Still, I don't like alternative of using Collections.synchronizedMap(...). This also has overheads, and can cause additional members in the call-stack as one synchronized method may call another, etc.

The most simple solution, and the one I recommend, would be to use plain-old-synchronization:

   private final Map<K,V> cache;   

   public LRUConcurrentCache(final int maxEntries) {
      this.cache = new LinkedHashMap<K,V>(maxEntries, 0.75F, true) {
               private static final long serialVersionUID = -1236481390177598762L;
               @Override
               protected boolean removeEldestEntry(Map.Entry<K,V> eldest){            
                  return size() > maxEntries;
               }
            };
   }

   public void put(K key, V value) {
       synchronized(cache) {
          cache.put(key, value);
       }
   }
   public V get(K key) {
       synchronized(cache) {
           return cache.get(key);
       }
   }

Note, while going through the code, I made the following additional changes:

1. I made the input parameter to the constructor maxEntries a final value. This means you can reference it from the constructor and removeEldestEntry methods of the LinkedHashMap without having to re-declare it on the instance
2. Your indentation is all off.... 3-space indents? That's unusual.
3. You have a lot of trailing white-space in your code. You do a block-based select instead of text-based?
4. Your whitespace handling before/after braces and operators is inconsistent.

I get the impression you are using vim or some other console editor to manage your code. You should consider the gg=G shortcut in vim to re-indent all your code consistently.