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!

Avoid Recursion in ConcurrentHashMap.computeIfAbsent()

Sometimes we give terrible advice. Like in that article about how to use Java 8 for a cached, functional approach to calculating fibonacci numbers. As Matthias, one of our readers, noticed in the comments, the proposed algorithm may just never halt. Consider the following program:

public class Test {
    static Map<Integer, Integer> cache 
        = new ConcurrentHashMap<>();
 
    public static void main(String[] args) {
        System.out.println(
            "f(" + 25 + ") = " + fibonacci(25));
    }
 
    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);
        });
    }
}

It will run indefinitely at least on the following Java version:

C:\Users\Lukas>java -version
java version "1.8.0_40-ea"
Java(TM) SE Runtime Environment (build 1.8.0_40-ea-b23)
Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)

This is of course a “feature”. The ConcurrentHashMap.computeIfAbsent() Javadoc reads:

If the specified key is not already associated with a value, attempts to compute its value using the given mapping function and enters it into this map unless null. The entire method invocation is performed atomically, so the function is applied at most once per key. Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

The “must not” wording is a clear contract, which my algorithm violated, although not for the same concurrency reasons.

The Javadoc also reads:

Throws:

IllegalStateException – if the computation detectably attempts a recursive update to this map that would otherwise never complete

But that exception isn’t thrown. Neither is there any ConcurrentModificationException. Instead, the program just never halts.

The simplest use-site solution for this concrete problem would be to not use a ConcurrentHashMap, but just a HashMap instead:

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

Subtypes overriding super type contracts

The HashMap.computeIfAbsent() or Map.computeIfAbsent() Javadoc don’t forbid such recursive computation, which is of course ridiculous as the type of the cache is Map<Integer, Integer>, not ConcurrentHashMap<Integer, Integer>. It is very dangerous for subtypes to drastically re-define super type contracts (Set vs. SortedSet is greeting). It should thus be forbidden also in super types, to perform such recursion.

Further reference

While the contract issues are a matter of perception, the halting problem clearly is a bug. I’ve also documented this issue on Stack Overflow where Ben Manes gave an interesting answer leading to a previous (unresolved as of early 2015) bug report:

https://bugs.openjdk.java.net/browse/JDK-8062841

My own report (probably a duplicate of the above) was also accepted quickly, as:

https://bugs.openjdk.java.net/browse/JDK-8074374

While this is being looked at by Oracle, remember to:

Never recurse inside a ConcurrentHashMap.computeIfAbsent() method. And if you’re implementing collections and think it’s a good idea to write a possibly infinite loop, think again, and read our article:

Infinite Loops. Or: Anything that Can Possibly Go Wrong, Does)

Murphy is always right.

Infinite Loops. Or: Anything that Can Possibly Go Wrong, Does.

A wise man once said:

Anything that can possibly go wrong, does

Murphy

Some programmers are wise men, thus a wise programmer once said:

A good programmer is someone who looks both ways before crossing a one-way street.

Doug Linder

In a perfect world, things work as expected and you may think that it is a good idea to keep consuming things until the end. So the following pattern is found all over in every code base:

Java

for (;;) {
    // something
}

C

while (1) {
    // something
}

BASIC

10 something
20 GOTO 10

Want to see proof? Search github for while(true) and check out the number of matches:

https://github.com/search?q=while+true&type=Code

Never use possibly infinite loops

There is a very interesting discussion in computer science around the topic of the “Halting Problem”. The essence of the halting problem as proved by Alan Turing a long time ago is the fact that it is really undecidable. While humans can quickly assess that the following program will never stop:

for (;;) continue;

… and that the following program will always stop:

for (;;) break;

… computers cannot decide on such things, and even very experienced humans might not immediately be able to do so when looking at a more complex algorithm.

Learning by doing

In jOOQ, we have recently learned about the halting problem the hard way: By doing.

Before fixing issue #3696, we worked around a bug (or flaw) in SQL Server’s JDBC driver. The bug resulted in SQLException chains not being reported correctly, e.g. when the following trigger raises several errors:

CREATE TRIGGER Employee_Upd_2  ON  EMPLOYEE FOR UPDATE
AS 
BEGIN

    Raiserror('Employee_Upd_2 Trigger called...',16,-1)
    Raiserror('Employee_Upd_2 Trigger called...1',16,-1)
    Raiserror('Employee_Upd_2 Trigger called...2',16,-1)
    Raiserror('Employee_Upd_2 Trigger called...3',16,-1)
    Raiserror('Employee_Upd_2 Trigger called...4',16,-1)
    Raiserror('Employee_Upd_2 Trigger called...5',16,-1)

