Статьи

Избегайте рекурсии в ConcurrentHashMap.computeIfAbsent ()

Январь 20, 2018

Иногда мы даем ужасные советы. Как в той статье о том, как использовать Java 8 для кэшированного, функционального подхода к вычислению чисел Фибоначчи . Как заметил в комментариях один из наших читателей Матиас, предложенный алгоритм может никогда не остановиться. Рассмотрим следующую программу:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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);
        });
    }
}

Это будет работать бесконечно, по крайней мере, на следующей версии Java:

1
2
3
4
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)

Это конечно «фича» . Javadoc ConcurrentHashMap.computeIfAbsent() гласит:

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

Формулировка «не должен» — это четкий контракт, который нарушил мой алгоритм, хотя и не по тем же причинам параллелизма.

Javadoc также гласит:

Броски:

IllegalStateException — если вычисление обнаружимо пытается рекурсивное обновление этой карты, которое иначе никогда бы не завершило

Но это исключение не выбрасывается. Также нет ConcurrentModificationException. Вместо этого программа просто никогда не останавливается.

Самое простое решение для этой конкретной проблемы — не использовать ConcurrentHashMap, а вместо этого просто HashMap:

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

Подтипы, переопределяющие контракты супер-типа

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

Дальнейшая ссылка

В то время как вопросы контракта являются вопросом восприятия, проблема остановки, безусловно, является ошибкой. Я также задокументировал эту проблему в переполнении стека, где Бен Мейнс дал интересный ответ, приведший к предыдущему (нерешенному на начало 2015 года) сообщению об ошибке:

Мой собственный отчет (возможно, дубликат вышеупомянутого) также был быстро принят, так как:

Пока Oracle смотрит на это, не забудьте:

Никогда не используйте в методе ConcurrentHashMap.computeIfAbsent() . И если вы реализуете коллекции и думаете, что это хорошая идея — написать бесконечный цикл, подумайте еще раз и прочитайте нашу статью:

Бесконечные циклы. Или: все, что может ошибаться, да )

Мерфи всегда прав.

Ссылка: Избегайте рекурсии в ConcurrentHashMap.computeIfAbsent () от нашего партнера по JCG Лукаса Эдера из блога JAVA, SQL и JOOQ .
32
Share: