Detail oriented

Ed Fine's blog.

Erlang's Internal Data Representation

I find it interesting how the Erlang BEAM engine represents data in memory.

Quick look: An Erlang list

This is the in-memory layout of the Erlang list "phi".

[112, 104, 105]

As a reminder, Erlang treats a string as a list of small integers; 'p', for instance, is 112. Don’t worry too much about the bitwise details of the diagram - we’ll cover those later on.

CAR and CDR denote the head and tail of the list, respectively (the Erlang ‘C’ source defines CAR and CDR macros, so I’ve adopted the same Lisp-y terminology).

Each of CAR, CDR, and NIL occupies one word in memory. A word is 4 bytes on a 32-bit system, and 8 bytes on a 64-bit system, so “phi” uses 2 + 2 + 2 + 1 = 7 words (28 bytes on 32-bit, and 56 bytes on 64-bit).

That’s right: 56 bytes for a 3-character string on 64-bit systems.

This is why Erlang developers routinely store strings as Erlang binaries. For more information, see the Erlang Efficiency Guide.

Let’s dig a little deeper into the memory layout.

Tagged Erlang term (Eterm)

Erlang data is represented internally by a typedef named Eterm.

An Eterm (a “tagged Erlang term”) is a data type defined in the Erlang emulator C code in sys.h. It is an unsigned integer that is chosen to be at least as large as a pointer on the architecture for which the Erlang emulator was compiled.

Tagged values are a clever way of saving memory by taking advantage of memory alignment rules, and using a word as either an immediate value or a pointer, depending on its tag.

An immediate value is a value that is in the word itself, as opposed to one obtained through pointer indirection.

A tag is a fixed number of least significant bits in the word, which are reserved for identifying attributes of the tagged data. Although this reduces the size of the data that can be stored in the word, it more than makes up for it by avoiding or reducing the overhead of pointers and descriptors.

On many CPU architectures, performance is penalized if access is made to data that is not aligned on a word boundary, that is, a 4 byte boundary on a 32-bit system, and an 8-byte boundary on a 64-bit system. This fact often drives designers of memory allocators to place data on word boundaries.

Addresses on word boundaries are even numbers that are multiples of the word size (e.g. 4, 8, 12, … on 32 bits, 8, 16, 24, … on 64 bits). This means that the addresses will have binary zeroes in their least significant bits: the least-significant 2 bits on a 32-bit system, and 3 bits on a 64-bit system. (This is because 4 in binary is 100 and 8 in binary is 1000).

Taking advantage of this, system programmers use these zero-bits to store information about the data, which could be an actual value like an integer, or it could be a pointer. When using a word, the bits are set at the time its data type is decided. If it’s a pointer type, those bits are masked off (zeroed) when the word is used (otherwise it would point to the wrong address).

Eterms in depth

There are 4 primary kinds of Eterm:

  • Header - If the data cannot fit into a word, the Eterm becomes a header, which is a descriptor of the data, followed by the variable-length data.
  • List - This is a pointer either to the first node of a list, or to the immediate value NIL. A node is a two-word array to hold CAR and CDR. CDR points either to the first node of the tail of the list, or NIL. CAR, being an Eterm, can be a List, Immediate, or Boxed value.
  • Boxed - A boxed Eterm is a pointer to a Header.
  • Immediate - If the data is small enough to fit into a word (minus the space used by the tag bits), it is called an immediate value.

Here’s my view of what the various flavors of Eterm look like for a 32-bit version of Erlang.

Note the 4 primary types we just mentioned, namely Header, List, Boxed, and Immediate. They are identified by the 2 least significant bits (for example, Header is binary 00, and Immediate is binary 11).

  • The Header type uses an extra 4 tag bits to identify 16 subtypes (only 15 are shown in the image, but BIGNUM has a sign bit, so it really has two header types).
  • The Immediate type is broken down into 4 subtypes, but one of those subtypes is called Immediate2, which is not shown but uses an extra two bits, which extends the number of immediate subtypes and sub-subtypes from 4 to 6, with one spare. The immediate types include a 28-bit small integer, which gives a signed integer range of -134217729 < i < 134217728. This is the data type used to represent a character in strings, which is why using binaries to store long strings is much more space-efficient.

Basic Erlang Data Types

We’ve already seen Erlang’s list and small integer, so let’s look at some other basic data types.

Tuple

A tuple is a fixed-size collection of values, somewhat like a struct in ‘C’.

A tuple is also a boxed value, so it consists of a Boxed pointer (1 word) to an ARITYVAL header (1 word), after which appear the elements of the tuple.

The arity part of the ARITYVAL header is a 26-bit (on a 32-bit system) integer value containing the number of elements in the tuple. It follows that the size of a tuple is 2 words + the size of the data following the header.

This is illustrated by this tuple of characters (integers, really).

{$H, $e, $l, $l, $o}

Binary

A binary is an interesting Erlang data type, because there is more than one flavor:

  • Heap: A binary that is up to 64 bytes long is created on the process heap and is not reference counted.
  • Refc: A binary that is longer than 64 bytes is created in a shared heap, and is reference counted.
  • Sub: A sub-binary is a descriptor that references a part of a binary. Two sub-binaries are created when, for example, splitting a binary.

Heap binary

A heap binary uses this data structure:

1
2
3
4
5

typedef struct erl_heap_bin {
    Eterm thing_word;		/* Subtag HEAP_BINARY_SUBTAG. */
    Uint size;			/* Binary size in bytes. */
    Eterm data[1];		/* The data in the binary. */
} ErlHeapBin;

<<"0123456789ABCDEF">>

Pid

There are two types of pid: internal and external. An internal pid refers to processes on the local node, while an external pid identifies processes on remote nodes.

Internal pid

External pid

TODO

Port

There are two types of port: internal and external. An internal port refers to a port on the local node, while an external port identifies those on remote nodes.

Internal port

External port

TODO

Combined data types

It gets interesting when we combine the data types. We’ll look at a tuple of lists, and a list of tuples.

Tuple of lists

{"phi", "eta", "rho"}

List of tuples

[{$p,$h,$i}, {$e,$t,$a}, {$r,$h,$o}]

Disclaimer

This information is based on an analysis I did of the Erlang C source code on github circa June 2016. In particular, I looked at erl_term.h and sys.h. I did my best to avoid mistakes, but I’m not an expert on Erlang internals, so YMMV.