END
GO

So, we explicitly consumed those SQLExceptions, such that jOOQ users got the same behaviour for all databases:

consumeLoop: for (;;)
    try {
        if (!stmt.getMoreResults() && 
             stmt.getUpdateCount() == -1)
            break consumeLoop;
    }
    catch (SQLException e) {
        previous.setNextException(e);
        previous = e;
    }

This has worked for most of our customers, as the chain of exceptions thus reported is probably finite, and also probably rather small. Even the trigger example above is not a real-world one, so the number of actual errors reported might be between 1-5.

Did I just say … “probably” ?

As our initial wise men said: The number might be between 1-5. But it might just as well be 1000. Or 1000000. Or worse, infinite. As in the case of issue #3696, when a customer used jOOQ with SQL Azure. So, in a perfect world, there cannot be an infinite number of SQLException reported, but this isn’t a perfect world and SQL Azure also had a bug (probably still does), which reported the same error again and again, eventually leading to an OutOfMemoryError, as jOOQ created a huge SQLException chain, which is probably better than looping infinitely. At least the exception was easy to detect and work around. If the loop ran infinitely, the server might have been completely blocked for all users of our customer.

The fix is now essentially this one:

consumeLoop: for (int i = 0; i < 256; i++)
    try {
        if (!stmt.getMoreResults() && 
             stmt.getUpdateCount() == -1)
            break consumeLoop;
    }
    catch (SQLException e) {
        previous.setNextException(e);
        previous = e;
    }

True to the popular saying:

640 KB ought to be enough for anybody

The only exception

So as we’ve seen before, this embarassing example shows that anything that can possibly go wrong, does. In the context of possibly ininite loops, beware that this kind of bug will take entire servers down.

The Jet Propulsion Laboratory at the California Institute of Technology has made this an essential rule for their coding standards:

Rule 3 (loop bounds)

All loops shall have a statically determinable upper-bound on the maximum number of loop iterations. It shall be possible for a static compliance checking tool to affirm the existence of the bound. An exception is allowed for the use of a single non-terminating loop per task or thread where requests are received and processed. Such a server loop shall be annotated with the C comment: /* @non-terminating@ */.

So, apart from very few exceptions, you should never expose your code to the risk of infinite loops by not providing upper bounds to loop iterations (the same can be said about recursion, btw.)

Conclusion

Go over your code base today and look for any possible while (true), for (;;), do {} while (true); and other statements. Review those statements closely and see if they can halt – e.g. using break, or throw, or return, or continue (an outer loop).

Chances are, that you or someone before you who wrote that code was as naive as we were, believing that…

… oh come on, this will never happen

Because, you know what happens when you think that nothing will happen.

MySQL Bad Idea #573

This is MySQL’s Bad Idea #573 (after #384, which I’ve blogged about before) I’ve just had a terrible experience with a bug report from the jOOQ User Group, related to escaping of backslashes in string literals in MySQL. First, I thought to myself, whatever. SQL doesn’t escape backslashes. The only escape character within a string literal according to the early SQL standards is the quote as in quote quote. Citing from SQL-1992 (slightly simplified):

<character string literal> ::=
    <quote> [ <character representation>... ] <quote>

<character representation> ::=
    <nonquote character>
  | <quote symbol><nonquote character> ::= !! See the Syntax Rules.
<quote symbol> ::= <quote><quote>

Alright? Crystal clear. There’s no escaping other than <quote><quote>

The only time when you will need to be able to escape something is with the LIKE predicate, in case you want to escape % and _ symbols. You can then use the ESCAPE clause:

<like predicate> ::=
    <match value> [ NOT ] LIKE <pattern>
    [ ESCAPE <escape character> ]

I have now learned, that MySQL (and of course MariaDB) unlike any other database also support quoting with backslashes, similar to Java and other languages. That’s not a problem per se, although from a cross-vendor compatibility perspective, it’s quite nasty. But then, I’ve discovered there is a flag called NO_BACKSLASH_ESCAPES:

This just reminds me of PHP’s horrible magic quotes. In fact, combine arbitrary configurations of PHP and MySQL on your server and good luck to you of ever getting string literals right. Sigh.