Why you shouldn't concatenate strings in erlang

In the previous article, I said that concatenating strings was an O(n) operation on the length of the first string.

I feel the need to explain that.

In erlang, strings are lists of integer. Since they are integers, they can store any unicode characters such as the snowman ☃ which has a value of 9731.

When one wants to concatenate 2 strings, one can use string:concat/2 implemented in lib/stdlib/src/string.erl as follows:

(All code extracts in this article are subject to the Erlang Public License.)

    %% concat(String1, String2)
    %%  Concatenate 2 strings.

    -spec concat(String1, String2) -> String3 when
          String1 :: string(),
          String2 :: string(),
          String3 :: string().

    concat(S1, S2) -> S1 ++ S2.

Ok, strings are lists, just concatenate lists!

Down the rabbit hole

The ++ operator is a BIF, a Built-In Function implemented in C in the Beam VM. It is implemented in erts/emulator/beam/erl_bif_lists.c.

1 /*
2 * erlang:'++'/2
3 */
4
5 Eterm
6 ebif_plusplus_2(BIF_ALIST_2)
7 {
8 return append(BIF_P, BIF_ARG_1, BIF_ARG_2);
9 }
10
11 static BIF_RETTYPE append(Process* p, Eterm A, Eterm B)
12 {
13 Eterm list;
14 Eterm copy;
15 Eterm last;
16 size_t need;
17 Eterm* hp;
18 int i;
19
20 if ((i = list_length(A)) < 0) {
21 BIF_ERROR(p, BADARG);
22 }
23 if (i == 0) {
24 BIF_RET(B);
25 } else if (is_nil(B)) {
26 BIF_RET(A);
27 }
28
29 need = 2*i;
30 hp = HAlloc(p, need);
31 list = A;
32 copy = last = CONS(hp, CAR(list_val(list)), make_list(hp+2));
33 list = CDR(list_val(list));
34 hp += 2;
35 i--;
36 while(i--) {
37 Eterm* listp = list_val(list);
38 last = CONS(hp, CAR(listp), make_list(hp+2));
39 list = CDR(listp);
40 hp += 2;
41 }
42 CDR(list_val(last)) = B;
43 BIF_RET(copy);
44 }

First, the length of A is computed. This operation is O(n) where n is the length of the list. Trust me on this one, of just go look at erts/emulator/beam/utils.c.

If either lists are empty, return the other one.

On lines 29 - 30, space is allocated on the process heap for a new list. Each list item has a size of 2 Eterm: one for the list itself, one for the element.

The code on lines 31 to 42 just copies A to our newly allocated list and adds B on its tail.

last = CONS(hp, CAR(list_val(list)), make_list(hp+2));

Ok, what is that?

From erts/emulator/beam/erl_term.h, we need some more definitions:

    #define CONS(hp, car, cdr) \
            (CAR(hp)=(car), CDR(hp)=(cdr), make_list(hp))
    
    #define CAR(x)  ((x)[0])
    #define CDR(x)  ((x)[1])

make_list is used to return an Eterm tagged as a list from a pointer on the process heap.

list_val does the opposite and returns the address on the heap of the list.

CONS puts 2 elements in hp[0] (the element in the list) and hp[1] (the next list item) and returns the list at hp as an Eterm.

That complicated expression can now be read as:

When list A has been fully copied, the last element is set to B at the line 42 with CDR(list_val(last)) = B;.

Memory allocation

If you’re curious, erts/emulator/beam/sys.h can tell you that an Eterm has usually a size of 4 bytes.

Small integers can be stored directly in those 4 bytes. There are 26 bits usable to store a small integer so it can store up to 2²⁵ = 33554432 because of the sign bit. For reference, pile of poo which was added in october 2010 has a value of 128169.

We can consider that unicode characters can be stored directly in the list.

If a string has n characters, it will use 2 * n words.

A binary on the opposite will use 3 to 6 words (depending on the data size) plus the size of the data itself.

A string stored as a list takes about 8 times the space it would take stored as a binary.

What about other lists?

The pointed values are not copied, only the list items themsleves.

Appending a list of records of n tuples to a list of m tuples will take the same time/memory as concatenating a string of length n to one of length m.

The only difference is that tuples are not boxed in an Eterm. The list only contains an Eterm as a pointer to the tuple: where it’s stored in the heap.

Solution?

Of course there is one! You should use binary and IoList whenever possible. An IoList is iolist = [char() | binary() | iolist()]. They are “deep-list”.

Want to append an IoList a to an IoList b? Simple! Just create a new list with 2 elements: a and b! Concatenation has become an O(1) operation. Most IO apis accept IoLists.