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.

* 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.

Reply via email to