Erlangs message passing

In the programming language Erlang[0], there are functionality to pass messages between processes. This feature is used to implement communication and synchronization between different concurrent activities in an Erlang system. Other languages implement somewhat the same functionality with slightly different semantics. But in most cases, you can implement one of the semantic styles in the other style, so they are not that different in practice. Haskell has STM and MVars for instance, Golang and the Standard ML CML extension has channels, and so on.

The current major implementation of the Erlang language, called the BEAM VM, implements message passing via copying. This sets the implementation apart from almost any other language out there. Most implementations have chosen to pass values between processes by reference. The reason seems strikingly obvious: passing by a reference is much faster than to copy values between processes.
I want to stress that there is nothing in the Erlang semantics which mandate that you copy data around. You could equally well keep the current semantics and opt to just pass values by reference between processes. So if it turns out that we—in the long run—win by using references over copying, we can just change to do exactly that.

One might wonder, why the BEAM VM opts to copying around data rather than passing it by reference. Of course, it boils down to the same thing as always: tradeoffs. There is much to be gained by copying.

Embracing copying

The secret to the success of the BEAM VM is its choice of copying messages around. The sacrifice you make is the ability to pass references. However, that sacrifice pays for itself in the long run in many ways, when you begin to think about the implications of picking a different strategy.

First of all, modern computers are good at copying data. In fact, they are extremely good at tossing data around. Most of the time is spent on copying data between caches anyway, for modern complicated programs. A correctly structured Erlang program will usually only copy some 100 bytes per message, which will quickly be transferred between processes. And so it turns out that there is an overhead to copying data around, but the overhead is much smaller than what people usually expect it to be. The behaviour has been known from around the 90'es, from the high allocation rates of functional languages in general. And copying a message is much like having a high allocation rate.

Second, there is one type of data in the BEAM VM which is passed by reference: binaries above a certain size (64 bytes). When you allocate, say, a 1 megabyte binary it is allocated in a separate memory arena, and you are only passing a pointer to that binary. Note that binaries can not contain pointers themselves, and furthermore, they are also immutable. Since there are no pointers, you don't have to worry about binaries pointing to other data. They are always "leaf nodes" in an Erlang term. This and immutability allows the VM to reuse the same binary in multiple processes. It also allows the VM to make sub-binaries that references inside the 1 megabyte chunk. If you do e.g., binary:split/3 to split a binary into parts, you just get these sub-binary references into the original binary. Other languages provide roughly the same primitives. Slices in Golang are like this, but they allow you to mutate the contents. This wouldn't work in Erlang, since data is immutable in general. Slices in Standard ML are more like the sub-binaries in the BEAM VM. In general it leads to excellent read-only memory reuse.
Copying means that you have the same operational behaviour, even if you are sending a message to another distributed node() running on another machine. Or if you have a NUMA architecture where you have to send the message into the memory bank of another CPU core. If modern CPUs lost cache coherency, it would pose no problem to the semantics of Erlang programs. They are fully forwards compatible in case it happens.

Copying means that you have full process isolation. When you send a message (locally) in Erlang the following happens:

• You allocate a target memory space in the sending process
• You copy the message to that memory space
• You take the external lock on the target process
• You link your memory space into the mailbox linked list
• You release the external lock on the target process

Note that you hold the external lock for a couple of pointer moves. Also note that the process itself has other locks which are the only locks which are needed for normal operation, so you don't block the target process. Once in a while, the target process takes the external lock and internalizes the mailbox. This is too a few pointer moves. It can then munge on that part of the mailbox at its own leisure and speed, not affecting other senders. The messages in the mailbox is considered part of the process heap.

Full process isolation means that a process can have its own heap and stack. The most important consequence is that if a process crashes or incorrectly handles memory, only that process can be affected. There is no way a library written by a Junior programmer can go havoc and make arbitrary memory corruption in the system. You can safely add modules and libraries and be sure they are limited in what amount of error they can cause in the running system. For large programs, this feature is necessary.

Since each process has its own heap and stack, it can run GC independently on every process. Since process heaps are usually small, the GC pause time is not noticable. This property makes Erlang into a true soft realtime system. Also, GC can be preempted if a process has amassed a large heap—efficiently thwarthing the ability of one process to hose the system as a whole.

The isolation property also means data independence. Data can't be shared by construction and so it is easy to operate on data in parallel. Since there is no data sharing, programmers are forced to think about how to pass data around in the program, which further improves independence and parallelism of the program. A copied message is a local cache.

Each Erlang node() has another arena called ETS—the Erlang Term Storage. ETS is a place in which you can store Erlang terms and look them up by Key later. It is equivalent to a tuple space[1] (though it isn't distributed). Process stores terms in ETS by copying the term to ETS. And they retrieve terms from ETS by copying them back into their own heap before operating on them. ETS is not garbage collected. As such, it works like safe variant of manual memory management. There is no use-after-free, double free, and so on. Just memory leaks. And they can be handled by having a janitorial process to clean up after other processes. The crux is that the non-GC property means you can easily have 400 gigabyte data in ETS without having to worry about GC pause times. Again, the embracing of copying makes it all possible. A common trick in Erlang is to move some of a process data into ETS to avoid amassing a large heap for the process. This then speeds up the GC times of the process into the area of "not noticable".

Cleverly, the copying scheme also avoids the complexity of realtime pauseless garbage collection of large shared heaps. These beasts actually do exist[2], but they are not easy to implement, nor well understood. They were not understood at all when Erlang needed soft realtime guarantees, in any case. So the copying compromise were chosen instead. The VM is now simpler to implement, which leads to fewer errors and a VM that is easier to comprehend and understand.

I am inclined to say that the copying message passing in the BEAM VM is a cornerstone to the success of Erlang. Many of the safety, realtime and robustness guarantees hinges on the copying message passing design, together with data immutability and data persistence.

So as an Erlang programmer, I tend to see copying of messages as a good thing. Not a bad design decision that has to be worked around.

[0] And also in Elixir!
[1] http://en.wikipedia.org/wiki/Tuple_space
[2] http://michaelrbernste.in/2013/06/03/real-time-garbage-collection-is-real.html