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

Igor Stasenko siguctua at gmail.com
Wed Oct 13 21:11:01 UTC 2010


On 13 October 2010 23:59, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>
>
> On Wed, Oct 13, 2010 at 12:58 PM, Igor Stasenko <siguctua at gmail.com> wrote:
>>
>> On 13 October 2010 21:56, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>> >
>> >
>> > 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.
>> >
>>
>> 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.
>>
>>
>> >
>> >> >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 :)
>> >
>>
>> Yes. But it looks more conformant to traditional ST syntax.  :)
>>
>> >> 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
>>
>> Okay, if you think its easy. No problem.
>> But i am a bit worrying about parsing & clearly reading following:
>>
>> boo ?= #foo:bar: : #baz: .
>>
>> colon seems not a good choice here.
>
> OK, how about
>     boo ?= #foo:bar: ? #baz
> ?
>

Err.. #? as well as #?= currently parsed as valid binary selector,
so
#foo:bar: ? #baz
can be treated as a valid binary message send expression.

In contrast,  :=:  leads to syntax error, which is good,
as well as
:=?

var :=: { match . expression }
var :=? { match . expression }

var :=? match :=: expression .


> The main problem we have now is finding space in the bytecode.  At least for
> me, the remaining bytecodes have all been taken by Newspeak (and I'm eager
> to get Newspeak running on Cog).  So my plan is new object representation,
> new bytecode set, then cas.

Always leave at least a single bytecode for future extensions.


-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list