Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to achieve Map putIfAbsent semantics with computeIfAbsent efficiency?

Tags:

java

Consider the following code:

ConcurrentHashMap<String, Value> map = new ConcurrentHashMap<>();

boolean foo(String key) {
    Value value = map.get(key);
    if (value == null) {
        value = map.putIfAbsent(key, new Value());
        if (value == null) {
            // do some stuff
            return true;
        }
    }
    // do some other stuff
    return false;
 }
    

Assume that foo() is called by multiple threads concurrently. Also assume that calling new Value() is expensive. The code is verbose and can still result in redundant Value objects created. Can the above logic be implemented in a way that guarantees no redundant Value objects are created (i.e. new Value() is called at most once)? I'm looking for a clean implementation- minimal code without acquiring locks explicitly.

computeIfAbsent could have been a good alternative, however its return semantics are not in line with the required logic.

like image 848
Daniel Nitzan Avatar asked Jul 01 '20 08:07

Daniel Nitzan


3 Answers

Some minimal code that does the job:

boolean foo(String key) {
    AtomicBoolean flag = new AtomicBoolean();
    Value value = map.computeIfAbsent(key, k -> {flag.set(true); return new Value();});
    if (flag.get()) {
        // do some stuff
    } else {
        // do some other stuff
    }
    return flag.get();
}
like image 161
Bohemian Avatar answered Oct 11 '22 11:10

Bohemian


One solution is to store Future<Value> instead of Value in the map:

ConcurrentHashMap<String, Future<Value>> map = new ConcurrentHashMap<>();

boolean foo(String key) {
    Future<Value> value = map.get(key);
    if (value == null) {
        value = map.putIfAbsent(key, new FutureTask<Value>(() -> new Value()));
        if (value == null) {
            // do some stuff
            return true;
        }
    }
    // do some other stuff
    return false;
}

You can access the underlying value by calling value.get(), which will block until the computation is complete.

There is a chance that more than one FutureTask is created, but only one will reach the map and only one computation of new Value() will be done.

like image 2
assylias Avatar answered Oct 11 '22 12:10

assylias


First let's fix the fact that you are not acting atomically, and do a needless look-up. Two threads could both simultaneously pass the first value == null check. Not really a problem now (except 2 Values will be created, which is slow), but a bug waiting to happen if someone adds an else clause to the second value == null check. It's cleaner this way too.

boolean foo(String key) {
    Value value = map.putIfAbsent(key, new Value());
    if (value == null) {
        // do some stuff
        return true;
    } 
    else {
       // do some other stuff
       return false;
    }
 }

Now let's address the fact that Value creation is slow (sounds like you are abusing constructor, but anyway).

 boolean foo(String key) {
    final AtomicBoolean wasCreated = new AtomicBoolean(false);
    final Value value = map.computeIfAbsent(key, k -> {
        wasCreated.set(true);
        return new Value();
    });
    if (wasCreated.get()) {
        // do some stuff
        return true;
    } 
    else {
       // do some other stuff
       return false;
    }
 }
like image 1
Michael Avatar answered Oct 11 '22 12:10

Michael