A Common Mistake Developers Make When Caching Nullable Values

Caching is hard in various ways. Whenever you’re caching things, you have to at least think of:

  • Memory consumption
  • Invalidation

In this article, I want to show a flaw that often sneaks into custom cache implementations, making them inefficient for some execution paths. I’ve encountered this flaw in Eclipse, recently.

What did Eclipse do wrong?

I periodically profile Eclipse using Java Mission Control (JMC) when I discover a performance issue in the compiler (and I’ve discovered a few).

Just recently, I’ve found a new regression that must have been introduced with the new Java 9 module support in Eclipse 4.7.1a:

Luckily, the issue has already been fixed for 4.7.2 (https://bugs.eclipse.org/bugs/show_bug.cgi?id=526209). What happened?

In that profiling session, I’ve found an awful lot of accesses to java.util.zip.ZipFile whenever I used the “content assist” feature (auto completion). This was the top stack trace in the profiler:

int java.util.zip.ZipFile$Source.hashN(byte[], int, int)
void java.util.zip.ZipFile$Source.initCEN(int)
void java.util.zip.ZipFile$Source.(ZipFile$Source$Key, boolean)
ZipFile$Source java.util.zip.ZipFile$Source.get(File, boolean)
void java.util.zip.ZipFile.(File, int, Charset)
void java.util.zip.ZipFile.(File, int)
void java.util.zip.ZipFile.(File)
ZipFile org.eclipse.jdt.internal.core.JavaModelManager.getZipFile(IPath, boolean)
ZipFile org.eclipse.jdt.internal.core.JavaModelManager.getZipFile(IPath)
ZipFile org.eclipse.jdt.internal.core.JarPackageFragmentRoot.getJar()
byte[] org.eclipse.jdt.internal.core.AbstractClassFile.getClassFileContent(JarPackageFragmentRoot, String)
IBinaryModule org.eclipse.jdt.internal.core.ModularClassFile.getJarBinaryModuleInfo()
IBinaryModule org.eclipse.jdt.internal.core.ModularClassFile.getBinaryModuleInfo()
boolean org.eclipse.jdt.internal.core.ModularClassFile.buildStructure(...)
void org.eclipse.jdt.internal.core.Openable.generateInfos(Object, HashMap, IProgressMonitor)
Object org.eclipse.jdt.internal.core.JavaElement.openWhenClosed(Object, boolean, IProgressMonitor)
Object org.eclipse.jdt.internal.core.JavaElement.getElementInfo(IProgressMonitor)
Object org.eclipse.jdt.internal.core.JavaElement.getElementInfo()
boolean org.eclipse.jdt.internal.core.JavaElement.exists()
boolean org.eclipse.jdt.internal.core.Openable.exists()
IModuleDescription org.eclipse.jdt.internal.core.PackageFragmentRoot.getModuleDescription()
IModuleDescription org.eclipse.jdt.internal.core.NameLookup.getModuleDescription(IPackageFragmentRoot, Map, Function)
...

In fact, the profiling session doesn’t show the exact number of accesses, but the number of stack trace samples that contained the specific method(s) which corresponds to the time spent inside of a method, not the number of calls (which is less relevant). Clearly, accessing zip files shouldn’t be the thing that Eclipse should be doing most of the time, when auto completing my code. So, why did it do it anyway?

It turns out, the problem was in the method getModuleDescription(), which can be summarised as follows:

static IModuleDescription getModuleDescription(
    IPackageFragmentRoot root, 
    Map<IPackageFragmentRoot,IModuleDescription> cache, 
    Function<IPackageFragmentRoot,IClasspathEntry> rootToEntry
) {
    IModuleDescription module = cache.get(root);
    if (module != null)
        return module;

    ...
    // Expensive call to open a Zip File in these calls:
    if (root.getKind() == IPackageFragmentRoot.K_SOURCE)
        module = root.getJavaProject().getModuleDescription();
    else
        module = root.getModuleDescription();

    if (module == null) {
        ...
    }

    if (module != null)
        cache.put(root, module);
    return module;
}

The ZipFile access is hidden inside the getModuleDescription() call. A debugger revealed that the JDK’s rt.jar file was opened quite a few times to look for a module-info.class file. Can you spot the mistake in the code?

The method gets an external cache that may already contain the method’s result. But the method may also return null in case there is no module description. Which there isn’t. jOOQ has not yet been modularised, and most libraries on which jOOQ depends haven’t been modularised either, nor has the JDK been modularised using which jOOQ is currently built (JDK 8). So, this method always returns null for non-modular stuff.

But if it returns null, it won’t put anything in the cache:

    if (module != null)
        cache.put(root, module);
    return module;
}

