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.