Re: [go-nuts] Re: locks and "happens before" withing a goroutine

[Jesper Louis Andersen]

On Thu, Dec 1, 2016 at 10:38 AM Daniel Fanjul <
daniel.fanjul.alcu...@gmail.com> wrote:

>
> > Inside a single goroutine the code proceeds in statement order.
> The code generated by the compiler, right? Of course, it is typically the
> processor who reorders. But what is the limit of the reorder?
>

The memory model describes a "virtual" CPU which happens to execute
operations in-order for each go-routine. Further it sets up a (causal)
happens-before relationship when synchronizing several goroutines and their
in-order execution. In short, the memory model is a pure logical
construction, not bound to real hardware.

In Computer Science, people tend to belong to either the "theory" side of
things, where you describe algorithms and phenomenon purely detached from
the underlying hardware. Or you belong to the "practical" side of things,
where the hardware is central and you build up the logic from what is
possible with the hardware.

The memory model is where these two worlds meet.

The task for a compiler/runtime writer is to take the virtual model, and
map it onto real hardware. We are allowed a certain amount of leverage
here, as long as we make sure we obey the memory model in the end.
Specifically:

* We can allow the CPU to reorder memory writes, as long as we make sure
there is a memory-barrier instruction inserted in the right place by the
compiler or runtime

* We can allow the compiler to reorder instructions as well, as long as we
have a proof that the reordering preserves the semantics of the program.
Again, we would have to insert a memory barrier in places.

But note if we compile Go to hardware which has in-order execution, one
core, and where there is no cache and no coherency problems, we don't have
to insert a memory-barrier. Hence, the memory model is best written to not
contain a word such as "memory barrier". They are artifacts of the
"practical" hardware, not of the "theoretic" memory-model.

