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.
