How about atomic value-swap bytecode?
Locked
12
12
How about atomic value-swap bytecode?
 
|
Hello, i just thought, that it would be cool to have a special bytecode,
which guarantees atomicity for swapping values between two variables. To swap two values, you usually do: | var1 var2 temp | temp := var1. var1 := var2. var2 := temp. But since its non-atomic, a process can be interrupted and such operation is not thread-safe. In order to make it thread safe, you must add even more boilerplate: | var1 var2 temp | semaphore critical: [ temp := var1. var1 := var2. var2 := temp. ] So, i thought , if we could have a special bytecode, then we could write something like: | var1 var2 | var1 :=: var2. So, VM will guarantee that values of var1 and var2 will be swapped atomically, and completely thread-safe. var1 and var2 could be either temps or instance variables, but of course not arguments, since they are not assignable. One thing i don't like, that it will need to introduce a new syntax for atomic-value-swap operator - :=: Or, maybe just reserve a special keyword selector (which is recognized by compiler), so var1 __atomicSwapWith: var2 so it will look like a regular smalltalk syntax, except that its not a message send, but a low-level operation instead. -- Best regards, Igor Stasenko AKA sig. |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
On Tue, 12 Oct 2010, Igor Stasenko wrote:
> Hello, i just thought, that it would be cool to have a special bytecode, > which guarantees atomicity for swapping values between two variables. > > To swap two values, you usually do: > > | var1 var2 temp | > > temp := var1. > var1 := var2. > var2 := temp. > > But since its non-atomic, a process can be interrupted and such operation > is not thread-safe. > > In order to make it thread safe, you must add even more boilerplate: > > | var1 var2 temp | > > semaphore critical: [ > temp := var1. > var1 := var2. > var2 := temp. > ] An alternative solution: | a b | a := 1. b := 2. [ | tmp | tmp := a. a := b. b := tmp ] valueUnpreemptively Levente > > So, i thought , if we could have a special bytecode, then we could > write something like: > > | var1 var2 | > > var1 :=: var2. > > So, VM will guarantee that values of var1 and var2 will be swapped > atomically, and completely thread-safe. > > var1 and var2 could be either temps or instance variables, but of > course not arguments, since they are not assignable. > > One thing i don't like, that it will need to introduce a new syntax > for atomic-value-swap operator - :=: > > Or, maybe just reserve a special keyword selector (which is recognized > by compiler), so > > var1 __atomicSwapWith: var2 > > so it will look like a regular smalltalk syntax, except that its not a > message send, but a low-level operation instead. > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
On 12 October 2010 16:51, Levente Uzonyi <[hidden email]> wrote:
> On Tue, 12 Oct 2010, Igor Stasenko wrote: > >> Hello, i just thought, that it would be cool to have a special bytecode, >> which guarantees atomicity for swapping values between two variables. >> >> To swap two values, you usually do: >> >> | var1 var2 temp | >> >> temp := var1. >> var1 := var2. >> var2 := temp. >> >> But since its non-atomic, a process can be interrupted and such operation >> is not thread-safe. >> >> In order to make it thread safe, you must add even more boilerplate: >> >> | var1 var2 temp | >> >> semaphore critical: [ >> temp := var1. >> var1 := var2. >> var2 := temp. >> ] > > An alternative solution: > > | a b | > a := 1. > b := 2. > [ > | tmp | > tmp := a. > a := b. > b := tmp ] valueUnpreemptively > Yeah, another boilerplate under the hood, also highly dependent from scheduling nuances :) valueUnpreemptively "Evaluate the receiver (block), without the possibility of preemption by higher priority processes. Use this facility VERY sparingly!" "Think about using Block>>valueUninterruptably first, and think about using Semaphore>>critical: before that, and think about redesigning your application even before that! After you've done all that thinking, go right ahead and use it..." | activeProcess oldPriority result | activeProcess := Processor activeProcess. oldPriority := activeProcess priority. activeProcess priority: Processor highestPriority. result := self ensure: [activeProcess priority: oldPriority]. "Yield after restoring priority to give the preempted processes a chance to run" Processor yield. ^result > > Levente > -- Best regards, Igor Stasenko AKA sig. |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
If you're going for atomic swap as a primitive, why not go for Compare-And-Swap? That way all the various lock-free algorithms that use the CAS machine instruction will translate easily.
CAS(variable,oldValue,newValue) is an atomic operation which returns a boolean value (my ST syntax is rusty at the moment, too much Objective-C): (variable == oldValue) ifTrue: [variable := newValue. ^true]. " variable not the same as oldValue, no swap performed " ^false On 2010-Oct-12, at 06:58, Igor Stasenko wrote: > On 12 October 2010 16:51, Levente Uzonyi <[hidden email]> wrote: >> On Tue, 12 Oct 2010, Igor Stasenko wrote: >> >>> Hello, i just thought, that it would be cool to have a special bytecode, >>> which guarantees atomicity for swapping values between two variables. >>> >>> To swap two values, you usually do: >>> >>> | var1 var2 temp | >>> >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> >>> But since its non-atomic, a process can be interrupted and such operation >>> is not thread-safe. >>> >>> In order to make it thread safe, you must add even more boilerplate: >>> >>> | var1 var2 temp | >>> >>> semaphore critical: [ >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> ] >> >> An alternative solution: >> >> | a b | >> a := 1. >> b := 2. >> [ >> | tmp | >> tmp := a. >> a := b. >> b := tmp ] valueUnpreemptively >> > > Yeah, another boilerplate under the hood, also highly dependent from > scheduling nuances :) > > valueUnpreemptively > "Evaluate the receiver (block), without the possibility of preemption > by higher priority processes. Use this facility VERY sparingly!" > "Think about using Block>>valueUninterruptably first, and think about > using Semaphore>>critical: before that, and think about redesigning > your application even before that! > After you've done all that thinking, go right ahead and use it..." > | activeProcess oldPriority result | > activeProcess := Processor activeProcess. > oldPriority := activeProcess priority. > activeProcess priority: Processor highestPriority. > result := self ensure: [activeProcess priority: oldPriority]. > "Yield after restoring priority to give the preempted processes a > chance to run" > Processor yield. > ^result >> >> Levente >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > -- Tom Rushworth |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
On Tue, Oct 12, 2010 at 8:28 AM, Tom Rushworth <[hidden email]> wrote: If you're going for atomic swap as a primitive, why not go for Compare-And-Swap? That way all the various lock-free algorithms that use the CAS machine instruction will translate easily. +1. I want, e.g. (var ?== expr : match) evaluates to true and var == expr if var == prev before the statement, and false and var unchanged if var ~~ match
var ?= expr : match is more difficult to implement since = is not necessarily primitive. So one could write e.g. LinkedList subclass: #Semaphore
instanceVariableNames: 'signals locked' Semaphore>>signal [locked ?== true : false] whileFalse. self isEmpty ifTrue: [signals := signals + 1]
ifFalse: [self removeFirst resume]. locked := false
|
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
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. ... locked here ... locked := false. Proof: In the above, thread having chance to exit from waiting loop only if temp == false. There is no way how more than one waiting threads can leave this loop at same time, because 'locked' value is not copied over (assigned) but swapped (always with true). So, first who succeed to swap false <-> true will obtain a lock, others will unable to do so, and swap true<->true, and thus will keep waiting in the loop. On 12 October 2010 20:46, Eliot Miranda <[hidden email]> wrote: > > > On Tue, Oct 12, 2010 at 8:28 AM, Tom Rushworth <[hidden email]> > wrote: >> >> If you're going for atomic swap as a primitive, why not go for >> Compare-And-Swap? That way all the various lock-free algorithms that use >> the CAS machine instruction will translate easily. > > +1. > I want, e.g. > (var ?== expr : match) evaluates to true and var == expr if var == > prev before the statement, and false and var unchanged if var ~~ match > var ?= expr : match is more difficult to implement since = is not > necessarily primitive. > So one could write e.g. > LinkedList subclass: #Semaphore > instanceVariableNames: 'signals locked' > Semaphore>>signal > [locked ?== true : false] whileFalse. > self isEmpty > ifTrue: [signals := signals + 1] > ifFalse: [self removeFirst resume]. > locked := false >> >> CAS(variable,oldValue,newValue) is an atomic operation which returns a >> boolean value (my ST syntax is rusty at the moment, too much Objective-C): >> >> (variable == oldValue) ifTrue: [variable := newValue. ^true]. >> " variable not the same as oldValue, no swap performed " >> ^false >> >> On 2010-Oct-12, at 06:58, Igor Stasenko wrote: >> >> > On 12 October 2010 16:51, Levente Uzonyi <[hidden email]> wrote: >> >> On Tue, 12 Oct 2010, Igor Stasenko wrote: >> >> >> >>> Hello, i just thought, that it would be cool to have a special >> >>> bytecode, >> >>> which guarantees atomicity for swapping values between two variables. >> >>> >> >>> To swap two values, you usually do: >> >>> >> >>> | var1 var2 temp | >> >>> >> >>> temp := var1. >> >>> var1 := var2. >> >>> var2 := temp. >> >>> >> >>> But since its non-atomic, a process can be interrupted and such >> >>> operation >> >>> is not thread-safe. >> >>> >> >>> In order to make it thread safe, you must add even more boilerplate: >> >>> >> >>> | var1 var2 temp | >> >>> >> >>> semaphore critical: [ >> >>> temp := var1. >> >>> var1 := var2. >> >>> var2 := temp. >> >>> ] >> >> >> >> An alternative solution: >> >> >> >> | a b | >> >> a := 1. >> >> b := 2. >> >> [ >> >> | tmp | >> >> tmp := a. >> >> a := b. >> >> b := tmp ] valueUnpreemptively >> >> >> > >> > Yeah, another boilerplate under the hood, also highly dependent from >> > scheduling nuances :) >> > >> > valueUnpreemptively >> > "Evaluate the receiver (block), without the possibility of >> > preemption >> > by higher priority processes. Use this facility VERY sparingly!" >> > "Think about using Block>>valueUninterruptably first, and think >> > about >> > using Semaphore>>critical: before that, and think about redesigning >> > your application even before that! >> > After you've done all that thinking, go right ahead and use it..." >> > | activeProcess oldPriority result | >> > activeProcess := Processor activeProcess. >> > oldPriority := activeProcess priority. >> > activeProcess priority: Processor highestPriority. >> > result := self ensure: [activeProcess priority: oldPriority]. >> > "Yield after restoring priority to give the preempted processes a >> > chance to run" >> > Processor yield. >> > ^result >> >> >> >> Levente >> >> >> > >> > >> > >> > -- >> > Best regards, >> > Igor Stasenko AKA sig. >> > >> >> -- >> Tom Rushworth >> >> >> >> > > > > > -- Best regards, Igor Stasenko AKA sig. |
Re: How about atomic value-swap bytecode?
|
|
In reply to this post by Igor Stasenko
On 10/12/2010 6:14 AM, Igor Stasenko wrote:
> Hello, i just thought, that it would be cool to have a special bytecode, > which guarantees atomicity for swapping values between two variables. > > To swap two values, you usually do: > > | var1 var2 temp | > > temp := var1. > var1 := var2. > var2 := temp. > > But since its non-atomic, a process can be interrupted and such operation > is not thread-safe. Actually, this is thread-safe. Process switches happen only on sends and backwards branches. Cheers, - Andreas > > In order to make it thread safe, you must add even more boilerplate: > > | var1 var2 temp | > > semaphore critical: [ > temp := var1. > var1 := var2. > var2 := temp. > ] > > So, i thought , if we could have a special bytecode, then we could > write something like: > > | var1 var2 | > > var1 :=: var2. > > So, VM will guarantee that values of var1 and var2 will be swapped > atomically, and completely thread-safe. > > var1 and var2 could be either temps or instance variables, but of > course not arguments, since they are not assignable. > > One thing i don't like, that it will need to introduce a new syntax > for atomic-value-swap operator - :=: > > Or, maybe just reserve a special keyword selector (which is recognized > by compiler), so > > var1 __atomicSwapWith: var2 > > so it will look like a regular smalltalk syntax, except that its not a > message send, but a low-level operation instead. > > |
Re: How about atomic value-swap bytecode?
|
|
On 12 Oct 2010, at 22:51, Andreas Raab wrote: > On 10/12/2010 6:14 AM, Igor Stasenko wrote: >> Hello, i just thought, that it would be cool to have a special bytecode, >> which guarantees atomicity for swapping values between two variables. >> >> To swap two values, you usually do: >> >> | var1 var2 temp | >> >> temp := var1. >> var1 := var2. >> var2 := temp. >> >> But since its non-atomic, a process can be interrupted and such operation >> is not thread-safe. > > Actually, this is thread-safe. Process switches happen only on sends and backwards branches. You will never know where your code is running on tomorrow... http://permalink.gmane.org/gmane.comp.lang.smalltalk.squeak.general/152184 Best regards Stefan -- Stefan Marr Software Languages Lab Vrije Universiteit Brussel Pleinlaan 2 / B-1050 Brussels / Belgium http://soft.vub.ac.be/~smarr Phone: +32 2 629 2974 Fax: +32 2 629 3525 |
Re: How about atomic value-swap bytecode?
|
|
In reply to this post by Andreas.Raab
On 10/12/10 1:51 PM, Andreas Raab wrote:
> On 10/12/2010 6:14 AM, Igor Stasenko wrote: >> Hello, i just thought, that it would be cool to have a special bytecode, >> which guarantees atomicity for swapping values between two variables. >> >> To swap two values, you usually do: >> >> | var1 var2 temp | >> >> temp := var1. >> var1 := var2. >> var2 := temp. >> >> But since its non-atomic, a process can be interrupted and such >> operation >> is not thread-safe. > > Actually, this is thread-safe. Process switches happen only on sends > and backwards branches. > > outside of the block/method's scope can't be sure that the external vars are consistent? Lawson |
Re: How about atomic value-swap bytecode?
|
|
On 12.10.2010, at 14:25, Lawson English wrote: > On 10/12/10 1:51 PM, Andreas Raab wrote: >> On 10/12/2010 6:14 AM, Igor Stasenko wrote: >>> Hello, i just thought, that it would be cool to have a special bytecode, >>> which guarantees atomicity for swapping values between two variables. >>> >>> To swap two values, you usually do: >>> >>> | var1 var2 temp | >>> >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> >>> But since its non-atomic, a process can be interrupted and such operation >>> is not thread-safe. >> >> Actually, this is thread-safe. Process switches happen only on sends and backwards branches. >> >> > So code within blocks methods is thread safe but code that accesses data outside of the block/method's scope can't be sure that the external vars are consistent? No. Whenever you send a message, your process can be interrupted. Has nothing to do with blocks. In addition to sends, a loop can be interrupted, too, at its end (when the instruction pointer is decreased, a.k.a. backwards branching). As Stefan pointed out, it is unwise to rely on this in application code (it is okay in very low-level code like the scheduling/process implementation itself). - Bert - |
Re: How about atomic value-swap bytecode?
|
|
In reply to this post by Stefan Marr
On 10/12/10 2:21 PM, Stefan Marr wrote:
> On 12 Oct 2010, at 22:51, Andreas Raab wrote: > >> On 10/12/2010 6:14 AM, Igor Stasenko wrote: >>> Hello, i just thought, that it would be cool to have a special bytecode, >>> which guarantees atomicity for swapping values between two variables. >>> >>> To swap two values, you usually do: >>> >>> | var1 var2 temp | >>> >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> >>> But since its non-atomic, a process can be interrupted and such operation >>> is not thread-safe. >> Actually, this is thread-safe. Process switches happen only on sends and backwards branches. > Please, do not rely on such implementation details, and please do not advocate them. > You will never know where your code is running on tomorrow... > > http://permalink.gmane.org/gmane.comp.lang.smalltalk.squeak.general/152184 > > Will this be online also? Will there be videos available during/afterwards? Thanks. Lawson |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Igor Stasenko
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. 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. 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 :). I've used this pattern (expressed in C code) in a very heavily used parallel data processing application, so I can even claim to have tested it extensively :). > > ... locked here ... > > locked := false. > > Proof: > In the above, thread having chance to exit from waiting loop only if > temp == false. > There is no way how more than one waiting threads can leave this loop > at same time, > because 'locked' value is not copied over (assigned) but swapped > (always with true). > So, first who succeed to swap false <-> true will obtain a lock, > others will unable to do so, and swap true<->true, and thus will keep > waiting in the loop. > > > On 12 October 2010 20:46, Eliot Miranda <[hidden email]> wrote: >> >> >> On Tue, Oct 12, 2010 at 8:28 AM, Tom Rushworth <[hidden email]> >> wrote: >>> >>> If you're going for atomic swap as a primitive, why not go for >>> Compare-And-Swap? That way all the various lock-free algorithms that use >>> the CAS machine instruction will translate easily. >> >> +1. >> I want, e.g. >> (var ?== expr : match) evaluates to true and var == expr if var == >> prev before the statement, and false and var unchanged if var ~~ match >> var ?= expr : match is more difficult to implement since = is not >> necessarily primitive. >> So one could write e.g. >> LinkedList subclass: #Semaphore >> instanceVariableNames: 'signals locked' >> Semaphore>>signal >> [locked ?== true : false] whileFalse. >> self isEmpty >> ifTrue: [signals := signals + 1] >> ifFalse: [self removeFirst resume]. >> locked := false >>> >>> CAS(variable,oldValue,newValue) is an atomic operation which returns a >>> boolean value (my ST syntax is rusty at the moment, too much Objective-C): >>> >>> (variable == oldValue) ifTrue: [variable := newValue. ^true]. >>> " variable not the same as oldValue, no swap performed " >>> ^false >>> >>> On 2010-Oct-12, at 06:58, Igor Stasenko wrote: >>> >>>> On 12 October 2010 16:51, Levente Uzonyi <[hidden email]> wrote: >>>>> On Tue, 12 Oct 2010, Igor Stasenko wrote: >>>>> >>>>>> Hello, i just thought, that it would be cool to have a special >>>>>> bytecode, >>>>>> which guarantees atomicity for swapping values between two variables. >>>>>> >>>>>> To swap two values, you usually do: >>>>>> >>>>>> | var1 var2 temp | >>>>>> >>>>>> temp := var1. >>>>>> var1 := var2. >>>>>> var2 := temp. >>>>>> >>>>>> But since its non-atomic, a process can be interrupted and such >>>>>> operation >>>>>> is not thread-safe. >>>>>> >>>>>> In order to make it thread safe, you must add even more boilerplate: >>>>>> >>>>>> | var1 var2 temp | >>>>>> >>>>>> semaphore critical: [ >>>>>> temp := var1. >>>>>> var1 := var2. >>>>>> var2 := temp. >>>>>> ] >>>>> >>>>> An alternative solution: >>>>> >>>>> | a b | >>>>> a := 1. >>>>> b := 2. >>>>> [ >>>>> | tmp | >>>>> tmp := a. >>>>> a := b. >>>>> b := tmp ] valueUnpreemptively >>>>> >>>> >>>> Yeah, another boilerplate under the hood, also highly dependent from >>>> scheduling nuances :) >>>> >>>> valueUnpreemptively >>>> "Evaluate the receiver (block), without the possibility of >>>> preemption >>>> by higher priority processes. Use this facility VERY sparingly!" >>>> "Think about using Block>>valueUninterruptably first, and think >>>> about >>>> using Semaphore>>critical: before that, and think about redesigning >>>> your application even before that! >>>> After you've done all that thinking, go right ahead and use it..." >>>> | activeProcess oldPriority result | >>>> activeProcess := Processor activeProcess. >>>> oldPriority := activeProcess priority. >>>> activeProcess priority: Processor highestPriority. >>>> result := self ensure: [activeProcess priority: oldPriority]. >>>> "Yield after restoring priority to give the preempted processes a >>>> chance to run" >>>> Processor yield. >>>> ^result >>>>> >>>>> Levente >>>>> >>>> >>>> >>>> >>>> -- >>>> Best regards, >>>> Igor Stasenko AKA sig. >>>> >>> >>> -- >>> Tom Rushworth >>> >>> >>> >>> >> >> >> >> >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > -- Tom Rushworth |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
On 13 October 2010 18:07, Tom Rushworth <[hidden email]> 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. > > 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. Again, who said, that i going to use atomic swap for loops like above? 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've used this pattern (expressed in C code) in a very heavily used parallel data processing application, so I can even claim to have tested it extensively :). > Yes yes.. But C is not Smalltalk. >> -- Best regards, Igor Stasenko AKA sig. |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Tom Rushworth-3
Hi Tom,
On Wed, Oct 13, 2010 at 8:07 AM, Tom Rushworth <[hidden email]> wrote: Hi all, 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.
|
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Tom Rushworth-3
Hi Tom,
On Wed, Oct 13, 2010 at 8:07 AM, Tom Rushworth <[hidden email]> wrote: Hi all, 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.
|
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Eliot Miranda-2
On 13 October 2010 18:54, Eliot Miranda <[hidden email]> 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. Eliot, if this not a bytecode (which is much more lightweigth to primitive), then why bother ? It is trivial to implement a primitive like: Array>>compareAt: index with: value andStore: anObject <primitive: 'primitiveCAS' > ... so, then you can do: moo := Array with: 100. oldValue := moo compareAt: 1 with: 100 andStore: 2. self assert: oldValue == 100. self assert: moo first == 2 -- Best regards, Igor Stasenko AKA sig. |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Igor Stasenko
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. 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. 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... On 2010-Oct-13, at 08:33, Igor Stasenko wrote: > On 13 October 2010 18:07, Tom Rushworth <[hidden email]> 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.... > > >> I've used this pattern (expressed in C code) in a very heavily used parallel data processing application, so I can even claim to have tested it extensively :). >> > > Yes yes.. But C is not Smalltalk. Very true, as Eliot pointed out one of the implications of the difference above. However, the algorithms for safe access to data in a multi-threaded environment are completely language and hardware independent. You simply choose the algorithm you use to match what your language and HW have available for you to implement the algorithm. In this context, if your (our) language provide CAS, you end up with a much broader choice of algorithms. The only reason I brought up the HW CAS instruction was to make it clear that the machine code or C code for the primitive would not be any more complicated for CAS no matter what the assumptions or guarantees are for the VM scheduler. > >>> > > -- > Best regards, > Igor Stasenko AKA sig. > Regards, -- Tom Rushworth |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Igor Stasenko
On Tue, 12 Oct 2010, Igor Stasenko wrote:
> On 12 October 2010 16:51, Levente Uzonyi <[hidden email]> wrote: >> On Tue, 12 Oct 2010, Igor Stasenko wrote: >> >>> Hello, i just thought, that it would be cool to have a special bytecode, >>> which guarantees atomicity for swapping values between two variables. >>> >>> To swap two values, you usually do: >>> >>> | var1 var2 temp | >>> >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> >>> But since its non-atomic, a process can be interrupted and such operation >>> is not thread-safe. >>> >>> In order to make it thread safe, you must add even more boilerplate: >>> >>> | var1 var2 temp | >>> >>> semaphore critical: [ >>> temp := var1. >>> var1 := var2. >>> var2 := temp. >>> ] >> >> An alternative solution: >> >> | a b | >> a := 1. >> b := 2. >> [ >> | tmp | >> tmp := a. >> a := b. >> b := tmp ] valueUnpreemptively >> > > Yeah, another boilerplate under the hood, also highly dependent from > scheduling nuances :) idea: Add the compiler changes to support :=: as atomic swap. We don't really need a bytecode for now, since a sequence of assignments is currently atomic. So the compiler could compile :=: as three assignments using a hidden temporary variable. On other systems, :=: can be compiled differently. Levente > > valueUnpreemptively > "Evaluate the receiver (block), without the possibility of preemption > by higher priority processes. Use this facility VERY sparingly!" > "Think about using Block>>valueUninterruptably first, and think about > using Semaphore>>critical: before that, and think about redesigning > your application even before that! > After you've done all that thinking, go right ahead and use it..." > | activeProcess oldPriority result | > activeProcess := Processor activeProcess. > oldPriority := activeProcess priority. > activeProcess priority: Processor highestPriority. > result := self ensure: [activeProcess priority: oldPriority]. > "Yield after restoring priority to give the preempted processes a > chance to run" > Processor yield. > ^result >> >> Levente >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Tom Rushworth-3
On 13 October 2010 19:41, Tom Rushworth <[hidden email]> 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. > > 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. > > 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... > > On 2010-Oct-13, at 08:33, Igor Stasenko wrote: > >> On 13 October 2010 18:07, Tom Rushworth <[hidden email]> 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. how many spin loops you seen where you need more than two values (true/false) i.e. locked/unlocked ? :) >> >>> >>> 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. > see.. now in own turn i can say.. hey.. i can do it w/o temp and without a loop. :) > 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. Ok. Here is a simple example for you. A shared LIFO queue. Populating: | temp | temp := newItem := QueueItem new. queueHead :=: newItem. temp next: newItem. Flushing and processing the queue: | oldHead | oldHead := nil. queueHead :=: oldHead. [ oldHead notNil ] whileTrue: [ "process the queue item here" oldHead := oldHead next. ] > >> 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.... If you tell me how you can atomically evaluate: SmallInteger maxVal+1 i'll try :) >> >> >>> I've used this pattern (expressed in C code) in a very heavily used parallel data processing application, so I can even claim to have tested it extensively :). >>> >> >> Yes yes.. But C is not Smalltalk. > > Very true, as Eliot pointed out one of the implications of the difference above. However, the algorithms for safe access to data in a multi-threaded environment are completely language and hardware independent. You simply choose the algorithm you use to match what your language and HW have available for you to implement the algorithm. In this context, if your (our) language provide CAS, you end up with a much broader choice of algorithms. > > The only reason I brought up the HW CAS instruction was to make it clear that the machine code or C code for the primitive would not be any more complicated for CAS no matter what the assumptions or guarantees are for the VM scheduler. I'm not arguing about userfulness of CAS. As i said, if you think its cool to have as well, lets think how to add it as well. But i'm against 'lets add CAS instead of atomic swap'. -- Best regards, Igor Stasenko AKA sig. |
Re: [Pharo-project] How about atomic value-swap bytecode?
|
|
In reply to this post by Igor Stasenko
On Wed, Oct 13, 2010 at 9:22 AM, Igor Stasenko <[hidden email]> wrote:
I'm sorry; I thought it was obvious that the above would be implemented as a bytecode since := is a (set of) bytecode(s). In fact it would be three bytecodes, e.g. cassignTemp, cassingnInstVar and cassingnLitVar.
Yes, but that requires two primitives (inst vars and indexed vars) and doesn't work elegantly on temp vars so I think expressively it's very poor. Whereas the bytecode is elegant and operates where I want it on variables. Do you see much utility for cas on arrays instead of cas on inst, temp and global vars?
best Eliot ... |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |