6 ms·

Single Writer Principle (2011)

70 points by jorangreef 6y ago

chrisweekly 6y ago
Wonderful stuff, as usual. And, because it's written from first principles, it holds up almost a decade later.
hpoe 6y ago
So I have heard about the idea of OOP being about passing messages between objects, rather than just calling functions with parameters but I can't seem to figure it out in a mental model. How does passing a message to an object differ from just calling an object's methods with parameters? Is there other good sources for understanding the differences and rewiring the mental model?
- deleted 6y ago
  [deleted]
- spooneybarger 6y ago
  A large part of your confusion might be that a lot of OO teaching sources define message passing as calling a function. Message passing allows for you to have the receiver of the message run in a different execution context; for example erlang. Calling an objects methods with parameters is tied to that execution context. Message passing is a larger concept than OOP. Microkernels for example are built around message passing as the means of communication.
  - int_19h 6y ago
    > Calling an objects methods with parameters is tied to that execution context. Not necessarily - this depends on the language, or rather, on the object model. But consider COM or CORBA: you call a method, but the object might be on a different machine altogether.
- bob1029 6y ago
  When you get to a very low-level, I think one way to look at it would be to say that the most simple form of message passing is simply invoking functions with arguments which contain message data. Most people probably go straight into the multi-node pub/sub universe when "messaging" starts being thrown around, but it could just as well be direct method invocation with objects in the single node/process case. The nuance and complexity seems to come from where those messages are stored, and how access to them (or knowledge of their availability).
- ncmncm 6y ago
  Ultimately there is no real difference between function calls and message-passing. It is a matter of emphasis. When you design with message-passing in mind, you don't expect an immediate answer to the message; instead, you expect to get an answer as another message. In some cases, this adds overhead: two messages, vs one function call. In others, you can do something else useful immediately after sending the message, and handle the return message whenever it arrives, maybe much later. It is common to overlay a function calling mechanism on top of message passing. This is called "RPC", and is often a bad idea. The failure modes of message systems differ from those for function calls, so that assuptions higher up in the abstraction tend to be wrong.
- deleted 6y ago
  [deleted]
- ben509 6y ago
  I seen various descriptions of message passing in OOP that wind up meaning "invoke a method, alter an object, return an answer." Lots of different ways to describe a method, lots of ways to modify the object, lots of ways to return an answer, but conceptually, they're all just invoking a method. I think in some languages and frameworks, message passing is associated with expressing a GUI, so objects have handlers for events, and there is more structure around how events can be signalled and handled. I'm thinking of Smalltalk, Hypercard and modern browsers. It's also more distinct in concurrent programming with something like communicating sequential processes (CSP), where message passing is a way for concurrent processes to agree on how to share state. So when process A writes some data to a channel C it explicitly hands that data off, thus process B can read from C and operate on the data without corrupting anything. (Contrast with threads where you can modify anything, any time, so you have to use locks and deal with deadlock and such.)
- gens 6y ago
  Checking out what Alan Kay has to say about it might help: https://www.youtube.com/watch?v=fhOHn9TClXY https://www.youtube.com/watch?v=fhOHn9TClXY The way i see it OOP is about encapsulating/bundling data and the code that processes that data into one "object", that is isolated from other objects. The objects could only "communicate" with other objects by sending "messages" (data/events/something). Personally i don't like OOP, and think that focusing on data and how it's processed is a better way forward (CSP and such). It's.. a complicated matter.
- jorangreef 6y ago
  Passing a message is immutable for starters, which means read-only access for the receiving process, enforcing the single-writer principle.
- mercer 6y ago
  I think one important difference is that if you call a method, things fail when the method doesn't exist, or the wrong arguments are passed. With message passing, the callee can decide not to respond to a message. Or to respond at a later time. In a broader sense, I'd say the difference is between pressing a button on a robot that 'forces' it to walk, or asking said robot to please go and walk. In the former case, you're essentially reaching 'into' the robot's behavior via an exposed control. The caller is in charge. In the latter case you have no control and the callee, the robot, has the freedom to decide what to do and when to do it.
