compareExchange interface does not match C/C++

[ronawho]

Unlike the rest of our atomic API, the interface for compareExchange does not match C/C++. Ignoring memory orders, the Chapel interface is:

proc compareExchangeStrong(expected: T, desired: T): bool

and C/C++ is:

bool compare_exchange_strong(T& expected, T desired);

Where the difference is that C/C++ take expected by ref and on failure the expected value is updated to be the value of the atomic. Should we update our implementation to match? Note that if we do I don't think it's possible to deprecate the old style and implement the new one, I think this would be a breaking change. (Assuming we don't change names, which would also be unfortunate.)

The advantage of updating expected by ref is that the NIC/processor already has to load the old value to do the comparison so if expected is passed by ref it can get updated for free. If it's not passed by ref the user needs to do another atomic read(), which is not free. The downside to passing expected by ref is that it's a breaking change (and the behavior may be a little subtle, but it matches what C/C++ does)

The code below compares what a spinlock and an atomic-fetch-multiply look like today vs. with expected passed by ref and updated

Spinlock:

This is a pretty weak example since you'd use testAndSet/clear in reality but it does showcase that when you don't want to update the expected argument, you have to add more code to clear the update (however clearing it is cheap computationally)

/* spinlock today */
var l: atomic bool;

proc lock() {
  while !l.compareExchangeStrong(false, true) {
  }
}

proc unlock() { l.write(false); }

/* spinlock if `expected` is passed by ref and updated on failure */
var l: atomic bool;

proc lock() {
  var expected = false;
  while !l.compareExchangeStrong(expected, true) {
    expected = false;
  }
}

proc unlock() { l.write(false); }

Atomic multiply:

This is also a little weak, but it is much more compelling if you think about classes being atomically exchanged for lock-free data structures (it's just that we don't currently support atomic ops on classes):

/* Atomic multiply today */
proc AtomicT.fetchMult(multiplier: T) {
  var oldValue = this.read();
  while !this.compareExchangeStrong(oldValue, oldValue * multiplier) {
    oldValue = this.read(); // Extra load
  }
  return oldValue;
}

/* Atomic multiply if we passed `expected` by ref and updated on failure */
proc AtomicT.fetchMult(multiplier: T) {
  var oldValue = this.read();
  while !this.compareExchangeStrong(oldValue, oldValue * multiplier) {
  }
  return oldValue;
}

---

I do not have any strong preferences here. I like matching the C/C++ interface like we do for everything else, but it took me a while to get used expected getting updated, and this is an incompatible breaking change.

Here's some related information about what Rust did. Rust used to have a compare_and_swap, but they added a compare_exchange that is more similar to the C/C++ variants (and I believe they intended to deprecate compare_and_swap, but they never did that). However, instead of taking expected by ref, Rust returns a Result indicating whether the new value was written and containing the previous value (for us I guess this would be a tuple that contains (performedExchange, origValue)?)

• https://github.com/rust-lang/rfcs/blob/master/text/1443-extended-compare-and-swap.md
• Tracking issue for compare_exchange rust-lang/rust#31767

---

Options that I can think of in no particular order (note that I don't like many of these, and there are likely other options I'm not thinking of):

• leave compareExchange as-is (requires a non-free atomic load when compareExchange fails)
• update the interface to take expected by ref and update on failure (breaking change)
• keep compareExchange as-is and add an additional method that takes expected by ref (compareExchangeUpdate()?)
• add a param to compareExchange that controls whether expected is passed by ref?
  • compareExchange(expected, ...) ...
  • compareExchange(ref expected, ..., param updateExpected)...
• keep compareExchange as-is and add an additional method that returns a tuple of (success, oldVal)
• Deprecate exchange/compareExchange and add new methods with different names that match the C/C++ interface (maybe swap/compareSwap)

[mppf]

I don't have a strong preference between the tuple return and ref versions, but I think I slightly prefer the ref version.

I think we should, at the end of the day, have 2 variants of compareExchange:

• one that behaves as our current compareExchange does
• one that somehow returns the old value

All this taken together leads to:

• rename the current compareExchange to compareAndSwap (or something)
• make a compareExchange with a ref argument and that matches the C/C++ version in behavior and in name (aside from camelCase)

[ronawho]

Based on exchanges in #10001, @LouisJenkinsCS is likely to have an opinion here.

[LouisJenkinsCS]

I'm in agreement with @mppf that there should be another variant, but I think the original should be unchanged and that instead compareAndSwap should be created that takes a reference and returns a boolean. Again, atomics are far too fundamental to just change the semantics of

[bradcray]

I'm catching up on this issue... It feels unfortunate to me to live with a difference like this from C/C++ for all time given how similar our interface is otherwise, making me want to make the two match now before more time goes on. I also think there's a potential correctness/confusion issue if we leave it as-is which I'll get to below.

@mppf: Do you recall the historical reason for why our compareExchange()'s interface differs from C++'s in the first place? (it looks like it's had this signature since you contributed the code). Best guess number 1: Was this before we had ref intents? (a quick look at the history suggests that this is the case whether or not it was the reason... atomics were introduced in 1.5.0 and ref intents in 1.6.0). Best guess number 2: Was this when the C/C++ interfaces were still in flux? (i.e., maybe this was the proposed interface at that time and then it changed?)

So thinking about what the new interface would look like:

proc compareExchangeStrong(ref expected: T, desired: T): bool

It seems like the two ways that this change could break existing code would be (a) a user didn't pass an l-value into the expected argument (e.g., they passed 0 instead, or (b) they did pass in an -value, but baked assumptions into their code that it would still be holding the same value after the call. Is that right? If so...

The first is a breaking change that would be easy to deal with (though still annoying) because your code wouldn't compile until you fixed it, so the lack of a deprecation warning doesn't seem like a big deal... you wouldn't be surprised once you understood what had changed and what you had to do to address it. The main downside of this is that it feels like it would be natural to say something like "I expect the value to be 0" where now, you have to store that 0 into a variable or call a different routine (I never thought I'd say it, but this makes me wish we had overloading based on argument intents, possibly for the first time).

The second is more subtle, assuming that people did pass in l-values... but would they really write code that relied upon the value being the same after the call? My bigger fear here points to a really important reason to unify with C++ for me: If you were coming from C++ assuming we behaved the same, and were checking to see whether or not the CAS succeeded by looking at whether or not expected was the same after the call (ignoring the return value), you could be led to believe that it always succeeded, right? (e.g., if you overlooked that it doesn't have a ref intent in the documentation).

Also interesting is that looking at the Wikipedia entry for compareAndSwap(), its behavior matches our current behavior, suggesting that introducing a second routine named compareAndSwap() which had the current behavior would make sense (though I suspect we could find additional examples for either name with different interfaces without searching very hard...).

So I think I'm leaning heavily towards unifying with C++ and making the current behavior available as compareAndSwap() where it seems like the three ways we could transition people would be:

1. Switch the interface now, have users work through cases of behavior (a), and hope nobody is relying on behavior (b). Louis, you've probably written more atomics code than most users... do you have practical cases where you pass in an l-value in and rely on the value being unchanged after the call? Or do you mostly pass r-values in? (case (a)).

2. Switch the interface, insert a warning for all calls to the routine alerting users to its changes, and a config param (mentioned in the warning itself) by which they can disable those warnings once they have.

3. Don't switch the interface, but add compareAnd Swap() and have compareExchange*() warn that its definition is about to change such that you should change existing calls to it to compareAndSwap() now unless you're comfortable with the change.

Option 3 is obviously the safest, but also could be annoying if what you really wanted was the C++ routine (since you'd change your code now to avoid the warning then change it back to get the C++ behavior in the next release...). So it's also the slowest. Although I suppose we could have a config param to disable the warning so that you could stay in the compareExchange() world if that's where you wanted to end up...

Option 2 feels safe, but noisy and would rely on code that uses the routine to throw the config param for all compiles until the next release.

Option 1 is the least safe, but also maybe not that bad if users' code doesn't bake assumptions in that the argument's value wouldn't change.

I think any of these three either options 2 and 3 are on the table for me. What do you guys think?

[edit: I've scratched out my previous open-ness to option 1 based on Louis's example in the next comment]

[LouisJenkinsCS]

Switch the interface now, have users work through cases of behavior (a), and hope nobody is relying on behavior (b). Louis, you've probably written more atomics code than most users... do you have practical cases where you pass in an l-value in and rely on the value being unchanged after the call? Or do you mostly pass r-values in? (case (a)).

I can say that I have definitely written code where I assume that the 'expected' operand has not changed. Since you asked for a practical one, I can show you at least one which the C++'s tendency to update the 'expected' operand has bit me before, and that's the K42 MCS Spinlock. In particular, this part...

                      L->next := nil
                      if ! compare_and_store (&L->tail, &I, &L->next)
                          // somebody got into the timing window
                          repeat
                              successor := I.next
                          while successor = nil     // wait for successor
                          L->next := successor
                      return

  proc acquire (list : List)
      var node = new ListNode();
      node.next = nil

      predecessor = list.tail.exchange(node);
      if predecessor != nil {     // queue was non-empty
          node.locked.write(true);
          predecessor.next = node;
          node.waitFor(false);               // wait for lock
  
      // I now have the lock
      successor = node.next;
      if successor = nil {
          // ??? Need to think about how L->next translates in Chapel...
          if list.tail.compareExchange(node, ...) {
              // somebody got into the timing window
              do {
                  successor = node.next;
              } while successor = nil;          // wait for successor
              // ???
      else
          // ???

The important part here is the fact that successor = node.next relies on node to have not changed, since the current node acts as a node a list of successors; if this is swapped out, you end up advancing to the head of the list and leave acquire before you actually hold the critical section, resulting in undefined behavior. Again, this happens in C++ as well, but given that you can write this now in Chapel without this problem, it'd be pretty bad if someone had wrote their own custom lock (which isn't entirely unreasonable for someone to do).

I know for a fact that I have done something similar in the past, but worst part is I don't know where so a change like this would be like a ticking time bomb (okay, that is a bit of hyperbole, but still it'd be an unexpected problem).

Again, I prefer compareExchange remain unchanged and that compareAndSwap be added that have the new interface changes, which is the safest of all since it breaks no code and only adds functionality.

Also as to how often I pass in r-values... very often, nil is a common one, as it is an essential sentinel value in a lot of data structures and algorithms. Of course that's with my own AtomicObject abstraction, when it comes to using atomic bool, very often I use true and false, and when using atomic int I often use r-value constants such as 0 or 1 or even my own param/const definitions.

[bradcray]

Thanks for the detailed follow-up. I think your example (passing an existing field in as the expected value and not wanting it to change) has talked me out of option 1 as being too dangerous and for behavior (b) being more likely than I had hoped.

I'm still not convinced that leaving compareExchange() as-is is as safe as you claim, though. Safe for existing Chapel programs sure, but not necessarily safe for future ones and users. For someone coming to Chapel from C++ who assumes the interface is the same and ignores the return value. I.e., if I wrote the following code I could incorrectly conclude that the action had succeeded when it had not, right?

var x: atomic int = ...;
var value1 = 42;
var value2 = 33;
x.compareExchangeStrong(value1, value2);
if (value1 == 42) then
  // Yay!  compareExchange succeeded!

Now sure, this is my fault as a user for not reading the docs more carefully / checking the return value, but given that it appears that we modeled our routines after C/C++ (and we did), it would be reasonable to assume that they were all the same once I'd verified that a few routines matched as expected and adjusted to the camelCase naming.

I also hear your preference for Chapel's current behavior for compareExchange() over the proposed / C++ approach, but that seems more like an argument with C++'s choice than with Chapel's (assuming I'm correct that we only diverged because we didn't yet have the ability to express a ref argument...). If languages that we tend to look to as kindred spirits or for guidance (e.g., Swift, Rust, Python, maybe C# and Java) used the compareExchangeStrong() name yet matched Chapel's current behavior, that would be more compelling to me. Otherwise, my thought is that you should switch to using compareAndSwap() (or whatever we end up calling it) since that's the behavior you prefer (and frankly, I think it's a better name anyway...).

[LouisJenkinsCS]

I'll just say that I'm sticking with my original stated preferences, but I'll also say that I suppose it wouldn't be too much effort to find-and-replace compareExchange to compareAndSwap and incrementally convert my old code to use the new semantics of compareExchange... just please don't do option 1, option 3 sounds preferable.

[mppf]

@mppf: Do you recall the historical reason for why our compareExchange()'s interface differs from C++'s in the first place? (it looks like it's had this signature since you contributed the code).

I think I hadn't picked up on the fact that the C/C++ version was modifying one of the arguments. I don't know if it was already standardized that way, but I'm guessing that it probably was and it was an oversight on my part.

[mppf]

I'd also like to propose Option 2.5:

Start with option 3:

Don't switch the interface, but add compareAnd Swap() and have compareExchange*() warn that its definition is about to change such that you should change existing calls to it to compareAndSwap() now unless you're comfortable with the change.

But mark the compareExchange* calls as "last resort".
Then, add a Package module called NewCompareExchange that implements the compareExchange* calls. Code wanting the new behavior can use NewCompareExchange;

That way:

• old code must be migrated (but won't break in this release)
• new code can opt in to the new behavior if it wants to be forward looking; we just deprecate NewCompareExchange in the next release.

Option 3 by itself would also not bother me much, since one might argue this is a library stability vs language stability issue.

[ronawho]

I'd be fine with either option 2.5 or 3

To me, compareAndSwap and compareExchange are interchangeable terms. I think I'd always have to look up or compile an example to remember which one does what. (CAS is the more natural textbook term to me, but CMPXCHG is the intel instruction.)

(I don't have any better naming suggestions, just noting that the names don't give me any indication of which one updates expected)

[bradcray]

I agree that the names don't distinguish from one another very well, but I also think that either name in isolation doesn't make it all that clear what it does with that first argument, so maybe it doesn't matter all that much and it's just a learning curve (or chance to read the documentation or see which one complains about passing in a literal).

If I wanted to work harder at distinguishing them, I might call the current behavior compareAndSwapValue (or compareSwapValue) but I don't know that doing so really helps that much because compareExchange is also comparing and exchanging a value, it's just a value that's referred to when it's passed in.

We could make both options use new names like compareExchangeViaRef vs. compareExchangeValue but once the strong and weak are also put in there, it starts to feel more annoyingly wordy than clearly beneficial to me.

[ronawho]

I'm currently leaning towards option 3. My preference is to deprecate compareExchange(), compareExchangeStrong(), and compareExchangeWeak() this release in favor of a single compareAndSwap() and then next release update compareExchange() and compareExchangeWeak() to match the C/C++ interface. (I could also be talked into compareAndSwap() and compareAndSwapWeak(), but I think if the Weak optimization is important enough to a user, they can just deal with the different compareExchange interface.

Option 2.5 is also reasonable, but I'm not sure it adds a ton of value and users would have to modify their code next release to remove the use NewCompareExchange. I could be talked into that if people feel strongly, but deferring would also give us more time to implement and test, which might be nice since there are 5 atomic implementations to update: locks, intrinsics, cstdlib, ugni, and ofi. (I have started on the implementation now in case that's the route we want to go though.)

---

Once everything settles for either proposal 2.5 or 3, I think we'd have:

proc compareAndSwap(expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool

/* Matches C/C++ compare_exchange_strong */
proc compareExchange(ref expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool
proc compareExchange(ref expected: T, desired: T, param success:memoryOrder, param failure:memoryOrder): bool

/* Matches C/C++ compare_exchange_weak */
proc compareExchangeWeak(ref expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool
proc compareExchangeWeak(ref expected: T, desired: T, param success:memoryOrder, param failure:memoryOrder): bool

(note that I'm proposing we don't have "strong" in the name for compareExchange. That matches rust and is discussed in #13837. I'm open to having a compareExchangeStrong alias like we do today, but it feels like a needless duplicate to me. I'd also be open to only having compareExchangeStrong, but I have a slight preference for dropping the Strong)

[ronawho]

And on the off chance he's still following us, I'd love to get @dmk42's input here now that the proposal is more fleshed out.

[LouisJenkinsCS]

I thought option 3 meant no switch for this release but deprecating for now.

[dmk42]

Hi. I still see these discussions when I'm mentioned.

I'm less concerned about the mechanism of migration than with the fact that the migration eventually happens. The machine instructions do change the expected value, so passing that behavior through to the user will save clock cycles by not having to reload the new expected value again in user code.

I am happy with the direction in which this conversation is converging.

[ronawho]

I thought option 3 meant no switch for this release but deprecating for now.

I think that matches what I said. When I said Once everything settles for either proposal 2.5 or 3, I think we'd have... -- I'm talking about the final API after deprecating this release and updating next release (to give a sense of where we'd end up after everything is said and done.)

[ronawho]

Here's my current branch that would follow option 3 (deprecate compareExchange in favor of compareAndSwap for this release) -- master...ronawho:deprecate-compare_exchange

[ronawho]

@LouisJenkinsCS I made the minimum required changes to AtomicObjects in that branch. Do you think it makes sense to change the AtomicObjects API too?

[LouisJenkinsCS]

That's not a bad idea, I like the idea of making AtomicObject consistent with the standard atomics API.

[cassella]

Do you want to introduce functions with the new behavior this release, so people can start developing against them, with some namespace work to allow opting in?

I can imagine either giving them new names (compareExchangeX) so that in that future release people can just change the name in their code; or putting them in a temporary module with the correct names, something like python's from future import ....

use Atomics_future only compareExchange;

Then in that future release, they can just drop those use lines. (Assuming they can have a use like that introduce symbols that will be used in preference to the internal module's.) Though this may be more error prone due to transitive use causing the new symbol to appear in a module not expecting it, or the user not noticing that they'd forgotten the use in one of many files.

[ronawho]

That's more in line with Michael's option 2.5 (#13836 (comment)). My current plan is to go with option 3 though (deprecate this release, change next release.)

Adding the prototype functionality now might be nice, but there is a lot of implementation work for the ~1 day left before feature freeze. Delaying also gives us time to make sure we're happy with what versions of the compareExchange interface we present. We're not losing any functionality this release, so I don't think there is a big rush to try and add opt-in versions.

[cassella]

Ah, sorry. With only 1 day left before feature freeze, I didn't have time to read all the comments. :-P

[bradcray]

I like the 2.5 concept and the potential value of letting people work with the new interface, but then it occurred to me that nobody has ever asked us for the by-ref interface (that I can recall), so making them wait another release isn't likely to make them unhappy (i.e., if they've been happy with the current interface, they will probably continue to be happy with the compareAndSwap()). Then I didn't feel as bad about going with 3. (Elliot also reminded me of the number of runtime implementations of the atomics interface that would need to be fleshed out and tested).

[ronawho]

We now have compareAndSwap with the old behavior, and compareExchange that matches the C/C++ interface (with the exception that we call it compareExchange instead of compareExchangeStrong). So we have:

proc compareAndSwap(expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool

/* Matches C/C++ compare_exchange_strong */
proc compareExchange(ref expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool
proc compareExchange(ref expected: T, desired: T, param success:memoryOrder, param failure:memoryOrder): bool

/* Matches C/C++ compare_exchange_weak */
proc compareExchangeWeak(ref expected: T, desired: T, param order:memoryOrder = memoryOrder.seqCst): bool
proc compareExchangeWeak(ref expected: T, desired: T, param success:memoryOrder, param failure:memoryOrder): bool