Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8074374

Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or ?fea

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P4
    • Resolution: Duplicate
    • Affects Version/s: 8-pool, 9
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:

      Description

      FULL PRODUCT 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)

      ADDITIONAL OS VERSION INFORMATION :
      Microsoft Windows [Version 6.3.9600]

      A DESCRIPTION OF THE PROBLEM :
      This is copied from here: http://stackoverflow.com/q/28840047/521799

      Some time ago, I've blogged about a Java 8 functional way of calculating fibonacci numbers recursively [1], with a ConcurrentHashMap cache and the new, useful computeIfAbsent() method:

      import java.util.Map;
      import java.util.concurrent.ConcurrentHashMap;

      public class Test {
          static Map<Integer, Integer> cache = new ConcurrentHashMap<>();

          public static void main(String[] args) {
              System.out.println(
                  "f(" + 8 + ") = " + fibonacci(8));
          }

          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);
              });
          }
      }

      I chose ConcurrentHashMap because I was thinking of making this example even more sophisticated by introducing parallelism (which I didn't in the end).

      Now, let's increase the number from 8 to 25 and observe what happens:

              System.out.println(
                  "f(" + 25 + ") = " + fibonacci(25));

      The program never halts. Inside the method, there's a loop that just runs forever:

      for (Node<K,V>[] tab = table;;) {
          // ...
      }


      Matthias, a reader of that blog post also confirmed the issue (he actually found it). [2]

      This is weird. I would have expected any of the following two:

      - It works
      - It throws a ConcurrentModificationException

      But just never halting? That seems dangerous. Is it a bug? Or did I misunderstand some contract?

      ------

      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.

      What's still interesting is that there is no ConcurrentModificationException. Instead, the program just never halts - which still is a rather dangerous bug in my opinion.

      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<>();

      Now, everything works fine.

      Note:

      The HashMap.computeIfAbsent() (or Map.computeIfAbsent() Javadoc don't forbid such recursive computation, which is of course crazy 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.


      [1]: http://blog.jooq.org/2014/02/28/java-8-friday-goodies-easy-as-pie-local-caching
      [2]: http://blog.jooq.org/2014/02/28/java-8-friday-goodies-easy-as-pie-local-caching/#comment-121821

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      See description

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      The program should halt
      ACTUAL -
      The program doesn't halt

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      See description
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      Use a HashMap instead of a ConcurrentHashMap

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: