CODEWITHSUNDEEP
java
Daniel
Daniel

Reputation: 1676

How to achieve Map putIfAbsent semantics with computeIfAbsent efficiency?

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.

Upvotes: 6

Views: 1431

Answers (5)

matt
matt

Reputation: 12346

Consider your method foo ( which is literally a wrapper for putIfAbsent ).

String key = "test";
if(foo(key)){
    //Positive Branch. 
} else{
    //Negative Branch.
}

Now, in a multi-threaded environment, thread A calls and completes foo and adds a new value. It is going down the Positive branch. Before it enters the Positive branch, it gets scheduled for later. Thread B calls and completes foo, it continues executing and goes down the Negative branch.

The Negative branch is getting executed before the Positive branch, which in my mind is not wanted. In your particular case it might be OK. compute might be a better replacement.

map.compute( key, ( k, old ) -> {
    if(old==null){
        Value v = new Value();
        //positive branch.
        return v;
    } else{
        //negative branch.
        return old;
    }
});

Now you would be acting atomically on whether or not the value exists.

Upvotes: 0

assylias
assylias

Reputation: 328737

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.

Upvotes: 2

Bohemian
Bohemian

Reputation: 425198

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

Upvotes: 3

ernest_k
ernest_k

Reputation: 45329

One way is to use local state and update it in computeIfAbsent's mapping function:

boolean foo(String key) {
    boolean[] b = { false };
    map.computeIfAbsent(key, k -> {
        // do some stuff
        b[0] = true;
        return new Value();
    });
    return b[0];
}

Because mappingFunction is only run if the key is not present in the map, you can guarantee that the heavy new Value() is only called when necessary and that the return value is set to true only when there was no mapping before the call.

Upvotes: 1

Michael
Michael

Reputation: 44200

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

Upvotes: 1

Related Questions