17

C++11 has a 'compare and exchange' operation for atomic variables.

The semantics are:

Atomically compares the value pointed to by obj with the value pointed to by expected, and if those are equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value pointed to by obj into *expected (performs load operation).

I want to do the same, but instead of setting *obj when the values are equal, I want it to be set when one is greater-than the other (assume we're talking about an ordered type).

Is this supported somehow? Achievable by some hack perhaps?

Note: A CAS loop will not do for me, since both the values I'm comparing might change between non-atomic operations.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • This is very simple to do in a loop and I'm sure someone will give you details soon, but tell me, how do you want to use this operation? – avakar Jul 17 '13 at 13:45
  • 1
    You can do a CAS loop, like http://stackoverflow.com/questions/16190078/how-to-update-an-atomic-maximum/16190791#16190791 . This might be a duplicate even, if I understand correctly. – zch Jul 17 '13 at 13:46
  • possible duplicate of [atomic compare(not equal) and swap](http://stackoverflow.com/questions/12755130/atomic-comparenot-equal-and-swap) – Kerrek SB Jul 17 '13 at 13:46
  • Do you mean a that obj is a pointer to an ordered object and you want to set a pointer depending on the compare result of the two objects you point to? If so: This is not possible since CAS deals with one memory address only. Your request deals with at least two memory addresses: The address of the pointer variable (the thing you want to swap) and the address of the data you want to compare. – mmmmmmmm Jul 17 '13 at 14:47
  • I, too, wish this existed, but it does not (apart from conceptually, of course, and workarounds that (potentially) use more than a single atomic instruction). – Cameron Jul 17 '13 at 15:08
  • @avakar: I was thinking of using this for a certain sorting I'm doing. – einpoklum Jul 18 '13 at 04:52
  • @KerrekSB: It's not a dupe, although they're very related. Any two values can be 'not equal', but for greater-than/lesser-than you need to have order. – einpoklum Jul 18 '13 at 04:53
  • @Cameron: Make that an answer? – einpoklum Jul 18 '13 at 04:54
  • As for the slightly complicated conditions, maybe we can refer to [the implementation](https://hg.openjdk.java.net/jdk/jdk11/file/76072a077ee1/src/java.base/share/classes/java/util/concurrent/atomic/AtomicLong.java) of the [getAndUpdate](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/atomic/AtomicLong.html#getAndUpdate(java.util.function.LongUnaryOperator)) or [updateAndGet](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/atomic/AtomicLong.html#updateAndGet(java.util.function.LongUnaryOperator)) method in Java `AtomicLong`. – samm Jan 06 '22 at 08:28

3 Answers3

15

I think you misunderstand how compare and swap/exchange works: the basic idea is that having looked at the current value you can work out some corresponding new value - and you attempt that update. If it succeeds - great - continue with whatever you need to, but if it fails then start all over again: looking at the new value that some other thread's put in there and thinking about the value that you'd consequently now need.

I want it to be set when one is greater-than the other (assume we're talking about an ordered type).

So say you want to store 11 but only if the existing value's still atomically less than 11. You won't find an instruction to do that directly, but you can easily do it with the existing compare and swap:

int target_value = 11;
do {
    int snapped_x = x;
    if (snapped_x >= target_value)
        what do you want to do instead?
} while (!compare_and_swap(x, snapped_x, target_value));
         // ...or whatever your exact calling convention is...

You still get the behaviour you want, just with a potentially higher failure/spin rate....

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • 2
    That doesn't really help me, because my target value can change after each atomic instruction I perform in this loop. – einpoklum Jul 18 '13 at 04:57
  • 1
    So? Just put the instructions to recalculate it into the "what do you want to do instead" statement(s).... – Tony Delroy Jul 18 '13 at 05:09
  • 2
    That doesn't help. Once I get to the while condition, `target_value` is no longer what it was in the "what to do instead" statement/s. – einpoklum Jul 18 '13 at 07:06
  • 1
    Why wouldn't it be? The "what to do instead" statements are *immediately* followed by the `while` condition... you are in complete control of the `target_value` variable. Not meaning to be rude, but either we've got a huge communications divide here (I'm struggling to see what to explain), I should find another profession, or you're completely failing to grok how CAS works and maybe should look at some implementations of simple things like incrementing a counter - make sure they sink in...? – Tony Delroy Jul 18 '13 at 07:12
  • Perhaps it's worth saying that setting a target value doesn't mean you're expecting that target value to still be valid when the CAS kicks in... the whole point is having a relationship between the current value `snapped_x` and the target value such that if `snapped_x` *hasn't* been changed by another thread meanwhile then you can be sure the target will still be valid. If `snapped_x` changes you get to recalculate the target... – Tony Delroy Jul 18 '13 at 07:19
  • Also note that "compare-and-swap" typically updates the "current" value with the real value if the operation failed, so the explicit reloading isn't necessary. – Kerrek SB Jul 18 '13 at 08:19
  • @KerrekSB: to the best of my recollection, not on Sun UltraSparcs... still, people should check their instrinsic's or assembly instruction's documentation: parameter order, by reference/pointer etc. may also differ. – Tony Delroy Jul 18 '13 at 08:42
6

As requested, here's my comment as an answer:

I, too, wish this existed, but it does not, as far as I know (certainly not for x86/x64), apart from conceptually, of course, and workarounds that (potentially) use more than a single atomic instruction (which work but are not wait-free).

Cameron
  • 96,106
  • 25
  • 196
  • 225
2

This may be an old question, but I think many people will want this kind of feature. I come up with an idea, here show the pseudo code(I am linux kernel people, so use some kernel functions).

update(new)
{
  old = atomic_read(&pvalue);
  while (old < new) {
    v = atomic_cmpxchg(&pvalue, old, new);
    if (v != old) {
      old = v;
      continue;
    }
  }
}

The code doesn't try cmpxchg for old value less than new value.
If there are concurrency issues, please tell me. Thanks:)

Takuya Okamoto
  • 31
  • 2