On 13 October 2010 21:06, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>
>
> On Wed, Oct 13, 2010 at 9:41 AM, Tom Rushworth <tom_rushworth at mac.com>
> wrote:
>>
>> Hi Igor, Eliot,
>>
>> Eliot, I'm not sure I understood your comment:
>>
>> On 2010-Oct-13, at 08:55, Eliot Miranda wrote:
>>
>> > Right.  And because Smalltak can't reify variables and CAS is an
>> > operation on a variable CAS can't be implemented as a primitive on
>> > variables.  There's no way to express "pass a variable to a primitive",
>> > only "pass an expression (which may be the value of a variable)" to a
>> > primitive".  One could do it with a primitive on an object, e.g.
>> > thisContext at: tempIndex compareWith: match andSetTo: expr, or anObject
>> > instVarAt: varIndex compareWith: match andSetTo: expr but that's soooo
>> > ugly.  Hence I think it is better done using a special assignment
>> > operator.
>
> I mean one can't write
>     | t |
>     self compare: t andSwap: expr
> because in the above the rvalue of t is passed, not it's lvalue, and cas
> needs to operate on an lvalue (rvalue == read value, or value of a variable;
> lvalue = location value, or address of a variable).  Clearly cas needs to
> apply to a variable, not the value in the variable.  The variable's value is
> compared and the variable is set to a new value if it matches.  Look at
> Igor's example and you'll see his primitive on Arrays passes an lvalue since
> the primitive takes the index of an array element.
> e.g. if you implemented CAS in C using functions instead of macros you'd
> know that you couldn't do it with int cas(int var, int match, int new) but
> you'd know that you can do it with int cas(int *var, int match, int new) and
> ... int v; ... cas(&v, match, new)
>
>>
>> Doesn't this apply to Igor's proposed atomic swap as well?  The target in
>> Igor's example was a variable "locked" which was clearly meant to be visible
>> to other threads.
>
> Yes.  First time I read Igor's post I on;y saw the initial
> "| var1 var2 temp |
> temp := var1.
> var1 := var2.
> var2 := temp."
> which I rejected and didn't read further.  Now I see the :=:.  I don't like
> this because it doesn't map as nicely to CAS which I like using.  I like the
> boolean result one gets fro CAS that says the assignment either happened or
> it didn't.  Atomic swap is more low-level.  I then have to inspect the value
> the variable used to have and undo the swap if it wasn't what was expected.
>  So
>         | var |
>         var ?= expr : match
> is equivalent to
>         [| var scratch |
>         scratch := expr.
>         var :=: scratch.
>         scratch == match
>             ifTrue: [true]
>             ifFalse: [var :=: scratch. false]] valueUninterruptibly
> Hence I think :=: is too low-level.
>

well, once you start using valueUninterruptibly, there is no much
reason to use/introduce atomic swap nor cas :)

moreover, i see no trivial way to implement CAS using atomic swap,
while reverse is trivial.
>From this point of view, CAS is better.

>>
>> If that's the case, then they both need to be implemented with a special
>> assignment operator, and Igor and I can get back to arguing the merits of
>> the atomic swap versus the atomic compare and swap :).  If not, then Igor's
>> swap has a clear advantage and I guess you can both ignore the rest of this
>> email...
>
> Um, mine /does/ use a special assignment operator, "?= :" :)
>

var ?= match : expression

could mean a lot of hacking in compiler. how about:

var ?= { match . expression }

so, you just need to introduce a new binary operator ?= "CAS
assignment" or "conditional assignment"
which is much simpler to hack comparing to trinary one.

And you can also force compiler to expect only '{' after ?=, so no

var ?= foo
var ?= #( foo )
var ?= self bar

will be allowed.


