Hi Igor,

It looks like I owe you an apology for (incorrectly) claiming your atomic swap (ASWP) was weaker than atomic compare and swap (CAS).

I went back to Herlihy's original 1991 paper[A] where he analyzed the various operations, and there are two types of swap considered.  I'll use " "global" to mean "visible to all threads", and "local" to mean "visible to only a single thread".  The first type of swap, where one var is global and one is local is the weak one.  The second type of swap, where both vars are global is as strong as CAS.

So, my bad - I hadn't remembered enough of the details of the paper, just the vague notion that "swap was bad and cas was good" :(.

However, I still think that the best operation to add to Squeak is CAS, for two reasons:

1) the heart of the bytecode can be the actual HW CAS instruction, so that the thread-safety of the bytecode does not depend on any other property of the VM such as scheduling conventions or block implementation strategy.  Most HW architectures today have CAS, I don't know of any with ASWP.  I guess ASWP has to have two main-memory locks while CAS only needs one, so the HW folks went with the one that looked easier :).

2) the "band wagon effect" I mentioned in another post has meant that most published algorithms are based on CAS, and wait-free or lock-free algorithms are very, very, very, difficult to get right[B], so if we jump on the band wagon as well, we are likely to save ourselves a lot of work and possibly some grief by being able to make use of the largest collection of known-good algorithms.

[A] "Wait-Free Synchronization" by Maurice Herlihy, in ACM Transactions on Programming Languages and Systems, Vol. 11, No. 1, January 1991, pages 124-149.

[B] This difficulty is the "real" conclusion to be drawn from the paper I mentioned earlier in this thread about the flaw in the double ended queue algorithm.  The paper in question is:
"DCAS is not a Silver Bullet for Nonblocking Algorithm Design" by Simon Doherty, David L.Detlefs, Lindsay Groves, Christine H. Flood, Victor Luchangco, Paul A. Martin, Mark Moir, Nir Shavit, and Guy L. Steel Jr., in
SPAA 2004, June 27-30, 2004, Barcelona, Spain.
In this paper they actually resorted to using a program verification system called PVS to make CERTAIN that their corrected algorithm is good.

On 2010-Oct-13, at 12:17, Igor Stasenko wrote:

>>> [snip]

>>> I'm not arguing about userfulness of CAS.
>>> As i said, if you think its cool to have as well, lets think how to
>>> add it as well.
>>> But i'm against 'lets add CAS instead of atomic swap'.
>> 
>> Ah.  Well, I'm afraid I am arguing against atomic swap, because it is just too weak to be really useful.  Yes, it does booleans, but that's about all.  I've been working on multi-threaded C code for about 5 years now, and the single most important thing I've learned is that lock free multi-threaded algorithms are not nearly as simple as they look at first.  The classic example is an actual published paper on a lock-free double ended queue that contained a flaw where the last element could be popped from both ends at once by two different threads.  The paper was peer-reviewed, both in it's original conference version and in its later journal version, and the flaw wasn't discovered until after the journal version was published.
> 
> Okay, i must confess, that atomic swap seems inferior to CAS.
> So, lets stick with CAS.
> 
> Thanks, Tom for providing arguments and proving your point.
> 
> -- 
> Best regards,
> Igor Stasenko AKA sig.

--
Tom Rushworth