[go-nuts] A question about Go Memory Model

You're confusing program (sequence of statements) execution and CPU
(sequence of machine instruction codes w/ the appropriate
memory/register effects) execution. The docs sentence is about the
former. The observed changes to a are again from the program point of
view. Moreover, a channel operation is not equal to a simple memory
operation, so even the "CPU" (write) reordering is not (generally)
applicable.

Roughly: The memory model specs in this case forces the compiler
writer to flush 'a' to memory if it happens to be in a register only
before that. That is legal as long as there's no sync by channel
communication (or atomic or lock operations, IIRC).

-j

I think I'm not confusing. And you answered the question:
"Moreover, a channel operation is not equal to a simple memory
operation, so even the "CPU" (write) reordering is not (generally)
applicable. "

在 2013年2月26日星期二UTC+8下午8时51分16秒，Jan Mercl写道：

See "http://golang.org/ref/mem", which describes which operations
force memory synchronization between goroutines. There are two
main events that force memory synchronization (a "memory fence"
operation at the CPU level):

- Receive on a channel.
- Unlock on a mutex lock.

Note that merely sending does not force synchronization;
someone has to receive.

Similarly, it's not mutex locking that triggers synchronization;
it's unlocking. Entering a locked section of code and accessing
shared data which was modified outside a locked section
from another goroutine creates a potential race condition.

This is very real in Go. There are programs which demo
these race conditions on multiple-CPU machines.

John Nagle

On Tue, Feb 26, 2013 at 8:00 PM, John Nagle wrote:

I don't agree with your view of that document. You have bashed the
same/similar thing about Go in dozens of threads and I refuse to go
into the same details again. Just check the compilers sources for your
self, its FOSS and it is worth of the study.

Anyway, Go is broken in your eyes, so let it be. Perhaps there is some
other language which isn't and you can enlighten its mailing list
instead.

-j

You are free to cease writing.

Go users need to know that race conditions are possible and how
to prevent them. It's not hard. The rather dense Go Memory Model
paper can be summarized for users as:

There are only a few events that force memory synchronization:

- Receive on a channel.
- Unlock on a mutex lock.

If a variable has been changed by one goroutine, you must do
one of those before accessing that variable in another goroutine.

John Nagle

