On 2010-Oct-13, at 14:28, Igor Stasenko wrote:

> On 14 October 2010 00:07, Tom Rushworth <tom_rushworth at mac.com> wrote:
>> 
>> On 2010-Oct-13, at 12:58, Igor Stasenko wrote:
>> 
>>>> 
>>>> Is it, or does it also rely on uninterruptbility?  Is this right?
>>>>     v1 :=: v2
>>>> is equivalent to
>>>>     [ | scratch |
>>>>      scratch := v1.
>>>>      v1 ?= v2 : scratch] whileFalse.
>>>>      v2 := scratch.
>>>> 
>>> 
>>> Nope! Not in all cases.
>>> 
>>> If v1 and v2 having equal significance in algorithm, not just v1,
>>> then it won't work.
>>> I mean, if the above will be interrupted after leaving the loop but
>>> before you assign to v2 (v2 := scratch)
>>> and your code expects that not only v1 swapped correctly, but v2 as well,
>>> then you're in trouble.
>>> 
>>> Swap is symmetric, i.e. v1 :=: v2 should be semantically equal to v2 :=: v1.
>>> But its not achievable unless its also atomic.
>>> 
>>> So, i must confess (again), that CAS cannot serve as a complete
>>> replacement for atomic swap.
>> 
>> I hadn't thought about both v1 and v2 being "global" (in the sense that they are both visible to other threads).  For the sake of the discussion I'll use a little C syntax to the lvalue/rvalue distinction is clear.
>> 
>> CAS looks like: boolean CAS(int *var, int match, int newVal) // only one lvalue
>> 
>> ASWP looks like: void ASWP(int *var1, int *var2) // two lvalues !!
>> 
>> If the second lvalue is thread-local, you can simulate ASWP with CAS.  If it isn't you need to step up to DCAS (Double Compare And Swap - two simultaneous, non-adjacent CAS ops as one atomic op), which is a much rarer bird. (I'm not aware of any actual HW that supports it.)  Another option might be STM (software transactional memory (I think)), but that's not really common either.
>> 
>> So, given how rare DCAS is, I'd have to say it isn't something we should be doing in Squeak, which leads to the question of just how often you expect to have an algorithm using ASWP where both v1 and v2 are "global" ?  I've spent a couple of months over the last few years reading papers on lock free data structures and there are lots of papers using CAS, but none I remember for an atomic swap, so I still think CAS is a better thing to add to Squeak than ASWP.  If you can come up with good examples for algorithms that need both v1 and v2 global then you might have a good argument, but I know there are good examples for algorithms using CAS, so you sort of need to match them :).
> 
> I think you won't find any papers about ASWP, because all researchers
> thinking in a way:
> - okay, i have a CAS, now how i implement X using it. :)

So true.  There's a very strong "band wagon" effect :).

(I may be being too English idomatic here.  English has an idiom "jump on the band wagon" for joining the currently popular fad or movement, so the "band wagon effect" is what happens when all the researchers see someone with a good idea, or even just a really good paper :).)
> 
> Lets get back to my LIFO queue, its seems i found how to make it right
> using ASWP:
> 
> Populating:
> 
> | temp |
> temp := newItem := QueueItem new.
> newItem next: newItem. "note this"
OK, at this point newItem is a single item circular list.
> queueHead :=: newItem.
Now queueHead is a single item circular list, and newItem is the old queue.  The single item circular list is the "guard" for flushing.
??? What happens if another thread (or threads) does a "Populate" right here, before the "Flush" grabs it, and before this Populate completes?  You end up with two circular lists, and two old queues in two different thread instances of temp - do they get re-assembled in the right way and does Flush handle it correctly?
> temp next: newItem.
This breaks the circular list by appending the old queue.
> 
> 
> Flushing and processing the queue:
> 
> | oldHead |
> oldHead := nil.
> queueHead :=: oldHead.
Now oldHead is the queue and queueHead is nil.
> 
> [ oldHead notNil ] whileTrue: [
"spin while the queue is a single item circular list - i.e wait for the last line of the "Populating" code.
>  oldHead next == oldHead ifFalse: [
>    "process the queue item here"
>  oldHead := oldHead next. ]
> ]
> 
> in this way, a processing thread will loop with no-operation,
> until thread, who populating new item will finish its job, i.e. attach
> a rest of queue (or nil).

This looks better, but I still have doubts, see the "???" above.  We need to work out the details of n>1 "Populates" happening at the same time.
> 
>>> 
>> 
>> --
>> Tom Rushworth
>> 
>> 
>> 
>> 
>> 
> 
> 
> 
> -- 
> Best regards,
> Igor Stasenko AKA sig.
> 

--
Tom Rushworth