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.
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.
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];
}
Very nice post. Thank you.