6
\$\begingroup\$

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?

\$\endgroup\$
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Looks good, simple, and clean. Not sure what's causing the formatting issues, I'm using eclipse; and you're seriously bashing my indentation preference? :-) Let me guess, you're using 4, not 3, spaces? :-) \$\endgroup\$ – raffian Feb 11 '15 at 14:44
  • \$\begingroup\$ I am not particularly set on specific indentation 'rules', (even 3-space, or ){ on a line of its own) just so long as there is consistency. The whitespace at the end of lines is odd. If you are using Eclipse, I recommend configuring the format rules to suit your local community, and then hitting Ctrl-A & Ctrl-shift-F \$\endgroup\$ – rolfl Feb 11 '15 at 14:49
  • \$\begingroup\$ Actually, whitespace was an issue, I corrected that; ty :-) \$\endgroup\$ – raffian Feb 11 '15 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.