Erlang:详解字符串连接

在erlang中，字符串是整数列表。因为它们是整数，所以它们可以存储任何unicode字符。

当想要连接2个字符串时，可以使用 如下string:concat/2实现：
 lib/stdlib/src/string.erl

1
2
3
4
5
6
7
8
9
%% concat(String1, String2)
%%  Concatenate 2 strings.

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

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

另一种++操作是一个BIF，在C中实现的内置函数 erts/emulator/beam/erl_bif_lists.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
 * erlang:'++'/2
 */

Eterm
ebif_plusplus_2(BIF_ALIST_2)
{
    return append(BIF_P, BIF_ARG_1, BIF_ARG_2);
}

static BIF_RETTYPE append(Process* p, Eterm A, Eterm B)
{
    Eterm list;
    Eterm copy;
    Eterm last;
    size_t need;
    Eterm* hp;
    int i;

    if ((i = list_length(A)) < 0) {
        BIF_ERROR(p, BADARG);
    }
    if (i == 0) {
        BIF_RET(B);
    } else if (is_nil(B)) {
        BIF_RET(A);
    }

    need = 2*i;
    hp = HAlloc(p, need);
    list = A;
    copy = last = CONS(hp, CAR(list_val(list)), make_list(hp+2));
    list = CDR(list_val(list));
    hp += 2;
    i--;
    while(i--) {
        Eterm* listp = list_val(list);
        last = CONS(hp, CAR(listp), make_list(hp+2));
        list = CDR(listp);
        hp += 2;
    }
    CDR(list_val(last)) = B;
    BIF_RET(copy);
}

首先，A计算长度。此操作是O(n)这里n是列表的长度(
erts/emulator/beam/utils.c)。如果任一列表为空，则返回另一个列表。

在进程堆上为新列表分配空间。每个列表项的大小为2 Eterm：列表本身为1，元素为1。最后只是复制A到新分配的列表并在其尾部添加B。

对于last = CONS(hp, CAR(list_val(list)), make_list(hp+2))， 定义在： erts/emulator/beam/erl_term.h。

1
2
3
4
5
#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用于Eterm从进程堆上的指针返回标记为列表的列表。list_val 相反并返回列表堆上的地址。CONS将2个元素放入hp[0] （列表中的元素）和hp[1]（下一个列表项）并返回列表hp作为Eterm。这个复杂的表达现在可以解读为：

  • 复制到hp[0]要复制的列表的元素中
  • 由于新列表被分配为堆栈中的一个块，因此Eterm 在stack（hp+2）上将下一个列表项设置为以下内容

列表A完全复制后，最后一个元素设置为B即 CDR(list_val(last)) = B。

内存分配

一个通常字符有4个字节的大小。 erts/emulator/beam/sys.hEterm。 小整数可以直接存储在这4个字节中。有26位可用于存储一个小整数，因此可以存储多达2²⁵= 33554432。我们可以认为unicode字符可以直接存储在列表中。 如果一个字符串有n字符，它将使用 2 * n单词。binary相反的A 将使用3到6个字（取决于数据大小）加上数据本身的大小。存储为列表的字符串大约占存储为a的空间的8倍binary。

对于其他的， 不会复制指向的值，只会复制列表项。 将n元组记录列表附加到元组列表m将花费相同的时间/内存，如将长度字符串连接n到一个长度字符串 m。 唯一的区别是元组没有封装 Eterm。该列表仅包含 Eterm一个_指向_元组的_指针_：它存储在堆中的位置。

使用

对于有！发生消息时，应该使用 binary和IoList尽可能。IoList为iolist = [char() binary() iolist()]。