java - safe - La llamada recursiva ConcurrentHashMap.computeIfAbsent() nunca finaliza. ¿Error o "característica"?

thread safe hashmap

Question

Hace algún tiempo, escribí en un blog sobre una forma funcional Java 8 de calcular números de Fibonacci de forma recursiva , con un caché ConcurrentHashMap y el nuevo y útil método computeIfAbsent() :

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

Elegí ConcurrentHashMap porque estaba pensando en hacer este ejemplo aún más sofisticado mediante la introducción de paralelismo (que al final no lo hice).

Ahora, aumentemos el número de 8 a 25 y observemos lo que sucede:

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

El programa nunca se detiene. Dentro del método, hay un bucle que se ejecuta para siempre:

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

Estoy usando:

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)

Matthias, un lector de esa publicación de blog también confirmó el problema (en realidad lo encontró) .

Esto es raro Hubiera esperado cualquiera de los siguientes dos:

• Funciona
• Lanza una ConcurrentModificationException

¿Pero nunca se detiene? Eso parece peligroso. ¿Es un error? ¿O entendí mal algún contrato?

Answer 1

Esto es muy similar al error. Porque, si crea su caché con capacidad 32, su programa funcionará hasta 49. ¡Y es interesante que ese parámetro sizeCtl = 32 + (32 >>> 1) + 1) = 49! Puede ser la razón en el cambio de tamaño?

Answer 2

Esto es, por supuesto, una "característica" . El Javadoc ConcurrentHashMap.computeIfAbsent() lee:

Si la clave especificada aún no está asociada con un valor, intenta calcular su valor utilizando la función de mapeo dada y la ingresa en este mapa a menos que sea nulo. La invocación del método completo se realiza atómicamente, por lo que la función se aplica como máximo una vez por tecla. Algunos intentos de actualización en este mapa por otros subprocesos pueden bloquearse mientras el cálculo está en progreso, por lo que el cálculo debe ser breve y simple, y no debe intentar actualizar ninguna otra asignación de este mapa .

La frase "no debe" es un contrato claro, que violó mi algoritmo, aunque no por las mismas razones de concurrencia.

Lo que sigue siendo interesante es que no hay ConcurrentModificationException . En cambio, el programa simplemente nunca se detiene, lo que sigue siendo un error bastante peligroso en mi opinión (es decir, bucles infinitos o: cualquier cosa que pueda salir mal, lo hace ).

Nota:

El HashMap.computeIfAbsent() o Map.computeIfAbsent() no prohíbe dicho cálculo recursivo, que por supuesto es ridículo ya que el tipo de caché es Map<Integer, Integer> , no ConcurrentHashMap<Integer, Integer> . Es muy peligroso para los subtipos redefinir drásticamente los contratos de SortedSet ( Set vs. SortedSet es un saludo). Por lo tanto, debería estar prohibido también en súper tipos, realizar tal recursión.

Answer 3

Esto se soluciona en JDK-8062841 .

En la propuesta de 2011 , identifiqué este problema durante la revisión del código. El JavaDoc se actualizó y se agregó una solución temporal. Se eliminó en una nueva reescritura debido a problemas de rendimiento.

En la discusión de 2014 , exploramos formas de detectar y fallar mejor. Tenga en cuenta que parte de la discusión se tomó fuera de línea a un correo electrónico privado por considerar los cambios de bajo nivel. Si bien no todos los casos pueden ser cubiertos, los casos comunes no tendrán bloqueo. Estas fixes están en el repositorio de Doug pero no se han convertido en una versión de JDK.