Threadsafe "put if greater" in map method

Question

I have a ConcurrentMap<Key, Long> that is a cache from some key to the greatest value for it that has been seen so far. If two values come in at once, I want to ensure that the larger one is inserted into the map. What's the cleanest way to do this?

One ugly way is to write a class LargestLong with an UpdateIfBigger method, that will probably involve some CAS loop. I don't see a way to do such a CAS loop on a ConcurrentHashMap directly.

Or use a ConcurrentMap<Key, AtomicLong> and a CAS loop after retrieval. I've heard it's usually a sign of a design flaw to use a concurrent collection against an atomic primitive like this, but this may be an exception.

Answer 1

Ideally, you should start with a simple synchronized block, identify that it indeed creates a bottle neck, then try to do it lock free. Maybe more complicated solution is not worth the effort or you have a bottle neck elsewhere?

John's solution seems faster but, if this is critical section of your program, you might want to also test the following (using just ConcurrentMap's atomic methods):

ConcurrentMap<Key, Long> map = new ConcurrentHashMap<>();

public boolean putIfGreater(Key key, long value) {
    Long boxedValue = Long.valueOf(value);
    Long current = map.putIfAbsent(key, boxedValue);
    if (current == null) {
        return true;
    } else {
        while (true) {
            if (value < current) {
                return false;
            }
            if (map.replace(key, current, boxedValue)) {
                return true;
            }
            current = map.get(key);
        }
    }
}

Answer 2

The best way to do this is to use an AtomicLong. You would get the current value and if it's greater than try to replace it, if you fail try again.

ConcurrentMap<Key, AtomicLong> map = new ConcurrentHashMap<>();

public static boolean putIfGreater(Key key, long value){
     // assuming it's never null at this point
     AtomicLong val = map.get(key);
     long current = val.get();

     for(;;){
        if(value < current)
             return false;
        if(val.compareAndSet(current, value))
             return true;
         current = val.get();
     }
     return false;
}

In this case, it checks first to see if it's greater, if it is it tries to set it. If it fails to set it (another thread beat that thread) then it will try again IFF it is greater than the updated value.

I've heard it's usually a sign of a design flaw to use a concurrent collection against an atomic primitive like this, but this may be an exception.

If your alternative is to use locks, I would tend to disagree in this case. If you have any links to that argument I would be happy to read it.

Answer 3

What about map.merge(key, value, Long::max)?

If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null. This method may be of use when combining multiple mapped values for a key.

Given a ConcurrentMap, you can assume this is thread-safe.

The default implementation makes no guarantees about synchronization or atomicity properties of this method. Any implementation providing atomicity guarantees must override this method and document its concurrency properties. In particular, all implementations of subinterface ConcurrentMap must document whether the remapping function is applied once atomically only if the value is not present.

But assuming your using a ConcurrentHashMap, then:

The entire method invocation is performed atomically.

Answer 4

The key point here is the wording "at the same time" I believe. None of the values would be inserted at the exact same time.

I would create a second thread and a ConcurrentSet which gathers all incoming data, that thread would be picking largest value from the Set and inserting values to your cache.

Because there is no exact same time, you could only optimize incoming data by observing them at fixed time rate.