>>
>> On 2010-Oct-13, at 08:33, Igor Stasenko wrote:
>>
>> > On 13 October 2010 18:07, Tom Rushworth <tom_rushworth at mac.com> wrote:
>> >> Hi all,
>> >>
>> >> Take a look through the literature for the "strength" of the various
>> >> types of atomic operations with respect to doing various synchronization
>> >> tasks.  CAS is "universal" in the sense that it can simulate all of the
>> >> others.  (The simulation is wretched, O(N**3), so it isn't practical,
>> >> but...)
>> >> I doubt that your atomic swap is as strong.
>> >
>> > Who said i gonna use it for synchronizations tasks?
>> > We got a plenty of other stuff in smalltalk for synchronization.
>>
>> I'm using "synchronization" in the sense of safe access to data in a
>> multi-threaded context.  There is no point at all to atomic ops unless you
>> are doing that kind of "synchronization".  In particular, your example was
>> for implementing a lock, which I took to be a mutex style lock from looking
>> at your code.  Your example is in fact implementing a CAS spinloop for a
>> boolean value.  My counter example just used CAS explicitly :).  You can use
>> an unconditional swap for boolean values because there are only two possible
>> values, so that setting the 'locked' variable to true unconditionally
>> doesn't hurt anything since either it was already true and you didn't change
>> anything visible to another thread, or it was the desired previous value
>> (false) and you did  change things visible to another thread is a planned,
>> predictable way.  If the variable in question was a pointer this would not
>> be a safe operation, because you have no way to predict what the value of
>> temp should be.
>> >
>> >>
>> >> Pretty well every current HW architecture actually has the CAS
>> >> instruction (or some minor variation) implemented as a single instruction,
>> >> so making it a primitive should be relatively easy. It seems a terrible
>> >> waste to pick a weak synchronization primitive when a much better one could
>> >> be had for very little more work.
>> >
>> > I feel that you are mixing hardware and language-side atomicity.
>> > I don't care about hardware , i care that at language side i have a
>> > simple atomic operation, which can't be interrupted by scheduler.
>> > Hardware CAS is completely irrelevant to this, since VM can support
>> > atomicity for language side without any specific requirements from the
>> > hardware it runs on.
>> >
>> >
>> >>
>> >> On 2010-Oct-12, at 12:04, Igor Stasenko wrote:
>> >>
>> >>> CAS? Perhaps. If you wish to add it too, no problem.
>> >>>
>> >>> I want at minimum swap, because with it i can easily implement
>> >>> lock-free waiting:
>> >>>
>> >>> [ | temp |
>> >>>  [ locked ] whileTrue.
>> >>>    temp := true.
>> >>>    locked :=: temp.
>> >>>    temp
>> >>> ] whileTrue.
>> >>
>> >> I think this is simpler (using Eliot's notation):
>> >>
>> >>  [locked ?:= true : false] whileFalse.
>> >>
>> >>   ... locked here ...
>> >>
>> >>   locked := false.
>> >>
>> >> No temp needed, single block. well understood atomic op :).
>> >
>> > Yeah? Then try and implement a unconditional atomic swap using CAS.
>>
>> I'll look up the paper in a short while, but for now, how about:
>>
>>    [ | oldVal | oldVal := var. var ?:= newVal : oldVal ] whileFalse.
>>
>> Yes, this makes the retry loop explicit, but the retry loop exists in
>> _any_ atomic op at some level.  It may be buried in the HW where the
>> microcode does the retry if there is memory cache line contention or some
>> such but it is always there.  "Atomic" implies blocking other threads, so
>> that the other (blocked) threads have to retry.  In the case of the atomic
>> op being a VM level primitive the retry loop is implicit in the scheduler,
>> in the sense that the scheduler cannot schedule other threads for the
>> duration of the primitive.
>> >
>> > Again, who said, that i going to use atomic swap for loops like above?
>>
>> Um, your example said it? :)  Sorry if I misunderstood, but email doesn't
>> give much context, and the loop you gave was the only context I had, so I
>> assumed that was what you wanted to do.
>>
>> > I simply need a guarantee from VM , that swap operation will be
>> > atomic. No less, no more.
>> > Compare-And-Swap and swap is different operations.
>>
>> I guess that depends on how you look at it.  I see CAS as a simple
>> generalization of atomic swap that is _much_ more useful for implementing
>> many different kinds of safe multi-threaded data access.  Unconditional swap
>> works safely for booleans, but if you use it for something more complicated,
>> like numbers, you end up in all sorts of complications.  The unconditional
>> swap ends up "leaking" information into the variable that is visible to
>> other threads in a way that is very difficult to cope with for the other
>> threads.  Try doing a thread safe numeric increment with unconditional
>> swap....
>
> +1.  I've used CAS quite a bit in Cog (e.g. reimplementing
> signalExternalSemaphore) ad it's concise and easy-to-use.
>



-- 
Best regards,
Igor Stasenko AKA sig.