Sometimes you just need a small simple cache for calculated values because the value generation is expensive in time or resources. In this post I show how such a cache can be implemented in a thread safe way with the Java8 version of the ConcurrentHashMap class with just 2 lines of relevant code.
For this example I use the calculation of the n-th fibonacci number and calculate the values for there input of 1 to 20.
using no cache
The sample program and the first version of the fibonacci() method without caching are as follows:
package com.sothawo;
import java.math.BigInteger;
public class App {
private BigInteger fibonacci(int n) {
return (n <= 2) ? BigInteger.ONE : fibonacci(n - 1).add(fibonacci(n - 2));
}
public static void main(String[] args) {
new App().run();
}
private void run() {
for (int i = 1; i <= 20; i++) {
System.out.println("fibonacci(" + i + ") is " + fibonacci(i));
}
}
}
This program produces the desired results, but due to the recursion there are 35.400 calls of the fibonacci() method, as already calculated values are recalculated again and again.
pre-Java 8 cache
As a cache I use a HashMap and guard it’s use with a lock object to ensure thread safety. The modified program looks like this:
package com.sothawo;
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
public class App {
private Map<Integer, BigInteger> simpleCache = new HashMap<>();
private Object simpleCacheLock = new Object();
private BigInteger fibonacci(int n) {
BigInteger fib;
synchronized (simpleCacheLock) {
fib = simpleCache.get(n);
if (null == fib) {
fib = (n <= 2) ? BigInteger.ONE : fibonacci(n - 1).add(fibonacci(n - 2));
simpleCache.put(n, fib);
}
}
return fib;
}
public static void main(String[] args) {
new App().run();
}
private void run() {
for (int i = 1; i <= 20; i++) {
System.out.println("fibonacci(" + i + ") is " + fibonacci(i));
}
}
}
This works as expected and gets the number of calls to the fibonacci() method down to the minimum of 20, but is a lot of code.
Java 8 version
The ConcurrentHashMap in Java 8 has got a nice addition, the computeIfAbsent method. It takes two arguments: the key value and a function to calculate the value if not present in the cache. This leads to the following code:
package com.sothawo;
import java.math.BigInteger;
import java.util.concurrent.ConcurrentHashMap;
public class App {
private ConcurrentHashMap<Integer, BigInteger> betterCache = new ConcurrentHashMap<>();
private BigInteger fibonacci(int n) {
return betterCache.computeIfAbsent(n, (i) -> (i <= 2) ? BigInteger.ONE : fibonacci(i - 1).add(fibonacci(i - 2)));
}
public static void main(String[] args) {
new App().run();
}
private void run() {
for (int i = 1; i <= 20; i++) {
System.out.println("fibonacci(" + i + ") is " + fibonacci(i));
}
}
}
The same result as before, but with just two lines of code.
Very nice post. Thank you.
In no cache approach we could produce Fibonacci program result by bottom up approach(Dynamic programming). it takes less time than recursive and memoize approaches.
/*
* fib series by bottom up approach method
*/
public static int fib_by_bottom_up_approach(int number){
int[] bottom = new int[number];
bottom[0] = 1;
bottom[1] = 1;
for(int i=2;i<bottom.length;i++){
bottom[i] = bottom[i-1]+bottom[i-2];
}
return bottom[number-1];
}
How do we define a record eviction policy in such a local cache ?
I wouldn’t use this approach for more than the basic cache functionality, this post just showed how Java 8 added the possibility to do such things with lambdas and some functions like `computIfAbsent`.
For caches that are better configurable espeicially with regard to cache eviction I would recommend to look at the Google Guava Caches (https://github.com/google/guava/wiki/CachesExplained) before writing somethign yourself.