1

In java 17, AtomicReference has the compareAndExchange method which is like compareAndSet, but instead of returning a boolean, it returns the value right before the atomic action. I need that to implement a custom concurrent structure.

Due to limitations on the project, I have to use only Java 8 features. Some digging revealed VarHandle which has compareAndExchange. However, VarHandle requires Java 9.

Therefore, it seems that I have to implement the compareAndExchange myself. But how to do so efficiently with the existing methods? (And what about the compareAndExchangeWeak version?)

(I cannot rely on any third-party libraries, BTW)

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
李浩穎
  • 47
  • 6
  • 1
    Why are you restricted to Java 8? Given Java 17 is the current LTS, you or your company should really consider upgrading. – Mark Rotteveel Aug 14 '22 at 06:58
  • It's because of... Well. Game modding. (Or, Minecraft modding more precisely.) Supporting many versions of MC, even very old but popular one, is important still. – 李浩穎 Aug 14 '22 at 07:42
  • 1
    `for(;;) { V current = ref.get(); if(current != expected || ref.compareAndSet(current, newValue)) return current; }` – Holger Aug 22 '22 at 11:53

1 Answers1

5

This is close but has an observable difference in at least one case:

V witness = ref.get();
if (ref.compareAndSet(oldValue, newValue)) {
    return oldValue;
} else {
    return witness;
}

If witness != oldValue, the witness value is not necessarily the correct value of the reference at the instant we do the compare-and-set.

However, it is not clear whether that value would be useful anyway ... so "close but not exactly right" may be sufficient. With a 100% correct compareAndExchange, the returned witness doesn't tell the caller what the state of the reference is now. Another thread could have changed the reference by the time that caller tries to use the returned value.

For example, this could return a value that matches oldValue without having done the store. e.g. if multiple threads run this simultaneously with the same oldValue when ref has that value, they can all loads witness = oldValue, but only one will succeed the CAS. So you can't safely use the return value to determine whether your CAS "won the race" to update ref. You need to keep to bool return value from compareAndSet for that.