- polyglotfacto 6y ago
  Calling a method on an object could potentially alter the internal state of that object. So in the context of some sort of concurrent execution, calling a method implies first of all having a direct reference to the object from the thread of execution where the method call occurs, and then it also implies having to synchronize potential state changes(writes) with other threads of execution who might also have a reference to the object and call methods on it. On the other hand, sending a message would allow for only a single thread of execution owning that object, and calling methods on the object in response to incoming messages. So I'd say it's not really "sending a message to an object", it's rather "sending a message to some kind of thread of execution, which owns that object uniquely". Result: there is a "single writer" with regards to the internal state of that object. I actually wrote an article on this for Rust, perhaps it could help rewiring your mental model: https://medium.com/@polyglot_factotum/rust-concurrency-the-single-writer-principle-applied-aada2cdc6fb0 https://medium.com/@polyglot_factotum/rust-concurrency-the-s...
dang 6y ago
Discussed just a bit at the time: https://news.ycombinator.com/item?id=3219193 https://news.ycombinator.com/item?id=3219193
ncmncm 6y ago
This principle is the basis for the extremely better throughput of ring buffers over other so-called "lock-free" queue structures. Things labeled "lock-free" typically are not; instead, they rely on locks at the hardware level that are subject to the same sort of contention seen with software-visible locks, such as mutexes, and the same sort of stalls, with just smaller numbers. So, a lock-free queue is often little faster than a locking one. But a ring buffer suffers from none of these overheads. The reader has to be sure to keep up with the writer, over a short enough time scale not to "get lapped"; but you need that anyway.
- troutwine 6y ago
  > Things labeled "lock-free" typically are not; instead, they rely on locks at the hardware level that are subject to the same sort of contention seen with software-visible locks, such as mutexes, and the same sort of stalls, with just smaller numbers. This isn't quite true. The 'hardware level lock' you're referring to are memory ordering primitives that allow you to coordinate threads of execution in a way that allows them to see memory operations in sequences that come to the same thing. Your notion of a software-visible lock is a construct built out of these primitives: the simplest mutex is an Acquire/Release pair. The difference might seem subtle -- and it is -- but it's very important. A lock requires that all coordinated threads operate in lockstep with one another at some point in their execution. A lock-free structure does not. A lock-free structure will be built to allow coordinated threads to see memory in ways that come to the same thing but in ways that don't require lock-step. A subclass of these kinds of structures are lock-free/wait-free, that is, they provably do not have any 'stalls' where coordinated threads must wait for the forward-progress of one of their cohort before they can operate, if I understand correctly what you're referring to as a stall. I do however acknowledge that x86 will coordinate your threads in some cases because of it's strong consistency guarantees. That is a complication. > So, a lock-free queue is often little faster than a locking one. This strongly, strongly depends on the environment you're running in and the nature of your queues, how over-contended your structures are. OS provided locks will often have hooks into the scheduler, which is a significant win over naive user-space spins. That's not to say you can't signal the scheduler yourself about being unable to proceed, and this is often done. I will readily admit that lock-free structures -- especially wait-free -- are specialty structures and you're almost surely better off starting with a traditional locking structure, unless everything you're doing can be done with relaxed ordering. > But a ring buffer suffers from none of these overheads. This is not quiet accurate. While there are many various designs for ring-buffers -- do you want MPSC, MPMC, do you need to detect 'lapping' etc etc -- any of the variants that are thread safe that I'm aware of will have to participate in some kind of explicit memory ordering, not to mention memory reclamation.
yeahgoodok 6y ago
Can't believe this is almost a decade old. I recently tried explaining this concept during an interview and got a lot of strange looks. Most devs (even senior) were taught von Neumann architecture and assume all memory is shared. This is an excellent explainer and one I'll refer to in the future.
- brickbrd 6y ago
  What's a way to implement this in practice? Does this article imply that if 1 core was writing the value of a variable (without any locking) and other cores were simply reading the value of that variable without any locking, it will just work correctly due to underlying CPU cache coherency protocols?

