Greater-than compare-and-swap

Question

As the title suggests, I'm looking for a compare-and-swap implementation, but with greater-than comparison:

if(newValue > oldValue) {
    oldValue = newValue;
}

where oldValue is some global shared state and newValue is private to each thread, without doing this:

synchronized(locker) {
    if(newValue > oldValue) {
        oldValue = newValue;
    }       
}

because I want a non-blocking solution. From studying source codes of other non-blocking operations, I've come up with this (assuming the values are integers):

AtomicInteger oldValue; // shared global variable

...

public boolean GreaterThanCAS(int newValue) {

    while(true) {
        int local = oldValue;
        if(local == oldValue) {
            if(newValue > local) {
                 if(oldValue.compareAndSet(local, newValue) {
                     return true;  // swap successful
                 } // else keep looping
            } else {
                 return false; // swap failed
            }
        } // else keep looping
    }
}

when // else keep looping happens, it means that another thread has changed the oldValue in the meantime and so I need to loop and try again.

Is this implementation correct (thread-safe)?

Osmen

This is only checking to see if thread switching occurred between assigning the local variable and checking to see if they're the same. Thread switching could occur after your if statement. So no, this is not thread safe, but without blocking I'm not sure if you'll find a solution. – Furuncle

@Shaded: The oldValue.compareAndSwap(local, newValue) call also returns false if the oldValue is not equal to local, so it also checks here. – Osmen

You do not need first equality comparizon. Just "if(newValue>local) oldValue.CAS(local, newValue) else repeat" is enough – Exordium

putIfGreater or something would be a better method name. – Trireme

(And oldValue is a very strange name. Hope it isn't really global.) – Trireme

Answer 1

I see no problems with your implementation, provided that no thread ever decreases the value of the AtomicInteger. If they do, your code is open to race conditions.

Note that the code can be simplified as follows:

public boolean GreaterThanCAS(int newValue) {
    while(true) {
        int local = oldValue.get();
        if(newValue <= local) {
             return false; // swap failed
        }
        if(oldValue.compareAndSet(local, newValue)) {
             return true;  // swap successful
        }
        // keep trying
    }
}

Antung

Thanks. You are right that decrementing would cause problems, but for my scenario, the value of oldValue can only change by executing this operation. Thanks also for the simplification suggestion. Now that I think about it, that if was indeed redundant. – Osmen

I think your code using <= for comparison in a method with GreaterThan in the name is a bit odd. – Trireme

@TomHawtin-tackline: I find this structure more readable that the original nested if statements. If one objects to the <=, one could just as easily phrase it as if(!(newValue > local)). I personally don't find this rephrased version any more or less clear than what I put in the answer. – Antung

Answer 2

Since Java 8 this can be simplified with use of updateAndGet:

public boolean greaterThanCAS(int newValue) {
    return oldValue.updateAndGet(x -> x < newValue ? newValue : x) == newValue;
}

Note that this would return true also in case when old and new values are equal. Give a try to @Adam's answer if this is not desired behaviour.

Charlie

x < newValue ? -newValue : newValue: why is this not x < newValue ? newValue : x? – Quigley

I don't think this works. Will return true if newValue == x – Senseless

@Senseless Yeah. And the last part of the answer mentions this case explicitly. ) – Charlie

Answer 3

I would re write it to look more like:

while(true) {
    int local = oldValue.get();
    if(newValue > local){
       if(oldValue.compareAndSwap(local, newValue) {
              return true;  // swap successful
        } // else keep looping 
    }else 
        return false;
 }

The equivalence check before the greater than check is redundant.

Otherwise it should work fine.

Coaster

Answer 4

@Vadzim, I would have commented on your post, but stackoverflow says I don't have enough points to post comments. Your answer is almost correct, but your function will always return false because getAndUpdate always returns the previous value, or 'x' in your case. I think all you would need to do is replace your last '==' with '<', e.g.:

 // return true if the assignment was made, false otherwise
 public boolean greaterThanCAS(int newValue) {
    return oldValue.getAndUpdate(x -> x < newValue ? newValue : x) < newValue;
 }

Dissimilate

Thanks for pointing out. This answer is also correct but I've fixed mine with switching to updateAndGet. Note that now answers differ in handling the case when old and new values are equal. It depends on context which behavior suits better. – Charlie