Skip to content
Advertisement

Is JVM or JIT able to reduce duplicate method calls?

I have a function that checks if a map has some value for key (map.get(key) != null) and then returns the value, or else create new value.
I’m wondering is there any JVM or JIT magic that doesn’t have to do 2 map lookups when the value exists for the given key?

Value someValue = map.get(key) != null ? map.get(key) : new Value();

According to my benchmark, it seems no optimisation can be done as it’s visibly slower than if we have a local variable to hold the value:

@Benchmark
public String duplicateCall() {
    return map.get(1) != null ? map.get(1) : DEFAULT;
}

@Benchmark
public String nonDuplicateCall() {
    final String s = map.get(1);
    return s != null ? s : DEFAULT;
}

Results:

Benchmark                                  Mode  Cnt       Score       Error   Units
duplicateCall     thrpt    5  634001.515 ± 69181.631  ops/ms
nonDuplicateCall  thrpt    5  869980.580 ± 66572.021  ops/ms

Advertisement

Answer

Eliminating duplicate method calls can only work if the optimizer can prove that the two operations are idempotent, which requires looking into the method’s actual implementation code.

Your assumption that the two occurrences of map.get(1) will do the same, relies on several premises, the JVM can’t take for granted.

  • You’re calling the method on the same object instance. Even in this simple code with adjacent calls, the optimizer can’t assume this, without knowing what get actually does. If get changes the map reference, this assumption would be void.

  • You’re passing the same key. Your code suggests that we’re talking about a Map<Integer, String>, so the expression is subject to auto-boxing. You’re effectively passing Integer.valueOf(1) to get and another occurrence of Integer.valueOf(1) for the other get call.
    The specific contract of auto-boxing/Integer.valueOf(int) allows substituting one for the other, regardless of how the implementation looks like, the question is whether the optimizer will know and exploit this.

  • The method is free of side effects. While it’s reasonable to assume that a Map’s get implementation does not modify the map, it might contain logging or benchmark statements which are ineffective by default but could be activated, depending on some runtime state. If it has such statements, proving their ineffectiveness requires predicting that runtime state.

Since eliminating the redundancy can only work when knowing the implementation code, it only works after inlining the code when the prerequisites for inlining are met (e.g. the invocation does always end up at the same implementation). Then, optimizations like common subexpression elimination will be applied.

The effectivity of this optimization depends on the actual implementation code. For empty maps like Map.of() or Collections.emptyMap() and for singleton maps like Map.of(1, "foo") or Collections.singletonMap(1, "foo") this might work well. But for maps like TreeMap or HashMap¹, the actual implementation is way too complex to assume that redundant evaluations can be eliminated completely. It’s important to keep in mind that this would also require inlining the hashCode and equals (or compareTo) implementations of the key, to prove their idempotence. Not an issue for Integer keys, but could be for other key types.

To illustrate this, we’re talking about an implementation like this for HashMap:

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

The optimizer would have to inline this code twice (chances are high that it won’t due to code size thresholds) and then prove that the two occurrences do the same and are free of side effects…


As already mentioned in the comments, you can simply use map.getOrDefault(1, DEFAULT) if you want concise code and avoid duplicate lookup operations.


¹ and concurrent or synchronized maps are out of the game anyway, unless the optimizer can prove that they have never been seen by another thread.

User contributions licensed under: CC BY-SA
1 People found this is helpful
Advertisement