Hi, Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ? nextId ^ idCounter := idCounter + 1 Or is it still possible that two process entering this code can mess things up ? I vaguely remember a discussion about that long ago... TIA, Sven
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends) x:= a. y:=b. z := c. w := e. will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
so, lock-free counter can be something like: atomicIncr | oldValue | [ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ]. ^ counter := oldValue + 1 atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old so you use dummy to block anyone from setting the new value unless you set it. dummy can be any object (not a number in your care), and lastly, once you assign a new value, you effectively release a "lock" :) Processor yield is mainly attempt to avoid busy-waiting. On 3 April 2014 01:28, Igor Stasenko <siguctua@gmail.com> wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
extra note about yielding: - if i remember correctly, it yields on same priority level, letting other process (if any) at same priority level to take control. and if there's none, then it is NOP. so, if counter incr. used by processes with different priority it is better to replace it with 1 ms sleep. or.... if you don't care, about busy waiting.. you can just don't put anything :) On 3 April 2014 01:34, Igor Stasenko <siguctua@gmail.com> wrote:
so, lock-free counter can be something like:
atomicIncr | oldValue |
[ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ].
^ counter := oldValue + 1
atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old
so you use dummy to block anyone from setting the new value unless you set it. dummy can be any object (not a number in your care), and lastly, once you assign a new value, you effectively release a "lock" :)
Processor yield is mainly attempt to avoid busy-waiting.
On 3 April 2014 01:28, Igor Stasenko <siguctua@gmail.com> wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
Just for the sake of discussion, you try to prevent interruptions by using assignments, right ? But you still need #== which seems like a (potential) message send, which brings us back to the other arguments in this thread. Furthermore, the dummy value must be different for each of the processes/threads entering, no ? On 03 Apr 2014, at 01:34, Igor Stasenko <siguctua@gmail.com> wrote:
so, lock-free counter can be something like:
atomicIncr | oldValue |
[ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ].
^ counter := oldValue + 1
atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old
so you use dummy to block anyone from setting the new value unless you set it. dummy can be any object (not a number in your care), and lastly, once you assign a new value, you effectively release a "lock" :)
Processor yield is mainly attempt to avoid busy-waiting.
On 3 April 2014 01:28, Igor Stasenko <siguctua@gmail.com> wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
On 4 April 2014 18:31, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Just for the sake of discussion, you try to prevent interruptions by using assignments, right ? But you still need #== which seems like a (potential) message send, which brings us back to the other arguments in this thread. Furthermore, the dummy value must be different for each of the processes/threads entering, no ?
dummy is placeholder used solely to detect that counter is 'locked' via #== comparison.. can be any object not really matters if you share it among processes or not, since it carries no state.
#== , whileTrue: .. as well as any other message sends potentially is subject of being interrupted.. but there's nothing wrong with it, as long as two assignments (in a row) don't have chance to be interrupted.
On 03 Apr 2014, at 01:34, Igor Stasenko <siguctua@gmail.com> wrote:
so, lock-free counter can be something like:
atomicIncr | oldValue |
[ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ].
^ counter := oldValue + 1
atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old
so you use dummy to block anyone from setting the new value unless you set it. dummy can be any object (not a number in your care), and lastly, once you assign a new value, you effectively release a "lock" :)
Processor yield is mainly attempt to avoid busy-waiting.
On 3 April 2014 01:28, Igor Stasenko <siguctua@gmail.com> wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
On 04 Apr 2014, at 19:29, Igor Stasenko <siguctua@gmail.com> wrote:
On 4 April 2014 18:31, Sven Van Caekenberghe <sven@stfx.eu> wrote: Just for the sake of discussion, you try to prevent interruptions by using assignments, right ? But you still need #== which seems like a (potential) message send, which brings us back to the other arguments in this thread. Furthermore, the dummy value must be different for each of the processes/threads entering, no ?
dummy is placeholder used solely to detect that counter is 'locked' via #== comparison.. can be any object not really matters if you share it among processes or not, since it carries no state.
#== , whileTrue: .. as well as any other message sends potentially is subject of being interrupted.. but there's nothing wrong with it, as long as two assignments (in a row) don't have chance to be interrupted.
All this is quite interesting (and makes my head hurt), maybe we should implement this as a helper class in the image, along side the other lock free stuff ?
On 03 Apr 2014, at 01:34, Igor Stasenko <siguctua@gmail.com> wrote:
so, lock-free counter can be something like:
atomicIncr | oldValue |
[ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ].
^ counter := oldValue + 1
atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old
so you use dummy to block anyone from setting the new value unless you set it. dummy can be any object (not a number in your care), and lastly, once you assign a new value, you effectively release a "lock" :)
Processor yield is mainly attempt to avoid busy-waiting.
On 3 April 2014 01:28, Igor Stasenko <siguctua@gmail.com> wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :)
I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
TIA,
Sven
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
-- Best regards, Igor Stasenko.
On 4 April 2014 22:54, Sven Van Caekenberghe <sven@stfx.eu> wrote:
On 04 Apr 2014, at 19:29, Igor Stasenko <siguctua@gmail.com> wrote:
On 4 April 2014 18:31, Sven Van Caekenberghe <sven@stfx.eu> wrote: Just for the sake of discussion, you try to prevent interruptions by using assignments, right ? But you still need #== which seems like a (potential) message send, which brings us back to the other arguments in this thread. Furthermore, the dummy value must be different for each of the processes/threads entering, no ?
dummy is placeholder used solely to detect that counter is 'locked' via #== comparison.. can be any object not really matters if you share it among processes or not, since it carries no state.
#== , whileTrue: .. as well as any other message sends potentially is subject of being interrupted.. but there's nothing wrong with it, as long as two assignments (in a row) don't have chance to be interrupted.
All this is quite interesting (and makes my head hurt), maybe we should implement this as a helper class in the image, along side the other lock free stuff ?
i don't know.. do you think it shall be part of some 'atomics' library?
From other side, for same problem there can be many different solutions.. For instance, if you need to uniquely identify an object, what can be simpler than just using that object (identity)? And simplest way to obtain unique object, which nobody can read/write to, is to allocate a new one.. and as long as you don't give a reference to it, it is free from any concurrency caveats..
-- Best regards, Igor Stasenko.
On Thu, 3 Apr 2014, Igor Stasenko wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId  ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of
If #+ is compiled to bytecode 176, and both the receiver and the argument are SmallIntegers, then it's not a message send, so the operation is atomic. Levente
returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :) Â I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
 TIA,
