<br><br><div class="gmail_quote">On Wed, Oct 13, 2010 at 11:37 AM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5">On 13 October 2010 21:06, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> wrote:<br>
><br>
><br>
> On Wed, Oct 13, 2010 at 9:41 AM, Tom Rushworth <<a href="mailto:tom_rushworth@mac.com">tom_rushworth@mac.com</a>><br>
> wrote:<br>
>><br>
>> Hi Igor, Eliot,<br>
>><br>
>> Eliot, I'm not sure I understood your comment:<br>
>><br>
>> On 2010-Oct-13, at 08:55, Eliot Miranda wrote:<br>
>><br>
>> > Right. And because Smalltak can't reify variables and CAS is an<br>
>> > operation on a variable CAS can't be implemented as a primitive on<br>
>> > variables. There's no way to express "pass a variable to a primitive",<br>
>> > only "pass an expression (which may be the value of a variable)" to a<br>
>> > primitive". One could do it with a primitive on an object, e.g.<br>
>> > thisContext at: tempIndex compareWith: match andSetTo: expr, or anObject<br>
>> > instVarAt: varIndex compareWith: match andSetTo: expr but that's soooo<br>
>> > ugly. Hence I think it is better done using a special assignment<br>
>> > operator.<br>
><br>
> I mean one can't write<br>
> | t |<br>
> self compare: t andSwap: expr<br>
> because in the above the rvalue of t is passed, not it's lvalue, and cas<br>
> needs to operate on an lvalue (rvalue == read value, or value of a variable;<br>
> lvalue = location value, or address of a variable). Clearly cas needs to<br>
> apply to a variable, not the value in the variable. The variable's value is<br>
> compared and the variable is set to a new value if it matches. Look at<br>
> Igor's example and you'll see his primitive on Arrays passes an lvalue since<br>
> the primitive takes the index of an array element.<br>
> e.g. if you implemented CAS in C using functions instead of macros you'd<br>
> know that you couldn't do it with int cas(int var, int match, int new) but<br>
> you'd know that you can do it with int cas(int *var, int match, int new) and<br>
> ... int v; ... cas(&v, match, new)<br>
><br>
>><br>
>> Doesn't this apply to Igor's proposed atomic swap as well? The target in<br>
>> Igor's example was a variable "locked" which was clearly meant to be visible<br>
>> to other threads.<br>
><br>
> Yes. First time I read Igor's post I on;y saw the initial<br>
> "| var1 var2 temp |<br>
> temp := var1.<br>
> var1 := var2.<br>
> var2 := temp."<br>
> which I rejected and didn't read further. Now I see the :=:. I don't like<br>
> this because it doesn't map as nicely to CAS which I like using. I like the<br>
> boolean result one gets fro CAS that says the assignment either happened or<br>
> it didn't. Atomic swap is more low-level. I then have to inspect the value<br>
> the variable used to have and undo the swap if it wasn't what was expected.<br>
> So<br>
> | var |<br>
> var ?= expr : match<br>
> is equivalent to<br>
> [| var scratch |<br>
> scratch := expr.<br>
> var :=: scratch.<br>
> scratch == match<br>
> ifTrue: [true]<br>
> ifFalse: [var :=: scratch. false]] valueUninterruptibly<br>
> Hence I think :=: is too low-level.<br>
><br>
<br>
</div></div>well, once you start using valueUninterruptibly, there is no much<br>
reason to use/introduce atomic swap nor cas :)<br></blockquote><div><br></div><div>Right :)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
moreover, i see no trivial way to implement CAS using atomic swap,<br>
while reverse is trivial.<br></blockquote><div><br></div><div>Is it, or does it also rely on uninterruptbility? Is this right?</div><div><br></div><div> v1 :=: v2</div><div><br></div><div>is equivalent to</div><div><br>
</div><div> [ | scratch |</div><div> scratch := v1.</div><div> v1 ?= v2 : scratch] whileFalse.</div><div> v2 := scratch.</div><div><br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
>From this point of view, CAS is better.<br>
<div class="im"><br>
>><br>
>> If that's the case, then they both need to be implemented with a special<br>
>> assignment operator, and Igor and I can get back to arguing the merits of<br>
>> the atomic swap versus the atomic compare and swap :). If not, then Igor's<br>
>> swap has a clear advantage and I guess you can both ignore the rest of this<br>
>> email...<br>
><br>
> Um, mine /does/ use a special assignment operator, "?= :" :)<br>
><br>
<br>
</div>var ?= match : expression<br>
<br>
could mean a lot of hacking in compiler. how about:<br>
<br>
var ?= { match . expression }<br>
<br>
so, you just need to introduce a new binary operator ?= "CAS<br>
assignment" or "conditional assignment"<br>
which is much simpler to hack comparing to trinary one.<br></blockquote><div><br></div><div>That's a good suggestion, bit let's see. Personally I find var ?= { match . expression } ok but a little flowery :)</div>
<div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
And you can also force compiler to expect only '{' after ?=, so no<br>
<br>
var ?= foo<br>
var ?= #( foo )<br>
var ?= self bar<br>
<br>
will be allowed.<br></blockquote><div><br></div><div>But ?= : is no more difficult than parsing expressions within keywords. I guess it'll look something like</div><div><br></div><div> conditionalAssignment: varNode</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>" var '?=' expression ':' match => ConditionalAssignmentNode."</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>| loc start valueNode |</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>(loc := varNode assignmentCheck: encoder at: prevMark + requestorOffset) >= 0 ifTrue:</div><div><span class="Apple-tab-span" style="white-space: pre; "> </span><span class="Apple-tab-span" style="white-space: pre; "> </span>[^self notify: 'Cannot store into' at: loc].</div>
<div><span class="Apple-tab-span" style="white-space: pre; "></span></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>start := self startOfNextToken.</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>self advance.</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>self expression ifFalse: [^self expected: 'Expression'].</div><div><span class="Apple-tab-span" style="white-space: pre; "> </span>newValueNode := parseNode.</div>
<div><span class="Apple-tab-span" style="white-space: pre; "> </span>(self match: #colon) ifFalse: [^self expected: 'colon'].</div><div><span class="Apple-tab-span" style="white-space: pre; "> </span>self advance.</div>
<div><span class="Apple-tab-span" style="white-space: pre; "> </span>self expression ifFalse: [^self expected: 'Expression'].</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>parseNode := ConditionAssignmentNode new</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>variable: varNode</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>value: valueNode</div><span class="Apple-tab-span" style="white-space: pre; "> </span>match: valueNode<div>
<span class="Apple-tab-span" style="white-space:pre"> </span>from: encoder</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>sourceRange: (start to: self endOfLastToken).</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>varNode nowHasDef.</div>
<div><span class="Apple-tab-span" style="white-space:pre"> </span>^true</div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5"><br>
<br>
>><br>
>> On 2010-Oct-13, at 08:33, Igor Stasenko wrote:<br>
>><br>
>> > On 13 October 2010 18:07, Tom Rushworth <<a href="mailto:tom_rushworth@mac.com">tom_rushworth@mac.com</a>> wrote:<br>
>> >> Hi all,<br>
>> >><br>
>> >> Take a look through the literature for the "strength" of the various<br>
>> >> types of atomic operations with respect to doing various synchronization<br>
>> >> tasks. CAS is "universal" in the sense that it can simulate all of the<br>
>> >> others. (The simulation is wretched, O(N**3), so it isn't practical,<br>
>> >> but...)<br>
>> >> I doubt that your atomic swap is as strong.<br>
>> ><br>
>> > Who said i gonna use it for synchronizations tasks?<br>
>> > We got a plenty of other stuff in smalltalk for synchronization.<br>
>><br>
>> I'm using "synchronization" in the sense of safe access to data in a<br>
>> multi-threaded context. There is no point at all to atomic ops unless you<br>
>> are doing that kind of "synchronization". In particular, your example was<br>
>> for implementing a lock, which I took to be a mutex style lock from looking<br>
>> at your code. Your example is in fact implementing a CAS spinloop for a<br>
>> boolean value. My counter example just used CAS explicitly :). You can use<br>
>> an unconditional swap for boolean values because there are only two possible<br>
>> values, so that setting the 'locked' variable to true unconditionally<br>
>> doesn't hurt anything since either it was already true and you didn't change<br>
>> anything visible to another thread, or it was the desired previous value<br>
>> (false) and you did change things visible to another thread is a planned,<br>
>> predictable way. If the variable in question was a pointer this would not<br>
>> be a safe operation, because you have no way to predict what the value of<br>
>> temp should be.<br>
>> ><br>
>> >><br>
>> >> Pretty well every current HW architecture actually has the CAS<br>
>> >> instruction (or some minor variation) implemented as a single instruction,<br>
>> >> so making it a primitive should be relatively easy. It seems a terrible<br>
>> >> waste to pick a weak synchronization primitive when a much better one could<br>
>> >> be had for very little more work.<br>
>> ><br>
>> > I feel that you are mixing hardware and language-side atomicity.<br>
>> > I don't care about hardware , i care that at language side i have a<br>
>> > simple atomic operation, which can't be interrupted by scheduler.<br>
>> > Hardware CAS is completely irrelevant to this, since VM can support<br>
>> > atomicity for language side without any specific requirements from the<br>
>> > hardware it runs on.<br>
>> ><br>
>> ><br>
>> >><br>
>> >> On 2010-Oct-12, at 12:04, Igor Stasenko wrote:<br>
>> >><br>
>> >>> CAS? Perhaps. If you wish to add it too, no problem.<br>
>> >>><br>
>> >>> I want at minimum swap, because with it i can easily implement<br>
>> >>> lock-free waiting:<br>
>> >>><br>
>> >>> [ | temp |<br>
>> >>> [ locked ] whileTrue.<br>
>> >>> temp := true.<br>
>> >>> locked :=: temp.<br>
>> >>> temp<br>
>> >>> ] whileTrue.<br>
>> >><br>
>> >> I think this is simpler (using Eliot's notation):<br>
>> >><br>
>> >> [locked ?:= true : false] whileFalse.<br>
>> >><br>
>> >> ... locked here ...<br>
>> >><br>
>> >> locked := false.<br>
>> >><br>
>> >> No temp needed, single block. well understood atomic op :).<br>
>> ><br>
>> > Yeah? Then try and implement a unconditional atomic swap using CAS.<br>
>><br>
>> I'll look up the paper in a short while, but for now, how about:<br>
>><br>
>> [ | oldVal | oldVal := var. var ?:= newVal : oldVal ] whileFalse.<br>
>><br>
>> Yes, this makes the retry loop explicit, but the retry loop exists in<br>
>> _any_ atomic op at some level. It may be buried in the HW where the<br>
>> microcode does the retry if there is memory cache line contention or some<br>
>> such but it is always there. "Atomic" implies blocking other threads, so<br>
>> that the other (blocked) threads have to retry. In the case of the atomic<br>
>> op being a VM level primitive the retry loop is implicit in the scheduler,<br>
>> in the sense that the scheduler cannot schedule other threads for the<br>
>> duration of the primitive.<br>
>> ><br>
>> > Again, who said, that i going to use atomic swap for loops like above?<br>
>><br>
>> Um, your example said it? :) Sorry if I misunderstood, but email doesn't<br>
>> give much context, and the loop you gave was the only context I had, so I<br>
>> assumed that was what you wanted to do.<br>
>><br>
>> > I simply need a guarantee from VM , that swap operation will be<br>
>> > atomic. No less, no more.<br>
>> > Compare-And-Swap and swap is different operations.<br>
>><br>
>> I guess that depends on how you look at it. I see CAS as a simple<br>
>> generalization of atomic swap that is _much_ more useful for implementing<br>
>> many different kinds of safe multi-threaded data access. Unconditional swap<br>
>> works safely for booleans, but if you use it for something more complicated,<br>
>> like numbers, you end up in all sorts of complications. The unconditional<br>
>> swap ends up "leaking" information into the variable that is visible to<br>
>> other threads in a way that is very difficult to cope with for the other<br>
>> threads. Try doing a thread safe numeric increment with unconditional<br>
>> swap....<br>
><br>
> +1. I've used CAS quite a bit in Cog (e.g. reimplementing<br>
> signalExternalSemaphore) ad it's concise and easy-to-use.<br>
><br>
<br>
<br>
<br>
</div></div>--<br>
<div><div></div><div class="h5">Best regards,<br>
Igor Stasenko AKA sig.<br>
<br>
</div></div></blockquote></div><br>