Lock-free Atomic Counter ?
Locked
Lock-free Atomic Counter ?
 
|
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 <[hidden email]> wrote: Hi, #+ 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, -- Best regards, Igor Stasenko. |
Re: Lock-free Atomic Counter ?
|
|
In reply to this post by Sven Van Caekenberghe-2
Hi Sven,
On Wed, Apr 2, 2014 at 3:11 PM, Sven Van Caekenberghe <[hidden email]> wrote: Hi, 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 ;-)
best, Eliot
|
|
|
In reply to this post by Igor Stasenko
so, lock-free counter can be something like: atomicIncr | oldValue | [ oldValue := self atomicSwapCounterWithDummy. oldValue == dummy ] whileTrue: [ Processor yield ]. atomicSwapCounterWithDummy | old | old := counter. counter := dummy. ^ old 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 <[hidden email]> wrote:
-- Best regards, Igor Stasenko. |
|
|
extra note about yielding: - if i remember correctly, it yields on same priority level, letting other process (if any)On 3 April 2014 01:34, Igor Stasenko <[hidden email]> wrote:
-- Best regards, Igor Stasenko. |
Re: Lock-free Atomic Counter ?
|
|
In reply to this post by Igor Stasenko
On Thu, 3 Apr 2014, Igor Stasenko wrote:
> > > > On 3 April 2014 00:11, Sven Van Caekenberghe <[hidden email]> 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 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. > > |
Re: Lock-free Atomic Counter ?
|
|
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 <[hidden email]> 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. > > > > |
Re: Lock-free Atomic Counter ?
|
|
In reply to this post by Sven Van Caekenberghe-2
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 <[hidden email]> 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 |
Re: Lock-free Atomic Counter ?
|
|
In reply to this post by 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 <[hidden email]> 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 <[hidden email]> wrote: > > > > On 3 April 2014 00:11, Sven Van Caekenberghe <[hidden email]> 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 <[hidden email]> 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.
-- Best regards, Igor Stasenko. |
Re: Lock-free Atomic Counter ?
|
|
On 04 Apr 2014, at 19:29, Igor Stasenko <[hidden email]> wrote: > On 4 April 2014 18:31, Sven Van Caekenberghe <[hidden email]> 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 <[hidden email]> 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 <[hidden email]> wrote: > > > > > > > > On 3 April 2014 00:11, Sven Van Caekenberghe <[hidden email]> 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 <[hidden email]> wrote:
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. |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |