Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

atomic_compare_exchange with greater-than instead of equals?

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.

like image 498
einpoklum Avatar asked Jul 17 '13 13:07

einpoklum


3 Answers

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....

like image 97
Tony Delroy Avatar answered Nov 15 '22 15:11

Tony Delroy


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).

like image 40
Cameron Avatar answered Nov 15 '22 15:11

Cameron


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:)

like image 44
Takuya Okamoto Avatar answered Nov 15 '22 17:11

Takuya Okamoto