[squeak-dev] Re: [Pharo-project] How about atomic value-swap bytecode?

Eliot Miranda eliot.miranda at gmail.com
Wed Oct 13 18:56:18 UTC 2010


On Wed, Oct 13, 2010 at 11:37 AM, Igor Stasenko <siguctua at gmail.com> wrote:

> 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 :)
>

Right :)


>
> moreover, i see no trivial way to implement CAS using atomic swap,
> while reverse is trivial.
>

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.



>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.
>

That's a good suggestion, bit let's see.  Personally I find  var ?= { match
. expression } ok but a little flowery :)


And you can also force compiler to expect only '{' after ?=, so no
>
> var ?= foo
> var ?= #( foo )
> var ?= self bar
>
> will be allowed.
>

But ?= : is no more difficult than parsing expressions within keywords.  I
guess it'll look something like

    conditionalAssignment: varNode
" var '?=' expression ':' match => ConditionalAssignmentNode."
| loc start valueNode |
(loc := varNode assignmentCheck: encoder at: prevMark + requestorOffset) >=
0 ifTrue:
 [^self notify: 'Cannot store into' at: loc].
start := self startOfNextToken.
self advance.
self expression ifFalse: [^self expected: 'Expression'].
newValueNode := parseNode.
(self match: #colon) ifFalse: [^self expected: 'colon'].
self advance.
self expression ifFalse: [^self expected: 'Expression'].
parseNode := ConditionAssignmentNode new
variable: varNode
value: valueNode
match: valueNode
from: encoder
sourceRange: (start to: self endOfLastToken).
varNode nowHasDef.
^true


>
> >>
> >> 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.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20101013/01b4cac2/attachment.htm


More information about the Squeak-dev mailing list