Least Recently Used or LRU Cache : a simple implementation in Java

A friend of mine asked me about LRU cache and while explaining the same I could not locate a simple implementation one by just googling it.

The Java util provides a beautiful implementation through LinkedHashMap. Which is a Hash table and linked list implementation of the Map interface, with predictable iteration order. In order to use it as an LRU cache, do the following,

  • use constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) and set the accessOrder to true. and,
  • override the implementation for removeEldestEntry(Map.Entry eldest)
  • please keep in mind that this is NOT an thread safe implementation and to have thread safety for this LinkedHashMap, you can do something like Map m = Collections.synchronizedMap(new LinkedHashMap(…)), if multiple threads may use the map.

You can of-course look at the implementation of LinkedHashMap for reference and it is really awesome how implemented but I thought to write up my own implementation for LRU cache using a HashMap and a linked list with minimal functionality. So this implementation provides a LRU cache implementation in Java using Hashmap and a doubly linked list.

package com.das.yadab.java;

import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {
    public static final int MAX_SIZE = 100; // Default max size for the cache to grow.
    private Entry<K, V> head;
    private HashMap<K, Entry> internalCache;
    private int maxSize;

    public LRUCache() {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        maxSize = MAX_SIZE;
    }

    public LRUCache(int maxSize) {
        this.head = new Entry(null, null);
        head.before = head.after = head;
        internalCache = new HashMap<K, Entry>();
        this.maxSize = maxSize;
    }

    /**
     * Gets value associated with the specified key from cache.
     *
     * @param key
     * @return value or null if not found
     */
    public V get(Object key) {
        Entry<K, V> e = internalCache.get(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

    /**
     * Associates key and value in the cache, null value is not allowed.
     * If cache size has grown more than the allowed capacity the eldest member will be evicted.
     *
     * @param key
     * @param value
     * @return
     */
    public V put(K key, V value) {
        if (value == null) {
            throw (new IllegalArgumentException("Null Value association is not helpful in caching"));
        }
        if (shouldRemoveEldestEntry()) {
            Entry eldest = head.after;
            removeEntry(eldest);
        }
        Entry entry = new Entry(key, value);
        if (!internalCache.containsKey(key)) {
            entry.addBefore(head);
        }
        internalCache.put(key, entry);
        return value;
    }

    private void removeEntry(Entry eldest) {
        // since we do not allow null value association so this is safe.
        if (internalCache.remove(eldest.key) != null) {
            eldest.recordRemoval(this);
        }
    }

    /*
    Returns true if this map should remove its eldest entry.
    if maxSize is not set during initialization the method will always return false.
     */
    public boolean shouldRemoveEldestEntry() {
        if (internalCache.size() > maxSize) {
            return true;
        }
        return false;
    }

    static class Entry<K, V> implements Map.Entry<K, V> {
        private Entry<K, V> before, after;
        private K key;
        private V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        private void addBefore(Entry<K, V> existingEntry) {
            after = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(LRUCache<K, V> cache) {
            remove();
            addBefore(cache.head);
        }

        final void recordRemoval(LRUCache<K, V> m) {
            remove();
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry e = (Map.Entry) o;
            Object k1 = getKey();
            Object k2 = e.getKey();
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                Object v1 = getValue();
                Object v2 = e.getValue();
                if (v1 == v2 || (v1 != null && v1.equals(v2)))
                    return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            return (key == null ? 0 : key.hashCode()) ^
                    (value == null ? 0 : value.hashCode());
        }

        @Override
        public String toString() {
            return "Entry key=" + key +
                    ", value=" + value +
                    '}';
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "internalCache=" + internalCache +
                ", head=" + head +
                ", maxSize=" + maxSize +
                '}';
    }
}

An example usage, since it only accesses the key “0”, it should retain the key “0” though it is added at the beginning.

LRUCache cache = new LRUCache(5);
for (int i = 0; i &lt; 10; i++) {
    cache.put(Integer.toString(i), i);
    cache.get(Integer.toString(0));
}
Advertisements

Java : difference between Polymorphism and Inheritance

Since the definition for both them have some common ground so it may confuse some times with the differences between this two paradigm. Definitions from wiki, you might have already read it.

  • Polymorphism polymorphism is the provision of a single interface to entities of different types. Java supports basically subtype(using inheritance in Java) and parametric polymorphism (using generics in Java).
  • Inheritance (OOP) is when an object or class is based on another object (prototypal inheritance) or class (class-based inheritance), using the same implementation (inheriting from an object or class) specifying implementation to maintain the same behavior (realizing an interface; inheriting behavior).

So from the above definition,

  1. Inheritance or subclassing in Java is one of the technique used to achieve polymorphism.
  2. Inheritance refers to using the structure and behavior of a superclass in a subclass.
  3. Inheritance helps code reuse at the same time while achieving polymorphism.

Java : Asynchronous Task sequencing using Observer pattern

The other day I was answering a question on stackoverflow on what could be a simple implementation of sequencing or ordering asynchronous tasks in Java. More detail about the question. Basically task sequencing problem is, you have a list of tasks say : {A, B, C, D} and you want execute them in some order, say {A} -> {B, C} ->{D} ->{X} -> {A}.

I preferred the Observer pattern because it is more of a reactive pattern so that design is reactive in nature rather than controlling and more loosely coupled.

public abstract class Task extends Observable implements Runnable, Observer {
    private final Mutex lock = new Mutex();
    private final String taskId;
    private final Set<String> completedTasks;
    private final Set<String> shouldCompletedTasksBeforeStart;

    public Task(final String taskId) {
        this.taskId = taskId;
        this.completedTasks = new HashSet<>();
        this.shouldCompletedTasksBeforeStart = new HashSet<>();
    }

    public String getTaskId() {
        return this.taskId;
    }

    @Override
    public void run() {
        while (true) {
            this.lock.getLock();
            if (this.completedTasks.equals(this.shouldCompletedTasksBeforeStart)) {
                doWork();
                setChanged();
                notifyObservers(this.taskId);
                // reset
                this.completedTasks.clear();
            }
            this.lock.freeLock();
            try {
                // just some sleep, you change to how it fits you
                Thread.sleep(1000);
            } catch (final InterruptedException e) {
                // TODO Auto-generated catch block
            }
        }
    }

    @Override
    public void update(final Observable observable, final Object arg) {
        this.lock.getLock();
        this.completedTasks.add((String) arg);
        this.lock.freeLock();
    }

    public void addPredecessorTask(final Task task) {
        if (this.taskId.equals(task.taskId)) {
            return;
        }
        this.lock.getLock();
        // Notice here, it is a little logic make your predecessor/successor work
        task.addObserver(this);
        this.shouldCompletedTasksBeforeStart.add(task.taskId);
        this.lock.freeLock();
    }
    protected abstract void doWork();
}

//HelloTask.java
public static class HelloTask extends Task {
    public HelloTask(final String taskId) {
        super(taskId);
    }

    @Override
    protected void doWork() {
        System.out.println("Hello from " + getTaskId() + "!");
    }
}

//Main.java
public class Main {
    public static void main(final String[] args) {
        final HelloTask helloTaskA = new HelloTask("A");
        final HelloTask helloTaskB = new HelloTask("B");
        final HelloTask helloTaskC = new HelloTask("C");

        helloTaskA.addPredecessorTask(helloTaskB);
        helloTaskC.addPredecessorTask(helloTaskB);

        final ExecutorService pool = Executors.newFixedThreadPool(10);
        pool.execute(helloTaskC);
        pool.execute(helloTaskA);
        pool.execute(helloTaskB);

    }
}

Artificial Brain and cryptanalysis

Was reading about different Blue brain or Artificial brain projects and thought of writing a simple network myself. So all I could afford myself is one compute machine from amazon which allows to run 3000 threads only if I am not doing much in each neuron. Each thread is a neuron and after adding little logic of filtering I came down to much lower number. I felt like, what am I doing, so to simulate this in cloud framework, I need the following,

  • A good messaging platform
  • A very lightweight service framework to make it work as neuron

And to able to use this network for doing a cryptanalysis is not far but the brain I produced is a size of an ant or less. I need bigger brain means a lot of machines => a lot of money ??

Example : Using Java future, Callable, Executor and CountDownLatch

When you start using java.util.concurrent’s Future and the thread pools or executor framework, Following questions may come to one’s mind

  • How to do thread join kind of operation ?
  • How to set timeout for future?
  • Can the futures notify back the submitting thread when they are done?

Example explaining usage for future, Callable and CountDownLatch together,

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Callable;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Future;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

public class DataAccessor {
    private static ThreadPoolExecutor executor;
    private int timeout = 100000;
    static {
        executor = new ThreadPoolExecutor(10, 10, 1000, TimeUnit.SECONDS, new ArrayBlockingQueue<Runnable>(1000));
    }

    public static void main(String[] args) {
        List<String> requests = new ArrayList<String>();
        for(int i=0; i<20; i++){
            requests.add("request:"+i);
        }
        DataAccessor dataAccessor = new DataAccessor();

        List<ProcessedResponse> results = dataAccessor.getDataFromService(requests);
        for(ProcessedResponse response:results){
            System.out.println("response"+response.toString()+"\n");
        }
        executor.shutdown();
    }

    public List<ProcessedResponse> getDataFromService(List<String> requests) {
        final CountDownLatch latch = new CountDownLatch(requests.size());
        List<SubmittedJob> submittedJobs = new ArrayList<SubmittedJob>(requests.size());
        for (String request : requests) {
            Future<ProcessedResponse> future = executor.submit(new GetAndProcessResponse(request, latch));
            submittedJobs.add(new SubmittedJob(future, request));
        }
        boolean isAllDone = false;
        try {
            isAllDone = latch.await(timeout, TimeUnit.MILLISECONDS);
            if (!isAllDone) {
                // some of the jobs not done
                System.out.println("some jobs not done");
            }
        } catch (InterruptedException e1) {
            // take care, or cleanup
            for (SubmittedJob job : submittedJobs) {
                job.getFuture().cancel(true);
            }
        }
        List<ProcessedResponse> results = new LinkedList<DataAccessor.ProcessedResponse>();
        for (SubmittedJob job : submittedJobs) {
            try {
                // before doing a get you may check if it is done
                if (!isAllDone && !job.getFuture().isDone()) {
                    // cancel job and continue with others
                    job.getFuture().cancel(true);
                    continue;
                }
                ProcessedResponse response = job.getFuture().get();
                results.add(response);
            } catch (ExecutionException cause) {
                // exceptions occurred during execution, in any
            } catch (InterruptedException e) {
                // take care
            }
        }
        return results;
    }

    private class SubmittedJob {
        final String request;
        final Future<ProcessedResponse> future;

        public Future<ProcessedResponse> getFuture() {
            return future;
        }

        public String getRequest() {
            return request;
        }

        SubmittedJob(final Future<ProcessedResponse> job, final String request) {
            this.future = job;
            this.request = request;
        }
    }

    private class ProcessedResponse {
        private final String request;
        private final String response;

        ProcessedResponse(final String request, final String response) {
            this.request = request;
            this.response = response;
        }

        public String getRequest() {
            return request;
        }

        public String getResponse() {
            return response;
        }

        public String toString(){
            return "[request:"+request+","+"response:"+ response+"]";
        }
    }

    private class GetAndProcessResponse implements Callable<ProcessedResponse> {
        private final String request;
        private final CountDownLatch countDownLatch;

        GetAndProcessResponse(final String request, final CountDownLatch countDownLatch) {
            this.request = request;
            this.countDownLatch = countDownLatch;
        }

        public ProcessedResponse call() {
            try {
                return getAndProcessResponse(this.request);
            } finally {
                countDownLatch.countDown();
            }
        }

        private ProcessedResponse getAndProcessResponse(final String request) {
            // do the service call
            // ........
            if("request:16".equals(request)){
                throw (new RuntimeException("runtime"));
            }
            return (new ProcessedResponse(request, "response.of." + request));
        }
    }
}

Some useful links on c++ constructor

There are lot of issues around c++ constructors, and I have few links that may help;

http://billharlan.com/pub/papers/Managing_Cpp_Objects.html .

Google code style is a helpfull material for that also.

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Classes

constructors should initialize as a rule all member objects in the initialization list

http://www.parashift.com/c%2B%2B-faq-lite/ctors.html#faq-10.6 .

Constructor Design, MSDN;

http://msdn.microsoft.com/en-us/library/ms229060.aspx .

Copy constructor,

http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Copy_Constructors .

C++ Idioms and Best Practices

http://www.cacr.caltech.edu/~sean/projects/stlib/html/idioms.html .

One very important point (my learning), you should have default constructor defined, either private or public !

simple C/C++ Serialization or deflating or Marshalling user defined data types or objects

But is it to use boost or not it is your decision 🙂  It is a good lib. But I find it very handy for small in another way as below;-

// Just a simple serialization in C++
#ifndef CVARIABLELENDATA_HPP
#define CVARIABLELENDATA_HPP

#include &lt;string&gt;

typedef char*	BuffPtr;
typedef size_t	BuffLen;

class CVariableLenData
{
public:
	//Serilizes data members to a char buffer
	void Serialize(BuffPtr &amp;ptr, BuffLen len, BuffLen &amp;writelen) const;

	//DeSerilizes from a char buffer &amp; constructs an object
	static CVariableLenData* DeSerialize(const BuffPtr ptr, BuffLen len);

	void SetData(std::string&amp; str);
	void SetData(int&amp; val);

	CVariableLenData();
private:
	int m_some_int;			// fixed length
	std::string m_some_str; // variable length
	CVariableLenData(const CVariableLenData&amp;);
};

#endif //CVARIABLELENDATA_HPP

// Source file
#include &lt;cstdio&gt;
#include "CVariableLenData.h"

using namespace std;

CVariableLenData::CVariableLenData():m_some_int(0),m_some_str(){}

void CVariableLenData::Serialize(BuffPtr &amp;ptr, BuffLen bufflen, BuffLen&amp; writelen) const
{
	if(!ptr)
		return;
	writelen = _snprintf (ptr, bufflen,"%d", m_some_int);
	*(ptr+writelen) = ' ';		// after each numeric value add an space
	size_t len = writelen + 1;
	// now write the string
	// copy length
	writelen = _snprintf ( (ptr+len), bufflen,"%u", m_some_str.length());
	*(ptr + len ) = ' ';
	len = len + writelen + 1;
	// Copy the data
	memcpy( (ptr+len), m_some_str.c_str(), m_some_str.length());
	writelen = len;
	return;
}

Some links.