Lock free structures in Pharo
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation? Stephan AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic" | temp | " atomic swap here" temp := next. next := self. ^ temp
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode therefore it can not be interrupted and process switches can not happen between the statements. Marcus
Am 14.11.2013 um 10:25 schrieb Marcus Denker <marcus.denker@inria.fr>:
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself. Norbert
Hi Norbert, I couldn't have said it any better. For me, this also was interesting, because I first thought: "Heck, how would I make anything atomic anyways?". And that question still stands: is there a way to make something atomic that includes message sends? I guess #critical is not the solution, is it? Joachim Am 14.11.13 11:12, schrieb Norbert Hartl:
Am 14.11.2013 um 10:25 schrieb Marcus Denker <marcus.denker@inria.fr>:
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements. Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
-- ----------------------------------------------------------------------- Objektfabrik Joachim Tuchel mailto:jtuchel@objektfabrik.de Fliederweg 1 http://www.objektfabrik.de D-71640 Ludwigsburg http://joachimtuchel.wordpress.com Telefon: +49 7141 56 10 86 0 Fax: +49 7141 56 10 86 1
Am 14.11.2013 um 11:16 schrieb jtuchel@objektfabrik.de:
Hi Norbert,
I couldn't have said it any better. For me, this also was interesting, because I first thought: "Heck, how would I make anything atomic anyways?". And that question still stands: is there a way to make something atomic that includes message sends? I guess #critical is not the solution, is it?
No, because then it isnât lock free anymore ;) Norbert
Am 14.11.13 11:12, schrieb Norbert Hartl:
Am 14.11.2013 um 10:25 schrieb Marcus Denker <marcus.denker@inria.fr>:
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements. Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
-- ----------------------------------------------------------------------- Objektfabrik Joachim Tuchel mailto:jtuchel@objektfabrik.de Fliederweg 1 http://www.objektfabrik.de D-71640 Ludwigsburg http://joachimtuchel.wordpress.com Telefon: +49 7141 56 10 86 0 Fax: +49 7141 56 10 86 1
Am 14.11.13 11:19, schrieb Norbert Hartl:
Am 14.11.2013 um 11:16 schrieb jtuchel@objektfabrik.de:
Hi Norbert,
I couldn't have said it any better. For me, this also was interesting, because I first thought: "Heck, how would I make anything atomic anyways?". And that question still stands: is there a way to make something atomic that includes message sends? I guess #critical is not the solution, is it?
No, because then it isnât lock free anymore ;)
Norbert I knew I was typing something stupid ;-) But you are of course right. #critical's whole concept is locking, of course ;-)
-- ----------------------------------------------------------------------- Objektfabrik Joachim Tuchel mailto:jtuchel@objektfabrik.de Fliederweg 1 http://www.objektfabrik.de D-71640 Ludwigsburg http://joachimtuchel.wordpress.com Telefon: +49 7141 56 10 86 0 Fax: +49 7141 56 10 86 1
Clement also told me that the VM only checked for Cmd-. breaks on back jumps. Phil On Thu, Nov 14, 2013 at 11:16 AM, jtuchel@objektfabrik.de < jtuchel@objektfabrik.de> wrote:
Hi Norbert,
I couldn't have said it any better. For me, this also was interesting, because I first thought: "Heck, how would I make anything atomic anyways?". And that question still stands: is there a way to make something atomic that includes message sends? I guess #critical is not the solution, is it?
Joachim
Am 14.11.13 11:12, schrieb Norbert Hartl:
Am 14.11.2013 um 10:25 schrieb Marcus Denker <marcus.denker@inria.fr>:
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic.
Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
-- ----------------------------------------------------------------------- Objektfabrik Joachim Tuchel mailto:jtuchel@objektfabrik.de Fliederweg 1 http://www.objektfabrik.de D-71640 Ludwigsburg http://joachimtuchel.wordpress.com Telefon: +49 7141 56 10 86 0 Fax: +49 7141 56 10 86 1
Note that it would be good to have a special syntactic construct for that because now we rely on the way the compiler works to ensure such properties and it means that an accessor and a direct access are not semantically equals. Stef
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
Stef, Am 14.11.2013 um 12:10 schrieb Stéphane Ducasse <stephane.ducasse@inria.fr>:
Note that it would be good to have a special syntactic construct for that because now we rely on the way the compiler works to ensure such properties and it means that an accessor and a direct access are not semantically equals.
I was asking for pointers/locations where to look at. I like to wrap my head around it in order to understand how it works and thus figuring out where and when there is a problem. Norbert
Stef
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
You should look in VM code clement / eliot can reply more precisely but the idea is to see when do you accept to suspend a computation. In Smalltlak this is after each message. Stef
Stef,
Am 14.11.2013 um 12:10 schrieb Stéphane Ducasse <stephane.ducasse@inria.fr>:
Note that it would be good to have a special syntactic construct for that because now we rely on the way the compiler works to ensure such properties and it means that an accessor and a direct access are not semantically equals.
I was asking for pointers/locations where to look at. I like to wrap my head around it in order to understand how it works and thus figuring out where and when there is a problem.
Norbert
Stef
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
On 14 nov. 2013, at 12:38, Stéphane Ducasse <stephane.ducasse@inria.fr> wrote:
You should look in VM code clement / eliot can reply more precisely but the idea is to see when do you accept to suspend a computation. In Smalltlak this is after each message.
Except for #== and inlined message like #ifTrue:ifFalse: , #to:do: , etc... See http://forum.world.st/About-and-td3898409.html for more details
Stef
Stef,
Am 14.11.2013 um 12:10 schrieb Stéphane Ducasse <stephane.ducasse@inria.fr>:
Note that it would be good to have a special syntactic construct for that because now we rely on the way the compiler works to ensure such properties and it means that an accessor and a direct access are not semantically equals.
I was asking for pointers/locations where to look at. I like to wrap my head around it in order to understand how it works and thus figuring out where and when there is a problem.
Norbert
Stef
On 14 Nov 2013, at 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
-> no message send -> no back jump bytecode
therefore it can not be interrupted and process switches can not happen between the statements.
Thanks, I learn something new every day. Iâve never thought about the condition when a process switch can happen. Can you say in short when a switch of processes is checked? Because I think I wonât finding it in a reasonable time looking myself.
Norbert
On 14 November 2013 10:15, Stephan Eggermont <stephan@stack.nl> wrote:
Reading this code, made me wonder what operations are actually atomic. Anyone having a good explanation?
Stephan
AtomicQueueItem>makeCircular "Make a receiver circular, i.e. point to itself, answer the old value of next variable. Note, this operation should be atomic"
| temp |
" atomic swap here" temp := next. next := self.
^ temp
imagine that i rewrite it with following:
temp := self. temp <=> next. ^ temp here the <=> is a special 'atomic swap' operation which atomically swaps values of two variables. The best way to do that is to introduce a special bytecode in VM, which either swaps values of two temps or swaps values of temp and instance variable. If we could have such bytecode, then we would have a strong guarantee from VM about atomicity of certain operations, but since we don't have it yet, right now it is just (ab)uses the intrinsic behavior of VM, knowing that it never interrupts between two simple assignments. -- Best regards, Igor Stasenko.
participants (8)
-
Camille Teruel -
Igor Stasenko -
jtuchel＠objektfabrik.de -
Marcus Denker -
Norbert Hartl -
phil＠highoctane.be -
Stephan Eggermont -
Stéphane Ducasse