70 points by jorangreef 6y ago

Wonderful stuff, as usual. And, because it's written from first principles, it holds up almost a decade later.

hpoe 6y ago

So I have heard about the idea of OOP being about passing messages between objects, rather than just calling functions with parameters but I can't seem to figure it out in a mental model. How does passing a message to an object differ from just calling an object's methods with parameters? Is there other good sources for understanding the differences and rewiring the mental model?

deleted 6y ago
[deleted]
spooneybarger 6y ago
A large part of your confusion might be that a lot of OO teaching sources define message passing as calling a function. Message passing allows for you to have the receiver of the message run in a different execution context; for example erlang. Calling an objects methods with parameters is tied to that execution context. Message passing is a larger concept than OOP. Microkernels for example are built around message passing as the means of communication.
- int_19h 6y ago
  > Calling an objects methods with parameters is tied to that execution context. Not necessarily - this depends on the language, or rather, on the object model. But consider COM or CORBA: you call a method, but the object might be on a different machine altogether.
bob1029 6y ago
When you get to a very low-level, I think one way to look at it would be to say that the most simple form of message passing is simply invoking functions with arguments which contain message data. Most people probably go straight into the multi-node pub/sub universe when "messaging" starts being thrown around, but it could just as well be direct method invocation with objects in the single node/process case. The nuance and complexity seems to come from where those messages are stored, and how access to them (or knowledge of their availability).
ncmncm 6y ago
Ultimately there is no real difference between function calls and message-passing. It is a matter of emphasis. When you design with message-passing in mind, you don't expect an immediate answer to the message; instead, you expect to get an answer as another message. In some cases, this adds overhead: two messages, vs one function call. In others, you can do something else useful immediately after sending the message, and handle the return message whenever it arrives, maybe much later. It is common to overlay a function calling mechanism on top of message passing. This is called "RPC", and is often a bad idea. The failure modes of message systems differ from those for function calls, so that assuptions higher up in the abstraction tend to be wrong.
deleted 6y ago
[deleted]
ben509 6y ago
I seen various descriptions of message passing in OOP that wind up meaning "invoke a method, alter an object, return an answer." Lots of different ways to describe a method, lots of ways to modify the object, lots of ways to return an answer, but conceptually, they're all just invoking a method. I think in some languages and frameworks, message passing is associated with expressing a GUI, so objects have handlers for events, and there is more structure around how events can be signalled and handled. I'm thinking of Smalltalk, Hypercard and modern browsers. It's also more distinct in concurrent programming with something like communicating sequential processes (CSP), where message passing is a way for concurrent processes to agree on how to share state. So when process A writes some data to a channel C it explicitly hands that data off, thus process B can read from C and operate on the data without corrupting anything. (Contrast with threads where you can modify anything, any time, so you have to use locks and deal with deadlock and such.)
gens 6y ago
Checking out what Alan Kay has to say about it might help: https://www.youtube.com/watch?v=fhOHn9TClXY https://www.youtube.com/watch?v=fhOHn9TClXY The way i see it OOP is about encapsulating/bundling data and the code that processes that data into one "object", that is isolated from other objects. The objects could only "communicate" with other objects by sending "messages" (data/events/something). Personally i don't like OOP, and think that focusing on data and how it's processed is a better way forward (CSP and such). It's.. a complicated matter.
jorangreef 6y ago
Passing a message is immutable for starters, which means read-only access for the receiving process, enforcing the single-writer principle.
mercer 6y ago
I think one important difference is that if you call a method, things fail when the method doesn't exist, or the wrong arguments are passed. With message passing, the callee can decide not to respond to a message. Or to respond at a later time. In a broader sense, I'd say the difference is between pressing a button on a robot that 'forces' it to walk, or asking said robot to please go and walk. In the former case, you're essentially reaching 'into' the robot's behavior via an exposed control. The caller is in charge. In the latter case you have no control and the callee, the robot, has the freedom to decide what to do and when to do it.
polyglotfacto 6y ago
Calling a method on an object could potentially alter the internal state of that object. So in the context of some sort of concurrent execution, calling a method implies first of all having a direct reference to the object from the thread of execution where the method call occurs, and then it also implies having to synchronize potential state changes(writes) with other threads of execution who might also have a reference to the object and call methods on it. On the other hand, sending a message would allow for only a single thread of execution owning that object, and calling methods on the object in response to incoming messages. So I'd say it's not really "sending a message to an object", it's rather "sending a message to some kind of thread of execution, which owns that object uniquely". Result: there is a "single writer" with regards to the internal state of that object. I actually wrote an article on this for Rust, perhaps it could help rewiring your mental model: https://medium.com/@polyglot_factotum/rust-concurrency-the-single-writer-principle-applied-aada2cdc6fb0 https://medium.com/@polyglot_factotum/rust-concurrency-the-s...

