[jboss-dev] compareAndSet variation

[Andrew Dinn]

On 02/10/2010 03:40 PM, David M. Lloyd wrote:
 > This doesn't really make any sense - you're saying if the value is
 > different, return the delta and leave the value unchanged, but if the 
delta
 > was zero between the expect and update, then the value wouldn't need
 > changing anyway!  You can do that with just a read.
I agree the request is not clear but I think I understand what is being 
asked for.  Assuming this is a methof of AtomicLong which has a long 
field called 'value' what would make sense would be:

   int compareAndSet(long expected, long new)
   atomic {
     if value == expected {
       value = new;
       return 0;
     else
       return value - expected;
     endif
   }

or, equivalently, in a form which clarifies the motive for the request:

   int compareAndSet(long expected, long new)
   atomic {
     int result = value - expected;
     if (result == 0) {
       value = new
     endif
     return result;
}

In other words can the update be conditional on the outcome of a 
subtract returning zero while the operation returns the value of the 
subtract operation whether or not the update occurs? This makes clear 
the difference form a normal CAS


   boolean compareAndSet(long expected, long new)
   atomic {
     boolean result = (value != expected);
     if (!result) {
       value = new
     endif
     return result;
}

Well, you could always implement this using conventional locking (which 
you can already do anyway) but you could not implement it using either a 
conventional hardware CAS instruction or LOAD_LINK STORE_CONDITIONAL 
pair. These only output a true or false result. So, when they succeed 
you know what the result of the subtract would be (zero) but when they 
fail you don't have enough information to identify the result as it was 
at the point where the check failed. n.b. reading value before or after 
trying an update with the CAS/LOAD_L-STORE_C is no good as the value is 
volatile. For example, reading after the CAS failed risks returning zero 
if some other thread updates the value to expected between the CAS and 
the read without actually updating value to new.

Building hardware which returned a difference rather than a boolean 
would be quite simple to do but no one has -- and almost certainly for 
good reasons. Since the updated value is by definition volatile the 
result of the subtraction is probably of no more use to you than the 
boolean result. If it is zero it tells you the value was as you expected 
and your update succeeded. If it is non-zero then you would need some 
very clever scheme to be usefully employ the result.

For example, imagine every thread which used this operation employed a 
unique positive integer as a lock value with 0 used to mean that the 
location was not locked. Supplying 0 as the expected value when 
attempting a lock operation would allow a non-zero return value to 
identify the lock owner _at the time of the lock attempt_. That might be 
useful as a way of chasing round locking threads but its utility is 
mitigated by the fact that the lock owner could transfer ownership 
immediately after the lock attempt. One possibility might be, say, to 
use the return value to order the failed thread in some sort of wait 
queue associated with the locked location, but it's not clear to me how 
you could make that work effectively.

n.b. Apologies for mixing Tim Harris's Java atomic syntax with C addressing.

regards,


Andrew Dinn
-----------