[Pharo-project] 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.
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 Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
On 12 October 2010 16:51, Levente Uzonyi <leves@elte.hu> 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.
On Tue, 12 Oct 2010, Igor Stasenko wrote:
On 12 October 2010 16:51, Levente Uzonyi <leves@elte.hu> 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 :)
I don't get the "dependency from scheduling nuances part", but here's my 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.
FWIW, Dolphin has (or at least had in earlier versions - I can check later if it matters) an analog to #valueUnpreemptively. Something like that is likely to be more portable than new syntax or a new bytecode. Any VW experts care to comment on what might be available there? Bill ________________________________________ From: pharo-project-bounces@lists.gforge.inria.fr [pharo-project-bounces@lists.gforge.inria.fr] On Behalf Of Levente Uzonyi [leves@elte.hu] Sent: Wednesday, October 13, 2010 1:00 PM To: The general-purpose Squeak developers list Cc: Pharo Development Subject: Re: [Pharo-project] [squeak-dev] Re: How about atomic value-swap bytecode? On Tue, 12 Oct 2010, Igor Stasenko wrote:
On 12 October 2010 16:51, Levente Uzonyi <leves@elte.hu> 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 :)
I don't get the "dependency from scheduling nuances part", but here's my 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.
2010/10/13 Levente Uzonyi <leves@elte.hu>:
On Tue, 12 Oct 2010, Igor Stasenko wrote:
On 12 October 2010 16:51, Levente Uzonyi <leves@elte.hu> 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 :)
I don't get the "dependency from scheduling nuances part", but here's my idea:
i don't like the code, which assuming that scheduling works in some specific way, or some code can't be interrupted in the middle. See Semaphore>>critical: for excersise. | caught | caught := false. ^[ caught := true. self wait. mutuallyExcludedBlock value ] ensure: [ caught ifTrue: [self signal] ] this code assuming that between caught := true. and self wait. no interrupt possible. But if it is, then the above implementation is incorrect.
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.
For same reason, there is no any guarantees from VM side that three assignments in a row will be atomic: storing pointer could trigger a root check, and if roots table is full, it could trigger GC, and after GC, there is a finalization semaphore, which could switch an active process immediately. VM is evolving and subject to change. Having a clear rule which guarantees a specific behavior is far more beneficial comparing to intimate knowledge about how VM works (now).
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.
-- Best regards, Igor Stasenko AKA sig.
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.
As far as I know the VM only preempts on back-jumps and message sends. None of that exists in your code snipped, so it should be atomic. No? Lukas -- Lukas Renggli www.lukas-renggli.ch
On 12 October 2010 17:07, Lukas Renggli <renggli@gmail.com> wrote:
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.
As far as I know the VM only preempts on back-jumps and message sends. None of that exists in your code snipped, so it should be atomic. No?
This is a bit blurry. I remember Eliot said it is no longer true under Cog VM.
Lukas
-- Lukas Renggli www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Best regards, Igor Stasenko AKA sig.
But since its non-atomic, a process can be interrupted and such operation is not thread-safe.
As far as I know the VM only preempts on back-jumps and message sends. None of that exists in your code snipped, so it should be atomic. No?
This is a bit blurry. I remember Eliot said it is no longer true under Cog VM.
Then let's just pray that the method comment of Semaphore>>#critical: is outdated and the implementation is fixed. Lukas -- Lukas Renggli www.lukas-renggli.ch
participants (4)
-
Igor Stasenko -
Levente Uzonyi -
Lukas Renggli -
Schwab,Wilhelm K