Рекурсивный вызов ConcurrentHashMap.computeIfAbsent() никогда не завершается. Ошибка или "функция"?

Некоторое время назад Я вел блог о функциональном способе вычисления чисел фибоначчи на Java 8, с кешем ConcurrentHashMap и новым, полезным 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);
        });
    }
}

Я выбрал ConcurrentHashMap, потому что думал о том, чтобы сделать этот пример еще более сложным, введя parallelism (которого я не сделал в конце).

Теперь позвольте увеличить число от 8 до 25 и наблюдать, что происходит:

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

Программа никогда не останавливается. Внутри метода существует цикл, который запускается вечно:

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

Я использую:

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)

Маттиас, читатель этого блога, также подтвердил эту проблему (он действительно ее нашел).

Это странно. Я бы ожидал любой из следующих двух:

Работает
Он выбрасывает ConcurrentModificationException

Но просто никогда не останавливаешься? Это кажется опасным. Это ошибка? Или я не понял какой-то контракт?

Ответ 1

Это исправлено в JDK-8062841.

В предложении 2011 я определил эту проблему во время обзора кода. JavaDoc был обновлен и добавлено временное исправление. Это было устранено в дополнительной перезаписи из-за проблем с производительностью.

В обсуждении 2014 мы рассмотрели способы более эффективного обнаружения и сбоя. Обратите внимание, что некоторые из обсуждений были отправлены в автономном режиме в частную электронную почту для рассмотрения изменений на низком уровне. Хотя не каждый случай может быть покрыт, обычные случаи не будут жить. Эти исправления находятся в репозитории Doug, но не попали в выпуск JDK.

Ответ 2

Это, конечно, "особенность". ConcurrentHashMap.computeIfAbsent() Javadoc читает:

Если указанный ключ еще не связан со значением, он пытается вычислить его значение с использованием заданной функции отображения и вводит его в эту карту, если не равен нулю. Весь вызов метода выполняется атомарно, поэтому функция применяется не более одного раза за ключ. Некоторые попытки выполнить операции обновления на этой карте другими потоками могут быть заблокированы, пока выполняется вычисление, поэтому вычисление должно быть коротким и простым, а не должно пытаться обновлять любые другие сопоставления этой карты.. p >

"Не должна" формулировка - это четкий договор, который мой алгоритм нарушил, хотя и не по тем же причинам concurrency.

Что еще интересно, так это отсутствие ConcurrentModificationException. Вместо этого программа просто никогда не останавливается, что по-прежнему является довольно опасной ошибкой (т.е. бесконечными циклами или: все, что может пойти не так, делает).

Примечание:

HashMap.computeIfAbsent() или Map.computeIfAbsent() Javadoc не запрещайте такие рекурсивные вычисления, что, конечно, смешно, так как тип кеша Map<Integer, Integer>, а не ConcurrentHashMap<Integer, Integer>. Очень опасно, что подтипы резко переопределяют контракты типа супер (Set vs. SortedSet - приветствие). Таким образом, запрещается также в супер-типах выполнять такую рекурсию.

Ответ 3

Это очень похоже на ошибку. Потому что, если вы создадите свой кеш объемом 32, ваша программа будет работать до 49. И интересно, что параметр sizeCtl = 32 + (32 → > 1) + 1) = 49! Может быть, причина в изменении размера?