1. Overview
In this tutorial, we’ll explore the memoization features of Googles’ Guava library.
Memoization is a technique that avoids repeated execution of a computationally expensive function by caching the result of the first execution of the function.
1.1. Memoization vs. Caching
Memoization is similar to caching with regards to memory storage. Both techniques attempt to increase efficiency by reducing the number of calls to computationally expensive code.
However, whereas caching is a more generic term that addresses the problem at the level of class instantiation, object retrieval, or content retrieval, memoization solves the problem at the level of method/function execution.
1.2. Guava Memoizer and Guava Cache
Guava supports both memoization and caching. Memoization applies to functions with no argument (Supplier) and functions with exactly one argument (Function). Supplier and Function here refer to Guava functional interfaces which are direct subclasses of Java 8 Functional API interfaces of the same names.
As of version 23.6, Guava doesn’t support memoization of functions with more than one argument.
We can call memoization APIs on-demand and specify an eviction policy which controls the number of entries held in memory and prevents the uncontrolled growth of memory in use by evicting/removing an entry from the cache once it matches the condition of the policy.
Function Memoization can be implemented using Guava Cache (section 3); for more detailed information regarding Guava Cache, please refer to our Guava Cache article.
2. Supplier Memoization
There are two methods in the Suppliers class that enable memoization: memoize, and memoizeWithExpiration.
When we want to execute the memoized method, we can simply call the get method of the returned Supplier. Depending on whether the method’s return value exists in memory, the get method will either return the in-memory value or execute the memoized method and pass the return value to the caller.
Let’s explore each method of the Supplier‘s memoization.
2.1. Supplier Memoization Without Eviction
We can use the Suppliers‘ memoize method and specify the delegated Supplier as a method reference:
Supplier<String> memoizedSupplier = Suppliers.memoize(
CostlySupplier::generateBigNumber);
Since we haven’t specified an eviction policy, once the get method is called, the returned value will persist in memory while the Java application is still running. Any calls to get after the initial call will return the memoized value.
2.2. Supplier Memoization With Eviction by Time-To-Live (TTL)
Suppose we only want to keep the returned value from the Supplier in the memo for a certain period.
We can use the Suppliers‘ memoizeWithExpiration method and specify the expiration time with its corresponding time unit (e.g., second, minute), in addition to the delegated Supplier:
Supplier<String> memoizedSupplier = Suppliers.memoizeWithExpiration(
CostlySupplier::generateBigNumber, 5, TimeUnit.SECONDS);
After the specified time has passed (5 seconds), the cache will evict the returned value of the Supplier from memory and any subsequent call to the get method will re-execute generateBigNumber.
For more detailed information, please refer to the Javadoc.
2.3. Example
Let’s simulate a computationally expensive method named generateBigNumber:
public class CostlySupplier {
private static BigInteger generateBigNumber() {
try {
TimeUnit.SECONDS.sleep(2);
} catch (InterruptedException e) {}
return new BigInteger("12345");
}
}
Our example method will take 2 seconds to execute, and then return a BigInteger result. We could memoize it using either the memoize or memoizeWithExpiration APIs*.*
For simplicity we’ll omit the eviction policy:
@Test
public void givenMemoizedSupplier_whenGet_thenSubsequentGetsAreFast() {
Supplier<BigInteger> memoizedSupplier;
memoizedSupplier = Suppliers.memoize(CostlySupplier::generateBigNumber);
BigInteger expectedValue = new BigInteger("12345");
assertSupplierGetExecutionResultAndDuration(
memoizedSupplier, expectedValue, 2000D);
assertSupplierGetExecutionResultAndDuration(
memoizedSupplier, expectedValue, 0D);
assertSupplierGetExecutionResultAndDuration(
memoizedSupplier, expectedValue, 0D);
}
private <T> void assertSupplierGetExecutionResultAndDuration(
Supplier<T> supplier, T expectedValue, double expectedDurationInMs) {
Instant start = Instant.now();
T value = supplier.get();
Long durationInMs = Duration.between(start, Instant.now()).toMillis();
double marginOfErrorInMs = 100D;
assertThat(value, is(equalTo(expectedValue)));
assertThat(
durationInMs.doubleValue(),
is(closeTo(expectedDurationInMs, marginOfErrorInMs)));
}
The first get method call takes two seconds, as simulated in the generateBigNumber method; however, subsequent calls to get() will execute significantly faster, since the generateBigNumber result has been memoized.
3. Function Memoization
To memoize a method that takes a single argument we *build a LoadingCache map using CacheLoader‘s from method to provision the builder concerning our method as a Guava Function.*
LoadingCache is a concurrent map, with values automatically loaded by CacheLoader. CacheLoader populates the map by computing the Function specified in the from method, and putting the returned value into the LoadingCache. For more detailed information, please refer to the Javadoc.
LoadingCache‘s key is the Function‘s argument/input, while the map’s value is the Function‘s returned value:
LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.build(CacheLoader.from(FibonacciSequence::getFibonacciNumber));
Since LoadingCache is a concurrent map, it doesn’t allow null keys or values. Therefore, we need to ensure that the Function doesn’t support null as an argument or return null values.
3.1. Function Memoization With Eviction Policies
We can apply different Guava Cache’s eviction policy when we memoize a Function as mentioned in Section 3 of the Guava Cache article.
For instance, we can evict the entries which have been idle for 2 seconds:
LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.expireAfterAccess(2, TimeUnit.SECONDS)
.build(CacheLoader.from(Fibonacci::getFibonacciNumber));
Next, let’s take a look at two use cases of Function memoization: Fibonacci sequence and factorial.
3.2. Fibonacci Sequence Example
We can recursively compute a Fibonacci number from a given number n:
public static BigInteger getFibonacciNumber(int n) {
if (n == 0) {
return BigInteger.ZERO;
} else if (n == 1) {
return BigInteger.ONE;
} else {
return getFibonacciNumber(n - 1).add(getFibonacciNumber(n - 2));
}
}
Without memoization, when the input value is relatively high, the execution of the function will be slow.
To improve the efficiency and performance, we can memoize getFibonacciNumber using CacheLoader and CacheBuilder, specifying the eviction policy if necessary.
In the following example, we remove the oldest entry once the memo size has reached 100 entries:
public class FibonacciSequence {
private static LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.maximumSize(100)
.build(CacheLoader.from(FibonacciSequence::getFibonacciNumber));
public static BigInteger getFibonacciNumber(int n) {
if (n == 0) {
return BigInteger.ZERO;
} else if (n == 1) {
return BigInteger.ONE;
} else {
return memo.getUnchecked(n - 1).add(memo.getUnchecked(n - 2));
}
}
}
Here, we use getUnchecked method which returns the value if exists without throwing a checked exception.
In this case, we don’t need to explicitly handle the exception when specifying getFibonacciNumber method reference in the CacheLoader‘s from method call.
For more detailed information, please refer to the Javadoc.
3.3. Factorial Example
Next, we have another recursive method that computes the factorial of a given input value, n:
public static BigInteger getFactorial(int n) {
if (n == 0) {
return BigInteger.ONE;
} else {
return BigInteger.valueOf(n).multiply(getFactorial(n - 1));
}
}
We can enhance the efficiency of this implementation by applying memoization:
public class Factorial {
private static LoadingCache<Integer, BigInteger> memo = CacheBuilder.newBuilder()
.build(CacheLoader.from(Factorial::getFactorial));
public static BigInteger getFactorial(int n) {
if (n == 0) {
return BigInteger.ONE;
} else {
return BigInteger.valueOf(n).multiply(memo.getUnchecked(n - 1));
}
}
}
4. Conclusion
In this article, we’ve seen how Guava provides APIs to perform memoization of Supplier and Function methods. We have also shown how to specify the eviction policy of the stored function result in memory.
As always, the source code can be found over on GitHub.