Some Go users are aware of that _races in the implementation are
possible_ years before you discovered the existence of the Go
programming language (http://research.swtch.com/gorace).

Though you're consistently "teaching" that it is the problem of the
language, which is not true.
Go users are not dependent on you to teach them. Especially not when
the teaching is incorrect.
It's simply not what is in the talked about document and AFAICS it is
not true. Please cite the document relevant parts and correctly derive
your result.
Not true. Let's return to the OP problem and let's look what the
document has to say about it:

[Q]
"The write to a happens before the send on c, which happens before the
corresponding receive on c completes, which happens before the print."
[/Q]

It not "dense". Before the send on 'c' the write to 'a' has happened.
I.e. if 'a' was for example held in a register (unsynced), it was
expelled to memory before the send to c happened.

I might be wrong, the doc might be wrong, of course. Just point out
where the mistake is, please.

TIA

-j

PS: The other, receiving side is simple as well, but let's first
figure out the "The write to a happens before the send on c" thing
before going any further, ok?

If it wasn't a problem, the Go Playground and Google AppEngine
wouldn't be locked down to single-thread.
That comes from the statements in "http://golang.org/ref/mem":

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

"A send on a channel happens before the corresponding receive from that
channel completes."

"For any sync.Mutex or sync.RWMutex variable l and n < m, call n of
l.Unlock() happens before call m of l.Lock() returns."

Therefore, the user is guaranteed sequential operations from one
goroutine to another if a channel receive intervenes. The receive
is the synchronizing operation, not the send. Similarly, Unlock
(or really, return from Lock) is the synchronizing operation,
not Lock. This is as it should be.

Mercl is right, though; I'm oversimplifying. If one goroutine
sends to a channel that has some items queued, and the receiver gets
an item that was already in the channel, a Go implementation is not
strictly required to synchronize memory up to the last send to the
channel, only to the state at the time the item being read
entered the channel. In practice an implementation probably
does a global memory fence operation on each channel receive,
but the spec is a bit looser than that.

How strict is Go's race detector about this? Does it track
state through channel queues, or does it just treat some
events as a commit?

(I once spent several years fixing a major mainframe operating
system by reading crash dumps from production machines.
This makes one very aware of race conditions as defects.
I never want to do that again.)

John Nagle

Makes me wonder if the difference between a language and its
implementation is somehow incomprehensible?
The guarantees are both stricter and simpler (in the first approximation).

As we haven't yet gone through this point, it probably has to be repeated:

[Q]
"The write to a happens before the send on c, which happens before the
corresponding receive on c completes, which happens before the print."
[/Q]

The write to 'a' happens before send on 'c', so a channel receive has
nothing (yet) to do with it. That's stricter, b/c it means that after
a send on 'c', 'a' is already in a correct state. It's simpler, b/c
the channel read is not required for "write to 'a' _happen before_
send on 'c'". The send on 'c' means 'a' is now in sync with the code
(`a = <expression>`).

Let me postpone discussion of the situation in the receiving goroutine
to the moment when this is figured out first.

-j

John is actually correct. The important part is the first line of the
model: they are defining a partial ordering on statements called "foo"
<tabooing mention of time because
it is misleading.> They then define a relation bar between writes and
reads. A read is bar with a write if the read is foo with respect to a
write and there is no other write
that is foo with the given write to which the read is foo. A read is bax
with a write if it is bar with a write and all other writes are foo to the
write or the read is foo to them.

In a single goroutine the foo relation subsumes textual ordering. However,
there is no guarantee that foo is a total ordering, and so it is only
necessary that the result of a write is reflected in reads that are foo to
it, so it suffices to commit it chronologically before the read that is foo
to it.

This is pedantic, but necessary. In particular if we have the following set
of relations:
A foo B
A foo C
B foo D
C foo E
D foo F
E foo F

Then it is not the case that either B foo E or E foo B, while in the total
ordering case this is correct. In particular a single-threaded
implementation would have this work
with foo defined as chronology, while a multiply threaded one could do
anything.

Sincerely,
Watson Ladd

the write to a happends before the "c <- 0"
no, after "go f()", the program can continue to "<-c", and can continue on
to "print(a)" before the a = "hello, world"
because your channel is buffered for 10 entries.

at the "print(a)", it MAY have assigned a, but it MAY NOT have.

Regards,

Rob Lapensee

incorrect. how can it continue past "<-c" if "c <- 0" doesn't happen before
it?
are you asserting the example in the official Go memory model is wrong?

sorry, my bad,
I had "which is send" and "which is receive' backwords.

No. No receive from a channel before a send to it can even happen.
Buffered or not.

-j

1. the processor (CPU) never reorders code, just pipeline or parallel at
most
2. the compiler may reorder (the generated code of) some statements only
if,
3. the generated code is logically equivallent to the original one

Hope this help.

David

"the processor (CPU) never reorders code, just pipeline or parallel at
most".
So these two a = "hello, world" and c <- 0 may parallel execute at same
time if go doesn't guarantee it.
I want to know if "The write to a happens before the send on c" is go
memory model spec guarantee.

在 2013年2月27日星期三UTC+8上午11时18分11秒，David DENG写道：

Go compiler and the CPU both guarantee no matter what they do(reordering,
parallel, pipeline), the *results* are just as expected.

David

Yes, see section 2 of the Go Memory Model, in particular
"Within a single goroutine, the happens-before order is the order expressed
by the program."
Since the assignment and the send are in the same goroutine, the assignment
happens-before the send.
Sincerely,
Watson Ladd

code, and on most CPUs loads and stores can complete after arithmetic
operations
that are dispached later. On some superscalar designs there is no global
ordering of instructions, because each operational unit has its own queue
of operations,
and magic keeps the results consistent. Any CPU that does not have precise
exceptions at all times does not have a concept of time in which
instructions are externally
visible or not depending on whether before or after a point in the
instruction sequence, and most CPU architectures do not for increased
performance.

As for compilers, the real question is what is logically equivalent.
Peterson's algorithm is not guarantied in Go to work.

1. Ok. Sorry for the first statement, I do not know much about different
kinda CPUs . :-P. But CPU, in my mind, is always in the way I just
mentioned. Only the writers of compiler has to make people like me happy
even the CPU makes them unhappy.

2. This statement needs to be further clarified: logically equivallent see
from the same thread or go-routine. From outside of the go-routine, it
could be different. That's what memory modle is about.

David

CPU makes everyone happy if it is fast. I am betting your cpu is mixing up
your instructions as well
http://en.wikipedia.org/wiki/Out_of_order_execution.
I think the only common in-order cpus go (gc at least) supports are the
older arms.
Intel's Atom (everything but the newest models?) are in-order as well (from
my memory, could be wrong)

I am curious if anyone has go working on a system with less memory
coherency than x86.

The memory model specifies how a Go program must behave, regardless of what
kind of CPU is being used.

The details of what the CPU does and what it needs to be told to do or not
to do are concerns for the Go implementation alone.

Russ