… which means the next time it is called, there’s a cache miss:

    IModuleDescription module = cache.get(root);
    if (module != null)
        return module;

… and the expensive logic involving the ZipFile call is invoked again. In other words, it is invoked all the time (for us).

Caching optional values

This is an important thing to always remember, and it is not easy to remember. Why? Because the developer who implemented this cache implemented it for the “happy path” (from the perspective of someone working with modules). They probably tried their code with a modular project, in case of which the cache worked perfectly. But they didn’t check if the code still works for everyone else. And in fact, it does work. The logic isn’t wrong. It’s just not optimal.

The solution to these things is simple. If the value null encodes a cache miss, we need another “PSEUDO_NULL” to encode the actual null value, or in this case something like NO_MODULE. So, the method can be rewritten as:

static IModuleDescription getModuleDescription(
    IPackageFragmentRoot root, 
    Map<IPackageFragmentRoot,IModuleDescription> cache, 
    Function<IPackageFragmentRoot,IClasspathEntry> rootToEntry
) {
    IModuleDescription module = cache.get(root);

    // Decode encoded NO_MODULE value:
    if (module == NO_MODULE)
        return null;
    if (module != null)
        return module;

    module = ...

    if (module != null)
        cache.put(root, module);

    // Encode null value:
    else
        cache.put(root, NO_MODULE);

    return module;
}

… where this NO_MODULE can be a simple java.lang.Object if you don’t care about generics, or a dummy IModuleDescription in our case:

static final IModuleDescription NO_MODULE = 
  new IModuleDescription() { ... };

Since it will be a singleton instance, we can use identity comparisons in our method.

Conclusion

When caching method results, always check if null is a valid result for the method. If it is, and if your cache is a simple Map, then you have to encode the null value with some sort of NO_MODULE value for the cache to work properly. Otherwise, you won’t be able to distinguish Map.get(key) == null for the cases:

  • Cache miss and Map returns null
  • Cache hit and the value is null

Update after some useful reddit / DZone comments

As /u/RayFowler pointed out on this article’s reddit discussion, the concept illustrated here is called “negative caching”

Something that is often forgotten when performing negative caching is the fact that exceptions are also a result, as pointed out by /u/zombifai in the same reddit discussion. The fix in Eclipse correctly took this into account as can be seen here: https://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=addfd789e17dbb99af0304912ef45e4ae72c0605

While a Map.containsKey() based solution would work in a similar way and would have the advantage of not needing a “dummy” / sentinel value, it is not a good approach in situations where performance really matters – remember that in this case, we’re talking about an Eclipse compiler optimisation where we really don’t want two Map lookups where one would suffice. This is a generally interesting thought for caches, which are introduced after all to improve performance!

Java 8 Friday Goodies: Easy-as-Pie Local Caching

At Data Geekery, we love Java. And as we’re really into jOOQ’s fluent API and query DSL, we’re absolutely thrilled about what Java 8 will bring to our ecosystem. We have blogged a couple of times about some nice Java 8 goodies, and now we feel it’s time to start a new blog series, the…

Java 8 Friday

Every Friday, we’re showing you a couple of nice new tutorial-style Java 8 features, which take advantage of lambda expressions, extension methods, and other great stuff. You’ll find the source code on GitHub. tweet this

Java 8 Goodie: Easy-as-Pie Local Caching

Now get ready for one of the most awesome revelations in this series so far. We’ll show you an easy-as-pie way to implement a local cache using the good old HashMap and lambda expressions. Because, Map now has a new way of a atomically calculating a new value in case a key is absent. Perfect for caches. Let’s delve into code:

public static void main(String[] args) {
    for (int i = 0; i < 10; i++)
        System.out.println(
            "f(" + i + ") = " + fibonacci(i));
}

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    System.out.println("Calculating f(" + i + ")");
    return fibonacci(i - 2) + fibonacci(i - 1);
}

Yes. That’s the naive way of doing things. Even for small numbers like fibonacci(5), the above algorithm will print out a huge amount of lines, as we’re repeating the same calculations exponentially:

Calculating f(6)
Calculating f(4)
Calculating f(2)
Calculating f(3)
Calculating f(2)
Calculating f(5)
Calculating f(3)
Calculating f(2)
Calculating f(4)
Calculating f(2)
Calculating f(3)
Calculating f(2)
f(6) = 8

