Erlang

lists.md

List

Internal implementation

Erlang list is a singly linked list. Each item has a size of 2 Eterm: one for storing value, second for storing the pointer to next item.

When you append new element to the list:

• is created a new copy
• and then to the last element is set the pointer to list that needed to append

erl_bif_lists.c

static BIF_RETTYPE append(Process* p, Eterm A, Eterm B)
{
    ...

    need = 2 * erts_list_length(A);
    // allocate memory for new list
    hp = HAlloc(p, need);
    list = A;
    // creating new list for appending
    copy = last = CONS(hp, CAR(list_val(list)), make_list(hp+2));
    list = CDR(list_val(list));
    hp += 2;
    i--;
    // copying items 
    while(i--) {
        Eterm* listp = list_val(list);
        last = CONS(hp, CAR(listp), make_list(hp+2));
        list = CDR(listp);
        hp += 2;
    }
    // set the pointer to list that needed to append 
    CDR(list_val(last)) = B;
    BIF_RET(copy);
}

erl_term.h

#define list_val(x)     ((Eterm*) EXPAND_POINTER((x) - TAG_PRIMARY_LIST))
#define make_list(x)    ((Uint) COMPRESS_POINTER(x) + TAG_PRIMARY_LIST)

#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 - returns an Eterm tagged as a list from a pointer on the process heap
• list_val - returns the address on the heap of the list from Eterm

Performance for append element to list

lists:foreach(fun(N) ->
    L = lists:seq(1, 100000*N),
    {Time, _} = timer:tc(lists, append, [L, [1]]),
    io:format("~w ~p~n", [100000*N, Time*1.0e-3])
end, lists:seq(1, 50)).