ConcurrentHashMap and Fibonacci Numbers - Inconsistent result

Question

I wrote a program for calculating fibonacci numbers recursively, with a ConcurrentHashMap and computeIfAbsent() method:

Program works absolutely fine when i used small values like 8,9,10 but stuck in endless loop when value increased from 10 to 20 program never halts

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

Can some one tell me why it is being stuck forever?

You have the explanation below, but what I said about recursive Fibonacci is valid; use dynamic programming if you really have a need to generate high sequence Fibonacci numbers. — Tim Biegeleisen, May 04 '17 at 06:15
@TimBiegeleisen- Yes i will .. i was just playing with concurrent hash map and found this...:) — T-Bag, May 04 '17 at 06:24
@TimBiegeleisen OP was doing dynamic programming, only in a not-so-obvious way. Each term of fibonacci number is only computed if it is not previously computed. If it was preivously computed, the value is looked up from `concurrentMap` — Adrian Shum, May 04 '17 at 06:26
@AdrianShum Yes, I see that now. Today is Tim is wrong day. But it looks like this isn't a valid DP approach. — Tim Biegeleisen, May 04 '17 at 06:27
iterating on a map/list, either with a loop on recursively, must use a synchronise block that contains the whole iteration process, otherwise you will have concurrent trouble if the lop is executed a second time by another thread. — Walfrat, May 04 '17 at 09:19
Possible duplicate of [Recursive ConcurrentHashMap.computeIfAbsent() call never terminates. Bug or "feature"?](https://stackoverflow.com/questions/28840047/recursive-concurrenthashmap-computeifabsent-call-never-terminates-bug-or-fea) — UserF40, Jul 31 '17 at 16:32

score 28 · Accepted Answer · answered May 04 '17 at 06:06

28

You are hitting a deadlock.

computeIfAbsent on a ConcurrentHashMap will lock the bucket in which the corresponding key will go to. If you are attempting to calculate a Fibonacci that is higher than the number of buckets in your map, then the recursive calls will attempt to lock a bucket that is already locked further up the call stack. But of course, that lock cannot be released until all of the recursive calls have completed. Thus, your deadlock.

I would reconsider your decision to use a ConcurrentHashMap here.

answered May 04 '17 at 06:06

Joe C

15,324
8
38
50

I think this is the correct answer. I tried the same code with `HashMap` and it works for values larger than 20. On the other hand, for `ConcurrentHashMap` the code deadlocks when i>=14. – Eran May 04 '17 at 06:13
@Eran I agree with you. I blasted my answer based on that I know that recursive Fibonacci fails for relatively small numbers, without even considering that the `ConcurrentHashMap` was being used +1 – Tim Biegeleisen May 04 '17 at 06:14
4

It might be worth linking to the [JavaDocs from ConcurrentHashMap.computeIfAbsent](https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function-): "Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map." – Hulk May 04 '17 at 07:02
5

Ho the irony: HashMap is reentrant, but ConcurrentHashMap is not! – YSC May 04 '17 at 08:02
@YSC-what does you mean when you say Hash Map is reentrant – T-Bag May 04 '17 at 09:38

score 3 · Answer 2 · answered May 04 '17 at 06:31

This recursion method for calculating fibonaci numbers is of exponential complexity. With caching you decrease it back to linear, or you may use simple cycle instead of recursion to get linear algorithm.

I wonder why are you using ConcurentHashMap for caching. I would use either simple map, or array for caching.

Maps has advantage against arrays, when values are sparsed, but when you have sequence of numbers, you may use simple array.

T-Bag · Answer 3 · 2017-05-04T11:19:13.100

I took thread dump, and we can see that thread with lock 0x000000076b70bba0 is causing dead lock problem.

Please correct me if am wrong.

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

Indeed - and line 1674 of ConcurrentHashMap.java (in my jdk1.8.0_121) is `synchronized (f) {`, where `f` is a `Node`, in this case a `ReservationNode` - probably the same one locked at the very bottom of the stack, according to the hashes. — Hulk, May 04 '17 at 07:24
...all of these are of course implemention details, and might change any time. The important thing is the contract of ConcurrentHashMap.computeIfAbsent which states that the mapping function "must not attempt to update any other mappings of this map". (see also my other comment https://stackoverflow.com/questions/43774947/concurrenthashmap-and-fibonacci-number-inconsistent-result#comment74592799_43775058) — Hulk, May 04 '17 at 07:30

score 1 · Answer 4 · edited May 23 '17 at 11:55

As per the Oracle Doc

Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map

As rightly said by Joe C in the topmost answer, the default initialization of ConcurrentHashMap has a small number of buckets allocated at the time of instantiation.

The purpose of using ConcurrentHashMap is to allow concurrent modification of the Map from several threads without the need to block them (link).

If you still want to stay with using ConcurrentHashMap for your application, then I would recommend increasing the initialCapacity during its creation.

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

can calculate Fibonacci series upto and including 25

As per the doc,

ConcurrentHashMap()
Creates a new, empty map with the default initial table size (16).

However, I beg to differ on this as I noticed the default size is much smaller.
The reason for this is when you get the fibonacci(25) from ConcurrentHashMap<>(11) then ConcurrentHashMap<>() <-- should be default 16 here..but it is not.

There are 2 misunderstandings here: 1. The default initial capacity of a `ConcurrentHashMap` is 16 as stated in the JavaDocs. However, the default `loadFactor` is 0.75, so as soon as you put the 13th element to your Map, it attempts to grow. — Hulk, May 08 '17 at 10:52
2. Just because your Map has a capacity of 16, this does not mean that putting 16 entries in it will put them into separate buckets — Hulk, May 08 '17 at 10:53
Just an example: Fill a `HashMap` with the keys `k=[0,1,2,4,9,16,25..100]` (values don't matter), and you can verify with the help of a debugger that only 4 out of the 16 default buckets contain values, those at indices: 0, 1, 4, 9. The bucket at index 0 contains the mappings for the keys 0,16 and 64, the one at index 1 conatains mappings for 1, 49 and 81. — Hulk, May 08 '17 at 11:56

ConcurrentHashMap and Fibonacci Numbers - Inconsistent result

4 Answers4