NonBlockingHashMap's computeIfAbsentc has a bug in a multithreaded environment about jctools HOT 11 CLOSED

I think you should use putIfAbsent .
computeIfAbsent was inherited from AbstractMap and is not thread-safe

from jctools.

The behaviour is not the same of concurrent hash map but of its interface ie concurrent map.
It means that the lambda can be called by many threads concurrently and/or many times.

from jctools.

The original design intention of NonBlockingHashMap is that all operations are lock-free implementations. However, the computeIfAbsent method involves transactional operations, and this transaction cannot be implemented without locking. Therefore, JCTools will not solve this problem.

The operations involved in this transaction are:

1. Determine whether the key exists
2. Generate value through lamdba
3. Put value into the container

NonBlockingHashMap only guarantees that the third step is thread-safe, and only one thread’s third step succeeds.

from jctools.

I think you should use putIfAbsent . computeIfAbsent was inherited from AbstractMap and is not thread-safe

PutIfAbsent cannot implement my business logic. I need to call my callback function to execute the business logic I specify when my map data does not exist, generate the objects required for the business function, and place them in my map. Obviously, if I use the putIfAbsent() method, I need to create it every time. I don't want to write so much synchronous judgment logic, otherwise I can solve the problem by simply using two synchronized methods, But this is not what I want.

from jctools.

The original design intention of NonBlockingHashMap is that all operations are lock-free implementations. However, the computeIfAbsent method involves transactional operations, and this transaction cannot be implemented without locking. Therefore, JCTools will not solve this problem.

The operations involved in this transaction are:

1. Determine whether the key exists
2. Generate value through lamdba
3. Put value into the container

NonBlockingHashMap only guarantees that the third step is thread-safe, and only one thread’s third step succeeds.

As a software engineer, I think this is its bug because it did not complete what I wanted as expected. I would rather the computeIfAbsent() method of NonBlockingHashMap be synchronized or locked, so that my business logic will not be wrong. It is obvious that it cannot be implemented, and the premise for software to achieve high concurrency is that its business processing is reliable, I haven't seen any prompts indicating that the method is unavailable or expired, so when I use it, I will notice that it obviously didn't crash when I use it on my website because all my data is incorrect and very difficult to troubleshoot. To achieve lockless modification, this method can be implemented through a callback interface, which I can also accept. However, although there is no lock now, my program data is incorrect. I think this method can refer to the spin lock method, or set a time or spin count or callback method to solve this problem. This is my suggestion, the author should not ignore it, otherwise many people like me will encounter the same problem

from jctools.

The behaviour is not the same of concurrent hash map but of its interface ie concurrent map. It means that the lambda can be called by many threads concurrently and/or many times.

If it doesn't support high concurrency, I think the official should label it because I have a deep understanding of it. I found that my data was incorrect, and after a long time of troubleshooting, I realized that this computeIfAbsent() method was a bug

from jctools.

The behaviour is not the same of concurrent hash map but of its interface ie concurrent map. It means that the lambda can be called by many threads concurrently and/or many times.

If it doesn't support high concurrency, I think the official should label it because I have a deep understanding of it. I found that my data was incorrect, and after a long time of troubleshooting, I realized that this computeIfAbsent() method was a bug

To summarize, your complaint is: the implementation of this method is not atomic, and the author should either make it atomic or inform the users.
First of all, the computeIfAbsent method originates from the ConcurrentMap interface, so the implementation of NonBlockingHashMap actually follows the rules of ConcurrentMap. If you carefully read the comments of all methods in ConcurrentMap, there is a sentence that says the action is performed atomically, which means that the implementation of this method must ensure atomicity, such as putIfAbsent, remove, replace, etc. These methods NonBlockingHashMap can guarantee their atomic execution. However, this sentence is not in the comment of the computeIfAbsent method, so the implementation of this method does not require atomicity, and only needs to ensure eventual consistency.
In addition, there is another rule that I don’t know if you are aware of? In NonBlockingHashMap, the remove operation only removes the value, and does not delete the corresponding key value (if the key is an object, then gc cannot recycle it). And this “bug” cannot be solved, which is still related to NonBlockingHashMap being a high-performance lock-free container.
I suggest you fully understand the characteristics and usage boundaries of this container before deciding whether to apply it to your production environment.

from jctools.

The action is atomic but there is no mention that no others can try attempting it too (and fail due to the atomicity of the state absent -> not absent).
What you are describing (and require) is an implementation detail of concurrent hash maps that lock the segment which belong the entry and prevent others to call more then one lambdas concurrently. The NonBlockingHashMap is fully non-blocking and don't employ that type of behavior.

Please check around other existing discussions on the list of closed issues that is very likely this has been already asked and answered.

Just a quick question: did you try evaluating if 2 concurrent thread calling computeIfAbsent race and both values are set (and can be observed in different times); or just just once the two win?
You can try this by making them to enter in the lambda at the same time by calling computeIfAbsent from different threads and awaiting till both are in their own lambda eg by suing a CyclicBarrier with value 2

Then, one will proceed immediately to set a value eg 2
and the other, instead wait 10 seconds before setting its value eg 3

you'll see that 3 won't be set (in theory...i gotta try myself :P)

Meaning that only one can win the race to set it, while the other would fail

from jctools.

This is a reproducer of the behaviour I've mentioned

    @Test
    public void testComputeIfAbsent() throws ExecutionException, InterruptedException {
        NonBlockingHashMap<Integer, Integer> hashMap = new NonBlockingHashMap<>();
        ExecutorService service = Executors.newSingleThreadExecutor();
        CyclicBarrier bothIn = new CyclicBarrier(2);
        CountDownLatch firstWin = new CountDownLatch(1);
        Future<?> setCompleted = service.submit(() -> {
            hashMap.computeIfAbsent(1, key -> {
                try {
                    bothIn.await();
                    firstWin.await();
                } catch (Throwable e) { }
                return 3;
            });
        });
        service.shutdown();
        hashMap.computeIfAbsent(1, key -> {
            try {
                bothIn.await();
            } catch (Throwable e) { }
            return 2;
        });
        Assert.assertEquals(Integer.valueOf(2), hashMap.get(1));
        // let the other thread to try update 1
        firstWin.countDown();
        setCompleted.get();
        Assert.assertEquals(Integer.valueOf(2), hashMap.get(1));
    }

from jctools.

ConcurrentSkipListMap similarly does not provide a computation that blocks and executes atomically. A simple workaround is to use putIfAbsent to store a future, and then compute it outside of the map. See jcip for an example, as it was idiomatic in Java 5.

from jctools.

+100 to @ben-manes to pointing a similar behaviour (will work on my same reproducer, indeed) in the JCL. I can close this as explained

from jctools.