The happens-before relation defines a causal relation between different
goroutines. This is powerful since this is where the leverage is hidden: we
can have a goroutine run as a "soup" of reorderings in limbo until
communication happens. At the point of rendezvous the happens-before
relationship "locks down" the soup and makes sure it is in the right order.
This is often ensured via a memory barrier instruction (or one which that
side-effect). Since we can reorder freely until lock-down occur, we can
optimize code by simultaneous execution of independent statements
(out-of-order execution via Tomasulo's algorithm).

The key is that this actually models the real world. You may get a summary
of a meeting with the findings, but you don't care too much about what was
discussed in the meeting in order to reach those findings. In short, the
discussions are allowed "reordering" leverage, as long as the findings are
locked down in the summary when you hear about them. I.e., there is a
memory barrier happening at the end of the meeting.

Another real world example, of a causal violation this time, is when you
have an image service such as Instagram, Google Images, Snapchat, ...,
where a person first blocks a recipient and then posts an image to
everyone. Because the block happens-before the post, you don't want that
image to end up in the inbox of the blocked person. But if you violate the
causal dependency, then that is exactly what might happen: the image gets
posted first, then the block is instated. Many distributed systems violate
these orderings unless you are careful.

So what is the limit of the memory reorder? The limit is that the causal
(happen-before) consistency must not be violated. You are allowed, as in
the meeting example, to have a *local* violation, as long as external
observers are not able to see that local violation. This allows you to
optimize programs for efficiency, which is a good thing[0]. But that is all
you are allowed.

[0] There is an interesting observation here: local violations
as-long-as-observers-cannot-see-it is the central aspect of APIs and
interfaces. Which has similarity to assuming the truth of a theorem or
lemma in mathematics. Give a module a (purely) functional interface, but in
the actual implementation, use every imperative programming speed trick you
know of, violating FP in the process. The program is still "functional",
though it allows you to violate that property locally.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: locks and "happens before" withing a goroutine

[Daniel Fanjul]

> Within a single goroutine, the happens-before order is the order 
expressed by the program. 
If this is true, why is the order of 'a = 1; b = 2;' not ensured?
I think you may be forgetting that "compilers and processors may reorder 
the reads and writes executed within a single goroutine"

> Inside a single goroutine the code proceeds in statement order. 
The code generated by the compiler, right? Of course, it is typically the 
processor who reorders. But what is the limit of the reorder? Is 'a = 1; b 
= 2;' so simple that we worry about this case, but is 'a = 1; x.Lock(); b = 
2;' so complex that we assume that it will never be reordered? Now I see it 
is because we assume it is a memory barrier though it is undocumented. 
Thanks, Ian, I am sure now it is undocumented.

> - a = "hello, world" happens-before l.Unlock() 
That is false unless l.Unlock() is memory barrier or some other 
restriction. It happens it is a barrier, so you can say it truly happens 
before. The spec or the memory model does not mention it, so technically we 
cannot state it because of the spec or the memory model.

> If it didn't chaos would ensue, it would be as if statements in a 
function were executed in random order.
In theory, the statements are allowed to run in any order but only "when 
the reordering does not change the behavior within that goroutine as 
defined by the language specification", that is "when reads and writes must 
behave as if they executed in the order specified by the program". But I 
agree with you, Dave, in practice the deviation is small.

> I agree that this fact is not documented, but it is true nonetheless. 
Cool, thank you. I think it is quite important and really necessary to 
understand the memory model. Otherwise its examples do not make sense at 
all.

Thank you all, I finally and completely understood the memory model.


On Thursday, December 1, 2016 at 7:15:45 AM UTC+1, Ian Lance Taylor wrote:
>
> On Wed, Nov 30, 2016 at 5:44 PM, Daniel Fanjul 
>  wrote: 
> > I cannot tell if there is any memory barrier in the code of 
> > sync.RWMutex.Lock(), I don't understand it completely. I just think 
> there is 
> > not. 
> > https://golang.org/src/sync/mutex.go?s=1143:1165#L34 
>
> The sync/atomic routines provides memory barriers. 
>
> I agree that this fact is not documented, but it is true nonetheless. 
>
> Ian 
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: locks and "happens before" withing a goroutine

[Ian Lance Taylor]

On Wed, Nov 30, 2016 at 5:44 PM, Daniel Fanjul
 wrote:
> I cannot tell if there is any memory barrier in the code of
> sync.RWMutex.Lock(), I don't understand it completely. I just think there is
> not.
> https://golang.org/src/sync/mutex.go?s=1143:1165#L34

The sync/atomic routines provides memory barriers.

I agree that this fact is not documented, but it is true nonetheless.

Ian

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: locks and "happens before" withing a goroutine

[Dave Cheney]

Inside a single goroutine the code proceeds in statement order. If it didn't 
chaos would ensue, it would be as if statements in a function were executed in 
random order.

However, from the view of another goroutine, without synchronising operations 
like channel sends and receives, or agreeing in a critical section via a mutex, 
this random order is precisely what abother goroutine perceives. 

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: locks and "happens before" withing a goroutine

[Caleb Spare]

I think the bit you're missing is this:

> Within a single goroutine, the happens-before order is the order expressed by 
> the program.

That is, there is an implicit happens-before between each successive
statement *within a single goroutine*.

So in the example:

- the first l.Lock() happens-before go f()
- by the memory model rules for goroutine creation; go f()
happens-before f executes
- a = "hello, world" happens-before l.Unlock()
- by the memory model rules for locks, the first (only) l.Unlock()
happens-before the second l.Lock()
- the second l.Lock() happens-before print(a)
- therefore, transitively, a = "hello-world" happens-before print(a)

-Caleb





On Wed, Nov 30, 2016 at 5:40 PM, Daniel Fanjul
 wrote:
> I think the current implementations of the methods of sync.RWMutex happen to
> be actual memory barriers and this is why everything works just fine.
>
> But I don't think the spec or the memory model or the doc of sync mentions
> this.
>
> If this is not described, the example in the memory model for the locks is
> wrong:
>
>// https://play.golang.org/p/pmhbeyn_wZ
>
> var l sync.Mutex
> var a string
>
> func f() {
> a = "hello, world"
> l.Unlock()
> }
>
> func main() {
> l.Lock()
> go f()
> l.Lock()
> print(a)
> }
>
>
> The statements in f() might be reordered to run l.Unlock() first and then
> the assignment. The code would not guarantee to print "hello, world" at the
> end.
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Re: locks and "happens before" withing a goroutine

[Daniel Fanjul]

I cannot tell if there is any memory barrier in the code of 
sync.RWMutex.Lock(), I don't understand it completely. I just think there 
is not.
https://golang.org/src/sync/mutex.go?s=1143:1165#L34


-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Re: locks and "happens before" withing a goroutine

[Daniel Fanjul]

I think the current implementations of the methods of sync.RWMutex happen 
to be actual memory barriers  
and this is why everything works just fine.

But I don't think the spec or the memory model or the doc of sync mentions 
this.

If this is not described, the example in the memory model for the locks is 
wrong:

   // https://play.golang.org/p/pmhbeyn_wZ

var l sync.Mutex
var a string

func f() {
a = "hello, world"
l.Unlock()
}

func main() {
l.Lock()
go f()
l.Lock()
print(a)
}

 
The statements in f() might be reordered to run l.Unlock() first and then 
the assignment. The code would not guarantee to print "hello, world" at the 
end.

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.