dang 6y ago

Discussed just a bit at the time: https://news.ycombinator.com/item?id=3219193 https://news.ycombinator.com/item?id=3219193

ncmncm 6y ago

This principle is the basis for the extremely better throughput of ring buffers over other so-called "lock-free" queue structures. Things labeled "lock-free" typically are not; instead, they rely on locks at the hardware level that are subject to the same sort of contention seen with software-visible locks, such as mutexes, and the same sort of stalls, with just smaller numbers. So, a lock-free queue is often little faster than a locking one. But a ring buffer suffers from none of these overheads. The reader has to be sure to keep up with the writer, over a short enough time scale not to "get lapped"; but you need that anyway.

troutwine 6y ago
> Things labeled "lock-free" typically are not; instead, they rely on locks at the hardware level that are subject to the same sort of contention seen with software-visible locks, such as mutexes, and the same sort of stalls, with just smaller numbers. This isn't quite true. The 'hardware level lock' you're referring to are memory ordering primitives that allow you to coordinate threads of execution in a way that allows them to see memory operations in sequences that come to the same thing. Your notion of a software-visible lock is a construct built out of these primitives: the simplest mutex is an Acquire/Release pair. The difference might seem subtle -- and it is -- but it's very important. A lock requires that all coordinated threads operate in lockstep with one another at some point in their execution. A lock-free structure does not. A lock-free structure will be built to allow coordinated threads to see memory in ways that come to the same thing but in ways that don't require lock-step. A subclass of these kinds of structures are lock-free/wait-free, that is, they provably do not have any 'stalls' where coordinated threads must wait for the forward-progress of one of their cohort before they can operate, if I understand correctly what you're referring to as a stall. I do however acknowledge that x86 will coordinate your threads in some cases because of it's strong consistency guarantees. That is a complication. > So, a lock-free queue is often little faster than a locking one. This strongly, strongly depends on the environment you're running in and the nature of your queues, how over-contended your structures are. OS provided locks will often have hooks into the scheduler, which is a significant win over naive user-space spins. That's not to say you can't signal the scheduler yourself about being unable to proceed, and this is often done. I will readily admit that lock-free structures -- especially wait-free -- are specialty structures and you're almost surely better off starting with a traditional locking structure, unless everything you're doing can be done with relaxed ordering. > But a ring buffer suffers from none of these overheads. This is not quiet accurate. While there are many various designs for ring-buffers -- do you want MPSC, MPMC, do you need to detect 'lapping' etc etc -- any of the variants that are thread safe that I'm aware of will have to participate in some kind of explicit memory ordering, not to mention memory reclamation.

yeahgoodok 6y ago

Can't believe this is almost a decade old. I recently tried explaining this concept during an interview and got a lot of strange looks. Most devs (even senior) were taught von Neumann architecture and assume all memory is shared. This is an excellent explainer and one I'll refer to in the future.

brickbrd 6y ago
What's a way to implement this in practice? Does this article imply that if 1 core was writing the value of a variable (without any locking) and other cores were simply reading the value of that variable without any locking, it will just work correctly due to underlying CPU cache coherency protocols?