Sven
-- Best regards, Igor Stasenko.
I hate to bust this old evilness out, but is it feasible to abuse #become: for this purpose? I haven't used it in so long I don't actually remember whether that's feasible semantics with ivars. On Thu, Apr 3, 2014, at 09:08 AM, Levente Uzonyi wrote:
On Thu, 3 Apr 2014, Igor Stasenko wrote:
On 3 April 2014 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote: Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId  ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
#+ is a message send. So technically, if you will be interrupted at the point of
If #+ is compiled to bytecode 176, and both the receiver and the argument are SmallIntegers, then it's not a message send, so the operation is atomic.
Levente
returning a result from it, then somebody else could run #nextId without notice, as result you will get 2 processes returning same value from #nextId. (and increasing numbers of concurrent processes will produce even more surprising results :) Â I vaguely remember a discussion about that long ago...
assignment is atomic.. the one which i use in atomic queue impl., but it is hidden, undocumented VM implementation detail :) e.g.:
oldA := a. a := newA. .. actually can be any series of it, as long as nothing else there (no message sends)
x:= a. y:=b. z := c. w := e.
will be performed atomically.
 TIA,
Sven
-- Best regards, Igor Stasenko.
Hi Sven, On Wed, Apr 2, 2014 at 3:11 PM, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
OK, but it's a real hack ;-). In the current Interpreter, Stack and Cog VMs this will work fine up to 63-bits because non-failing primitives are not suspension points in the VM /except/ for the Semaphore primitives. If the counter is initialized to 0, at first, there won't even be a send since either the interpreter will evaluate special selector #+ on SmallInteger without performing a send, or machine code will evaluate the inlined code for SmallInteger #+ without doing a send. Once the counter overflows into LargePositveInteger but is within 63-bits, there will be sends but these will always be of primitive 21 (LargePositiveInteger>>#+ uses primitive 21, which does 64-bit /signed/ arithmetic but nothing larger, hence works up to 63-bit LargePositiveIntegers). Once beyond 63 bits the primitive will fail and there will be a suspension point in LargePositiveInteger>>#+ before it calls Integer>>#+, which will call digitAdd:. You should be able to test this. Try evaluating this one: | counter proc | counter := 0. proc := [[counter := counter + 1. true] whileTrue] newProcess. proc priority: Processor activePriority - 1. proc resume. [(Delay forSeconds: 1) wait. proc suspendedContext method ~~ thisContext method ifTrue: [proc suspend. self halt]] repeat Now try and evaluate this one: | counter proc | counter := 1 bitShift: 64. proc := [[counter := counter + 1. true] whileTrue] newProcess. proc priority: Processor activePriority - 1. proc resume. [(Delay forSeconds: 1) wait. proc suspendedContext method ~~ thisContext method ifTrue: [proc suspend. self halt]] repeat The second one halts almost immediately. You can fix this by changing LargePositiveInteger>>#+ to use the primitive frm the large integer arithmetic plugin, which will not fail until it runs out of memory. So if you really /must/ go this route you /can/ get away with it. But on your own head be it ;-)
I vaguely remember a discussion about that long ago...
TIA,
Sven
-- best, Eliot
Thanks guys for all the answers, I think I am going to stick with the simple code and no protection based on the arguments that I read. It will do for my application where nothing catastrophic will happen when in case of a clash. On 03 Apr 2014, at 00:11, Sven Van Caekenberghe <sven@stfx.eu> wrote:
Hi,
Is it possible to have a simple lock-free atomic counter in Pharo 3.0 ?
nextId ^ idCounter := idCounter + 1
Or is it still possible that two process entering this code can mess things up ?
I vaguely remember a discussion about that long ago...
TIA,
Sven
participants (5)
-
Benjamin Pollack -
Eliot Miranda -
Igor Stasenko -
Levente Uzonyi -
Sven Van Caekenberghe