| by suyi | No comments

Erlang:详解字符串连接

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

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

%% 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

/*
 * 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。

#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一个指向元组的指针:它存储在堆中的位置。

使用

对于有!发生消息时,应该使用 binaryIoList尽可能。IoList为iolist = [char() | binary() | iolist()]

发表评论