Рекурсивный 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 потому что я думал сделать этот пример еще более сложным, введя параллелизм (который я не сделал в конце концов).
теперь, давайте увеличим число от 8 до 25 и наблюдать за тем, что бывает:
System.out.println(
"f(" + 25 + ") = " + fibonacci(25));
программа никогда не останавливается. Внутри метода есть цикл, который просто работает вечно:
for (Node<K,V>[] tab = table;;) {
// ...
}
я:
C:UsersLukas>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)
Маттиас, читатель этого сообщения в блоге также подтвердил проблему (он действительно нашел его).
это странно. Я ожидал бы любого из следующих двух:
- он работает
- он бросает!--9-->
но только не остановились? Это кажется опасным. Это баг? Или я неправильно понял какой-то контракт?
3 ответов:
это исправлено в JDK-8062841.
на предложение 2011, Я определил эту проблему во время проверки кода. JavaDoc был обновлен и временное исправление было добавлено. Он был удален в дальнейшем переписать из-за проблем с производительностью.
на обсуждение, мы исследовали способы лучшего обнаружения и сбоя. Обратите внимание, что часть обсуждения была переведена в автономный режим на частную электронную почту для рассмотрения изменений низкого уровня. Пока нет каждый случай может быть покрыт, общие случаи не будут livelock. Эти исправления находятся в репозитории Doug, но не превратили его в выпуск JDK.
это конечно a "функции". Элемент
ConcurrentHashMap.computeIfAbsent()Javadoc читает:если указанный ключ еще не связан со значением, пытается вычислить его значение с помощью данной функции отображения и вводит его в эту карту, если null. Весь вызов метода выполняется атомарно, поэтому функция применяется не более одного раза на ключ. Некоторые попытки обновления этой карты другими потоками могут быть заблокированы во время вычислений выполняется, поэтому вычисление должно быть коротким и простым, и не следует пытаться обновить любые другие сопоставления этой карты.
The "не должен" формулировка-это четкий контракт, который мой алгоритм нарушил, хотя и не по тем же причинам параллелизма.
что еще интересно, так это то, что нет
ConcurrentModificationException. Вместо этого программа просто никогда не останавливается - что по-прежнему является довольно опасным багом на мой взгляд (т. е. бесконечные циклы. или: все, что может пойти не так, делает).Примечание:
The
HashMap.computeIfAbsent()илиMap.computeIfAbsent()Javadoc не запрещает такие рекурсивные вычисления, что, конечно, смешно, поскольку тип кэшаMap<Integer, Integer>, а неConcurrentHashMap<Integer, Integer>. Для подтипов очень опасно резко переопределять контракты супертипа (SetиSortedSetэто приветствие). таким образом, он должен быть запрещен также в супер типах, чтобы выполните такую рекурсию.
Это очень похоже на баг. Потому что, если вы создадите свой кэш с емкостью 32, ваша программа будет работать до 49. И интересно, что параметр sizeCtl =32 + (32 >>> 1) + 1) =49! Может быть причина в изменении размера?
Comments