I don't think it is possible to do an exact emulation of compareAndExchange without using locks ... which would largely defeat the purpose of using an AtomicReference.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • I don't think this has the correct effects, but I'm not sure. – Mark Rotteveel Aug 14 '22 at 07:10
  • I **know** it doesn't have the correct effect. That's the point. – Stephen C Aug 14 '22 at 07:11
  • @MarkRotteveel: But is there ever a case where we can distinguish this from a failed CAS? Java doesn't allow memory ordering weaker than sequential consistency, so I think this is indistinguishable from `ref.get()` being the load part of a failed CAS. Whether a thread has done one vs. two loads isn't a directly-observable side effect. – Peter Cordes Aug 14 '22 at 07:16
  • I think this works, and would only be really worried about it if there was any code between `ref.get()` and the CAS attempt, and/or weaker memory orders were possible. Although a failed CAS is potentially just a pure load, not an RMW, on some machines, so maybe even weaker memory orders would be fine for a hypothetical C++ version of this, as long as `.get()` and the CAS use the same memory order strength for the failure side, and the success load side. – Peter Cordes Aug 14 '22 at 07:21
  • @PeterCordes - It could be "observable sometimes" rather than "guaranteed observable". But my thought is that it is hard to see how it matters that you return the wrong witness following a failed CAS. It would be indistinguishable from another thread updating the reference immediately afterwards. – Stephen C Aug 14 '22 at 07:23
  • (ISO C++11 compare_exchange_weak has always updated `oldValue` by reference, like the GNU C `__atomic`, as well as returning a bool for success/fail. The old GNU C [`__sync_bool_compare_and_swap`](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fsync-Builtins.html) existed, but so did `__sync_val_compare_and_swap` that just returned the old value, not the compare success. So you could manually compare after to also see if the compare succeeded, without needing to emulate this way. And didn't take a memory-order parameter. So my C++ hypothetical is just hypothetical.) – Peter Cordes Aug 14 '22 at 07:23
  • I wonder if a loop with get witness, compare witness with expected, return witness if unequal, otherwise compare-and-set, return witness if true end loop would be better, or if that just makes it perform badly with the same end result. – Mark Rotteveel Aug 14 '22 at 07:27
  • @MarkRotteveel - Tried that thought. The problem is you get into an infinite loop. (If you don't care about `oldValue`, you can replace this with `getAndUpdate(() -> newValue())` ... but the semantics are different to `compareAndExchange`.) – Stephen C Aug 14 '22 at 07:29
  • I think I'm not familiar enough with Java memory-model terminology. Does "observable sometimes" just mean you were racing with another store and might or might not have seen it? I think this emulation is still equivalent (except perhaps performance) to a single CAS attempt at either the moment the `get.ref()` takes a value (on later CAS failure), or at the moment the CAS itself executes (on success). Since those two operations are back to back in one thread, I don't think it can ever matter which of the two loads (separate or part of CAS) was the one that counted. (@MarkRotteveel). – Peter Cordes Aug 14 '22 at 07:29
  • By "observable sometimes" I meant ... "not guaranteed by *happens before* relationships, so behavior depends on ... things". – Stephen C Aug 14 '22 at 07:33
  • Ok yeah, that's what I was already assuming, that it was racing with other writers, otherwise it would be trivially correct. I could certainly be missing something, but my intuition says this is fine. Yes, you could see a `witness` that matched `oldValue` and then have the CAS fail, but in that case it's as if the earlier load never happened. Except **this could potentially return `oldValue` *without* having done a store of `newValue`**. So there we go, that's a potentially observable difference. – Peter Cordes Aug 14 '22 at 07:36
  • Yup. I think it is potentially observable too, hence my "close ... but not exactly right" characterization of the "solution". – Stephen C Aug 14 '22 at 07:38
  • Is there any possible noticable difference regarding ABA problem? I currently cannot think of any but I'm worried that I'm missing something there. – 李浩穎 Aug 14 '22 at 07:39
  • Potentially, yes. But please update the question to provide a concrete example where you would be using (real) `compareAndExchange` to address an ABA problem. Then we can be sure we know what you mean. – Stephen C Aug 14 '22 at 07:41
  • @李浩穎 : I just edited this answer to explain in more detail the one case I've thought of where the observable results would be different. There may be other cases, too. However, even `compareAndExchange` doesn't avoid ABA problems in general, but I don't *think* this emulation would make ABA problems worse. If you're using a 2-element struct with a counter avoid ABA problems, or using some bits of a wider integer as a sequence counter for the same reason, this doesn't break that. – Peter Cordes Aug 14 '22 at 07:46
  • Thanks. And I guess it now functions like `CompareAndExchangeWeak` if I also pass in a mutable boolean. And I think with a slight modification, (by retrying if weak fails yet return value is the same as the expected value), it could be a full (and a bit slow) `compareAndExchange`? – 李浩穎 Aug 14 '22 at 07:59
  • @李浩穎: `compareAndSet` doesn't fail *spuriously*. If it fails, there definitely was a value other than `oldValue` in `ref` at the time it executed. You just don't know what it is. Some algorithm might want to retry until success or `witness != oldValue`, but most use-cases don't need that. It would be a bad idea to introduce retries where not necessary, amplifying contention in cases where it already exists. – Peter Cordes Aug 14 '22 at 09:05
  • Though that does still mean if I need exact (or as best as it could in a *as if* way) c++'s `compareAndExchange`, I would still need the retires right? And there isn't any other better methods right? – 李浩穎 Aug 14 '22 at 09:22
  • 1
    And in your case where the CAS fails, and yet the witness value is the same as expected, then by the 'as if' rule, I could say that the value was changed before the operation, and said `CompareAndExchangeWeak` operation just fail spuriously. Is this still correct? – 李浩穎 Aug 14 '22 at 09:25
  • Wait... I flipped that around. I meant as if the value was changed after the operation, which said operation just fails spuriously. – 李浩穎 Aug 14 '22 at 09:40
  • @李浩穎 : Were you still replying to me? You didn't @ notify me but I just randomly happened to look at this thread again. Yeah, treating it as a `compare_exchange_weak` that could spuriously fail would be one way to account for the possibility of `witness == oldValue` but still failure. That is possible with a C++ CAS_weak – Peter Cordes Aug 14 '22 at 23:48