5

I have seen the following code, and I think that there is a useless while loop in the implementation of addElement method. It should never happen to have more elements than size+1 since there is already a write lock. So why is the addElement method removing elements till it gets this condition true

while(concurrentLinkedQueue.size() >=maxSize)

Any pointers around this would be great.

Here is the Implementation:

public class  LRUCache<K,V> {

    private  ConcurrentLinkedQueue<K> concurrentLinkedQueue = new ConcurrentLinkedQueue<K>();

    private  ConcurrentHashMap<K,V> concurrentHashMap = new ConcurrentHashMap<K, V>();

    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock();

    private Lock readLock = readWriteLock.readLock();

    private Lock writeLock = readWriteLock.writeLock();

    int maxSize=0;

    public LRUCache(final int MAX_SIZE){
        this.maxSize=MAX_SIZE;
    }

    public V getElement(K key){

        readLock.lock();
        try {
        V v=null;
          if(concurrentHashMap.contains(key)){
              concurrentLinkedQueue.remove(key);
              v= concurrentHashMap.get(key);
                concurrentLinkedQueue.add(key);
          }


        return v;
        }finally{
            readLock.unlock();
        }
    }

    public V removeElement(K key){
         writeLock.lock();
         try {
        V v=null;
        if(concurrentHashMap.contains(key)){
        v=concurrentHashMap.remove(key);
            concurrentLinkedQueue.remove(key);
        }

        return v;
         } finally {
             writeLock.unlock();
         }
    }

    public V addElement(K key,V value){
        writeLock.lock();
        try {
        if(concurrentHashMap.contains(key)){
             concurrentLinkedQueue.remove(key);
        }
        while(concurrentLinkedQueue.size() >=maxSize){
             K queueKey=concurrentLinkedQueue.poll();
             concurrentHashMap.remove(queueKey);
        }
        concurrentLinkedQueue.add(key);
        concurrentHashMap.put(key, value);

        return value;
        } finally{
            writeLock.unlock();
        }
    }
}
Sandeep Kaul
  • 2,957
  • 2
  • 20
  • 36
  • 1
    fyi: `ConcurrentLinkedQueue#size` requires a full scan, whereas `ConcurrentHashMap#size` is tracked. Your implementation is O(n), whereas efficient implementations are O(1). You may be interested in reading the [design](https://github.com/ben-manes/caffeine/wiki/Design) of a concurrent LRU cache. – Ben Manes May 08 '15 at 22:39
  • You can find working solutions on following link: http://stackoverflow.com/questions/6398902/best-way-to-implement-lru-cache – vaquar khan Oct 15 '15 at 14:50
  • Since thread safety is ensured by using locks, i believe there is no need of using concurrent version of map and queue. It is just an overhead – Sahil Gupta Jul 15 '16 at 03:52

3 Answers3

0

the point here is, i guess, that you need to check if the LRU is at it's maximum size. the check here is NOT (map.size() > maxSize), it is ">=". now, you could probably replace that with "if (map.size() == maxSize) {...}" - which, in ideal conditions, should do exactly the same thing.

but in not-so-ideal conditions, if for whatever reason, somebody put an EXTRA entry in the map without checking, then with this code, the map would NEVER go down in size again, because the if condition would never be true.

so - why not "while" and ">=" instead of "if" and "=="? same amount of code, plus more robust against "unexpected" conditions.

rmalchow
  • 2,689
  • 18
  • 31
0

An easy implementation of an LRU cache does the following, a while loop is only need when the max size is adjusted, but not for the primitive operations:

  • During put, remove superflous element.
  • During get, move element to top.

The primitive operations will be one shot. You can then use either ordinary synchronized or read write lock around this data structure.

When using read write locks the fairness on who comes first is then rather an issue of the used read write locks than of the LRU cache itself.

Here is a sample implementation.

0

It's not wrong but just a safety in case of accidental modification. You could check for equality with concurrentLinkedQueue.size() == maxSize in a conditional statement.

Sawan
  • 236
  • 3
  • 12