ConcurrentHashMap i Fibonacciego Liczby - Niezgodne wynik

Question

Napisałem program do obliczania liczby Fibonacci rekurencyjnie, z ConcurrentHashMap i computeIfAbsent() metody:

program działa absolutnie bez zarzutu, gdy użyłem małych wartości jak 8,9,10 ale utknęła w niekończącej się pętli, gdy wartość wzrosła z 10 to 20program nie zatrzymuje

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

    public static void main(String[] args) { 
     System.out.println("Fibonacci result for 20 is" + fibonacci(20)); 
    } 

    static int fibonacci(int i) { 
     if (i == 0) 
      return i; 

     if (i == 1) 
      return 1; 

     return concurrentMap.computeIfAbsent(i, (key) -> { 
      System.out.println("Value is " + key); 
      return fibonacci(i - 2) + fibonacci(i - 1); 
     }); 
    } 
} 

Czy ktoś mi powiedzieć, dlaczego jest tkwić wiecznie?

Answer 1

Uderzasz w zakleszczenie.

computeIfAbsent na ConcurrentHashMap zablokuje wiadro, w którym znajduje się odpowiedni klucz. Jeśli próbujesz obliczyć wartość Fibonacci wyższą niż liczba segmentów na mapie, połączenia rekursywne będą próbowały zablokować zasobnik, który jest już zablokowany na stosie wywołań. Ale oczywiście tej blokady nie można zwolnić, dopóki wszystkie rekurencyjne połączenia nie zostaną zakończone. Zatem twój impas.

Chciałbym ponownie rozważyć decyzję o użyciu tutaj ConcurrentHashMap.

Answer 2

Ta metoda rekursji do obliczania liczby fibonaci ma wykładniczą złożoność. Przy buforowaniu zmniejszasz ją z powrotem do liniowości lub możesz użyć prostego cyklu zamiast rekursji, aby uzyskać liniowy algorytm.

Zastanawiam się, dlaczego używasz ConcurentHashMap do buforowania. Chciałbym użyć albo zwykłej mapy, albo tablicy do buforowania.

Mapy mają przewagę nad tablicami, gdy wartości są sparowane, ale jeśli masz sekwencję liczb, możesz użyć prostej tablicy.

Answer 3

Zrobiłem zrzut wątku i widzimy, że wątek z blokadą 0x000000076b70bba0 powoduje problem martwej blokady.

Proszę mnie poprawić, jeśli się mylę.

main - priority:5 - threadId:0x00000000021af000 - nativeId:0x2798 - state:RUNNABLE 
    stackTrace: 
    java.lang.Thread.State: RUNNABLE 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674) 
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c720> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c5c0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c460> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c300> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c1a0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70c040> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70bee0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.lambda$0(Test.java:20) 
    at Test$$Lambda$1/834600351.apply(Unknown Source) 
    at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1660) 
    - locked <0x000000076b70bba0> (a java.util.concurrent.ConcurrentHashMap$ReservationNode) 
    at Test.fibonacci(Test.java:18) 
    at Test.main(Test.java:8) 
    Locked ownable synchronizers: 
    - None 

Answer 4

Jak na Oracle Doc

Kilka prób operacji aktualizacji na tej mapie przez innych wątków może być zablokowana podczas obliczeń jest w toku, więc obliczenia powinny być krótkie i proste, i nie należy próbować aktualizować innych mapowania tej mapie

Jak słusznie powiedział przez Joe C w najwyższej odpowiedź, domyślna inicjalizacja ConcurrentHashMap ma SMA Liczba łyżek przydzielonych w momencie tworzenia.

Celem użycia ConcurrentHashMap jest umożliwienie równoczesnej modyfikacji mapy z kilku wątków bez konieczności ich blokowania (link).

---

Jeśli nadal chcą pozostać z użyciem ConcurrentHashMap dla danej aplikacji, to polecam zwiększenie initialCapacity podczas jego tworzenia.

static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>(11); 

może obliczyć szereg Fibonacciego do września włącznie 25

---

Jak na doc,

ConcurrentHashMap()
Tworzy nową, pustą mapę z domyślnym początkowego rozmiaru tabeli (16).

Jednak proszę się różnić, ponieważ zauważyłem, że domyślny rozmiar jest znacznie mniejszy.
Powodem tego jest, gdy masz fibonacci(25) z ConcurrentHashMap<>(11), a następnie ConcurrentHashMap<>() < - powinno być domyślnie 16 tutaj .., ale nie jest.