What we want to do is build a cache of previously calculated fibonacci numbers. The most straightforward technique is to memoize all values in a cache. Here’s how we build a cache:

static Map<Integer, Integer> cache = new HashMap<>();

Important side note: A previous version of the blog post used a ConcurrentHashMap here. DO NOT USE ConcurrentHashMaps when you recursively calculate values using computeIfAbsent(). Details here:

http://stackoverflow.com/q/28840047/521799

Done! As mentioned before, we’re using the newly added Map.computeIfAbsent() method to calculate a new value from a source function only if we don’t already have a value for a given key. Caching! And since this method is guaranteed to execute atomically, and since we’re using a ConcurrentHashMap, this cache is even thread-safe without resorting to manually applying synchronized anywhere. And it can be reused for stuff other than calculating fibonacci numbers. But let’s first apply this cache to our fibonacci() function.

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    return cache.computeIfAbsent(i, (key) ->
                 fibonacci(i - 2)
               + fibonacci(i - 1));
}

That’s it. It can’t get any simpler than this! Want proof? We’ll log a message on the console every time we actually evaluate a new value:

static int fibonacci(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    return cache.computeIfAbsent(i, (key) -> {
        System.out.println(
            "Slow calculation of " + key);

        return fibonacci(i - 2) + fibonacci(i - 1);
    });
}

The above program will print

f(0) = 0
f(1) = 1
Slow calculation of 2
f(2) = 1
Slow calculation of 3
f(3) = 2
Slow calculation of 4
f(4) = 3
Slow calculation of 5
f(5) = 5
Slow calculation of 6
f(6) = 8
Slow calculation of 7
f(7) = 13
Slow calculation of 8
f(8) = 21
Slow calculation of 9
f(9) = 34

How would we have done it in Java 7?

Good question. With lots of code. We’d probably write something like this using double-checked locking:

static int fibonacciJava7(int i) {
    if (i == 0)
        return i;

    if (i == 1)
        return 1;

    Integer result = cache.get(i);
    if (result == null) {
        synchronized (cache) {
            result = cache.get(i);

            if (result == null) {
                System.out.println(
                    "Slow calculation of " + i);

                result = fibonacci(i - 2) 
                       + fibonacci(i - 1);
                cache.put(i, result);
            }
        }
    }

    return result;
}

Convinced?

Note, that your actual solution would probably make use of Guava Caches.

Conclusion

Lambdas are only one part of Java 8. An important part, but let’s not forget all the new features that were added to the libraries and that can be leveraged with lambdas now!

This is really exciting and…

We can greatly improve our code bases without resorting to new libraries. All of the above can be run with the JDK’s libraries only. tweet this

Next week in this blog series, we’re going to look at how Java 8 will improve on the existing and new concurrency APIs, so stay tuned!

More on Java 8

In the mean time, have a look at Eugen Paraschiv’s awesome Java 8 resources page

Oracle scalar subquery caching

The importance of being able to fully control executed SQL (using jOOQ, or plain JDBC) on large-scale systems becomes obvious every time you need to fine-tune your SQL queries for a specific RDBMS. In this case, we’re looking at Oracle and its miraculous scalar subquery caching mechanisms:

Usually, the context switch from SQL to PL/SQL and back is quite expensive for an average Oracle query, so we should normally omit putting stored functions as filtering, grouping, sorting criteria, even if they’re DETERMINISTIC. When we have large result sets, however, even functions in the query projection may turn out to be an execution plan nightmare. I recently raised the question on Stack Overflow, as I’m curious if there is any caching mechanism, that I could take advantage of for a concrete use-case:

http://stackoverflow.com/questions/7270467/is-there-a-pl-sql-pragma-similar-to-deterministic-but-for-the-scope-of-one-singl

And most interestingly, there are several. The accepted answer points to this very relevant article on Ask Tom’s Q/A:

http://www.oracle.com/technetwork/issue-archive/2011/11-sep/o51asktom-453438.html

Apparently, in scalar subqueries, function results may be cached! While this can be very useful for performance, it can also be very dangerous for consistency – as with any caching mechanism, but this one is highly implicit! So this will be cached:

-- my_function is NOT deterministic but it is cached!
select t.x, t.y, (select my_function(t.x) from dual)
from t

-- logically equivalent to this, uncached
select t.x, t.y, my_function(t.x) from t

Knowing this, I think I have to review quite a bit of SQL…