Python内核阅读(四): 字符串对象

Python 2017-08-02

起步

在python3中,默认的字符串采用了unicode编码方式,它的结构定义为:

[unicodeobject.h]
typedef struct {
    PyCompactUnicodeObject _base;
    union {
        void *any;
        Py_UCS1 *latin1;
        Py_UCS2 *ucs2;
        Py_UCS4 *ucs4;
    } data;                     /* Canonical, smallest-form Unicode buffer */
} PyUnicodeObject;

创建 PyUnicodeObject 对象

python提供了两条路径,从C中原生字符串中创建 PyUnicodeObject 对象:

PyObject * PyUnicode_FromString(const char *u)
{
    size_t size = strlen(u);
    printf("PY_SSIZE_T_MAX = %u\n", PY_SSIZE_T_MAX);
    if (size > PY_SSIZE_T_MAX) {
        printf("size = %u\n", size);
        PyErr_SetString(PyExc_OverflowError, "input too long");
        return NULL;
    }
    return PyUnicode_DecodeUTF8Stateful(u, (Py_ssize_t)size, NULL, NULL);
}

PY_SSIZE_T_MAX 是一个与平台相关的数值,如果所创建的字符串长度超过这个值,那么python将不会创建对应的对象,在64位系统下,它的值是4 294 967 295 换算一下,4GB,确实如果不是变态,几乎不会超过这个禁区。 具体在 PyUnicode_DecodeUTF8Stateful 这个函数里会对字符串预先判断是哪种格式,因为对于Unicode来说,ascii只需1个字节保存,中文需要2或3个字。

字符串对象的共享机制intern

在python中,也有像小整数一样将段字符串作为共享其他变量引用,以达到节省内存和性能上不必要的开销,这就是intern机制:

void PyUnicode_InternInPlace(PyObject **p)
{
    PyObject *s = *p;
    PyObject *t;

    if (s == NULL || !PyUnicode_Check(s))
        return;

    // 对PyUnicodeObjec进行类型和状态检查
    if (!PyUnicode_CheckExact(s))
        return;
    if (PyUnicode_CHECK_INTERNED(s))
        return;
    // 创建intern机制的dict
    if (interned == NULL) {
        interned = PyDict_New();
        if (interned == NULL) {
            PyErr_Clear(); /* Don't leave an exception */
            return;
        }
    }

    // 对象是否存在于inter中
    t = PyDict_SetDefault(interned, s, s);

    // 存在, 调整引用计数
    if (t != s) {
        Py_INCREF(t);
        Py_SETREF(*p, t);
        return;
    }
    /* The two references in interned are not counted by refcnt.
       The deallocator will take care of this */
    Py_REFCNT(s) -= 2;
    _PyUnicode_STATE(s).interned = SSTATE_INTERNED_MORTAL;
}

PyDict_SetDefault 函数中首先会进行一系列的检查, 包括类型检查, 因为intern共享机制只能应用在字符串对象上; 检查传入的对象是否已被inter机制处理过了。

在代码中可以看到, inter机制的核心在 interned 变量中,interned = PyDict_New(); 也就是在python中经常用到的 dict 。这样就很清楚了, 就是在系统中有一个(key,value)映射关系的集合。

intern机制中的PyUnicodObject采用了特殊的引用计数机制。将一个PyUnicodeObject对象a的PyObject指针作为key和valu添加到intered中时,PyDictObjec对象会通过这两个指针对a的引用计数进行两次+1操作。这会造成a的引用计数在python程序结束前永远不会为0,这也是 Py_REFCNT(s) -= 2; 将计数减2的原因。

intern机制作用的对象是 PyUnicodObject ,可以看到函数参数中看到对象还是被创建了。事实上python始终会为字符创建PyUnicodeObject对象, 尽管interned中已经有维护了一个和原字符串一样的对象。进行了inter机制后, 临时创建的字符串对象会减少引用计数为0而被销毁, 也就是临时变量在内存中昙花一现然后迅速消失。

#define Py_SETREF(op, op2)                      \
    do {                                        \
        PyObject *_py_tmp = (PyObject *)(op);   \
        (op) = (op2);                           \
        Py_DECREF(_py_tmp);                     \
    } while (0)

那,如果直接在c原生字符串中进行inter的动作, 不就不需要创建这一个临时对象了吗, python确实提供一个char × 的共享机制函数, 但只是换汤不换药:

PyObject * PyUnicode_InternFromString(const char *cp)
{
    PyObject *s = PyUnicode_FromString(cp);
    if (s == NULL)
        return NULL;
    PyUnicode_InternInPlace(&s);
    return s;
}

临时对象照样是要被创建的, 这里并不是作者偷懒或者怎样, 这是因为PyDictObject中必须以PyObect × 指针作为key的。

字符串对象有两种状态,一个是 SSTATE_INTERNED_IMMORTAL 另一个是 SSTATE_INTERNED_MORTAL, 处于SSTATE_INTERNED_IMMORTAL这种状态的字符串永远不会被销毁,它将与python虚拟机共存亡。 PyUnicode_InternInPlace 函数只能创建SSTATE_INTERNED_MORTAL 状态的对象。若要修改可以调用:

void PyUnicode_InternImmortal(PyObject **p)
{
    PyUnicode_InternInPlace(p);
    if (PyUnicode_CHECK_INTERNED(*p) != SSTATE_INTERNED_IMMORTAL) {
        _PyUnicode_STATE(*p).interned = SSTATE_INTERNED_IMMORTAL;
        Py_INCREF(*p);
    }
}

字符缓冲池

在整型对象中,有一个小整数对象池,而字符串对象中,也有一个对应的PyUnicodeObject对象池:

static PyObject *unicode_latin1[256] = {NULL};

如果字符串实际是一个字符,则胡进行如下操作:

[unicodeobjec.c]
PyObject * PyUnicode_DecodeUTF8Stateful(const char *s,
                             Py_ssize_t size,
                             const char *errors,
                             Py_ssize_t *consumed)
{
    ...

    /* ASCII is equivalent to the first 128 ordinals in Unicode. */
    if (size == 1 && (unsigned char)s[0] < 128) {
        if (consumed)
            *consumed = 1;
        return get_latin1_char((unsigned char)s[0]);
    }
    ...
}

会简单从get_latin1_char中获取:

static PyObject* get_latin1_char(unsigned char ch)
{
    PyObject *unicode = unicode_latin1[ch];
    if (!unicode) {
        unicode = PyUnicode_New(1, ch);
        if (!unicode)
            return NULL;
        PyUnicode_1BYTE_DATA(unicode)[0] = ch;
        assert(_PyUnicode_CheckConsistency(unicode, 1));
        unicode_latin1[ch] = unicode;
    }
    Py_INCREF(unicode);
    return unicode;
}

先对所创建的字符串(只有一个字符)对象进行intern操作,再将inter的结果缓存到字符缓冲池 unicode_latin1 中,两者都是指向同一个字符对象。

PyUnicodeObject 操作效率

pytho中,使用 “+” 符号进行字符串拼接, 这种方法效率极低, 因为在python中PyUnicodeObject对象是一个不可变对象。 这就意味着当进行字符串拼接时,实际上是创建一个新的对象。如果要链接n个PyUnicodeObject对象,就要进行n-1次内存申请和内存搬运的工作。

因此,当需要多个字符串拼接时,官方推荐的做法是通过join来操作。这种做法只需要分配一次内存,执行效率大大提高。通过“+”运算时会调用:

PyObject * PyUnicode_Concat(PyObject *left, PyObject *right)
{
    PyObject *result;
    Py_UCS4 maxchar, maxchar2;
    Py_ssize_t left_len, right_len, new_len;
    //省略类型检查的代码

    left_len = PyUnicode_GET_LENGTH(left);
    right_len = PyUnicode_GET_LENGTH(right);

    new_len = left_len + right_len;

    maxchar = PyUnicode_MAX_CHAR_VALUE(left);
    maxchar2 = PyUnicode_MAX_CHAR_VALUE(right);
    maxchar = Py_MAX(maxchar, maxchar2);

    /* Concat the two Unicode strings */
    result = PyUnicode_New(new_len, maxchar);
    if (result == NULL)
        return NULL;
    // 内存搬运
    _PyUnicode_FastCopyCharacters(result, 0, left, 0, left_len);
    _PyUnicode_FastCopyCharacters(result, left_len, right, 0, right_len);
    // 断言检查
    assert(_PyUnicode_CheckConsistency(result, 1));
    return result;
}

对于任意两PyUnicodeObject对象的拼接,就会进行一次内存申请的动作,而如果利用join则会进行如下的动作:

[unicodeobject.c]
static PyObject * unicode_join(PyObject *self, PyObject *iterable)
/*[clinic end generated code: output=6857e7cecfe7bf98 input=2f70422bfb8fa189]*/
{
    return PyUnicode_Join(self, iterable);
}

PyObject * PyUnicode_Join(PyObject *separator, PyObject *seq)
{
    PyObject *res;
    PyObject *fseq;
    Py_ssize_t seqlen;
    PyObject **items;

    fseq = PySequence_Fast(seq, "can only join an iterable");
    if (fseq == NULL) {
        return NULL;
    }

    /* NOTE: the following code can't call back into Python code,
     * so we are sure that fseq won't be mutated.
     */

    items = PySequence_Fast_ITEMS(fseq);
    seqlen = PySequence_Fast_GET_SIZE(fseq);
    res = _PyUnicode_JoinArray(separator, items, seqlen);
    Py_DECREF(fseq);
    return res;
}

跟踪 _PyUnicode_JoinArray

// seqlen表示list中元素个数
PyObject * _PyUnicode_JoinArray(PyObject *separator, PyObject **items, Py_ssize_t seqlen)
{
    PyObject *res = NULL; /* the result */
    PyObject *sep = NULL;
    Py_ssize_t seplen;
    PyObject *item;
    ...     // 省略变量声明若干

    sz = 0; // 记录总共要存放字符个数

    for (i = 0; i < seqlen; i++) {
        size_t add_sz;
        item = items[i];

        add_sz = PyUnicode_GET_LENGTH(item);
        item_maxchar = PyUnicode_MAX_CHAR_VALUE(item);
        maxchar = Py_MAX(maxchar, item_maxchar);
        if (i != 0) {
            add_sz += seplen;
        }
        sz += add_sz;
        last_obj = item;
    }

    res = PyUnicode_New(sz, maxchar);   // 申请内存
    if (res == NULL)
        goto onError;

    for (i = 0, res_offset = 0; i < seqlen; ++i) {
        Py_ssize_t itemlen;
        item = items[i];

        /* Copy item, and maybe the separator. */
        if (i && seplen != 0) {
            // 内存搬运
            _PyUnicode_FastCopyCharacters(res, res_offset, sep, 0, seplen);
            res_offset += seplen;   // 调整偏移量
        }

        itemlen = PyUnicode_GET_LENGTH(item);
        if (itemlen != 0) {
            _PyUnicode_FastCopyCharacters(res, res_offset, item, 0, itemlen);
            res_offset += itemlen;
        }
    }
    // 断言检查
    assert(res_offset == PyUnicode_GET_LENGTH(res));

    Py_XDECREF(sep);
    assert(_PyUnicode_CheckConsistency(res, 1));
    return res;

  onError:
    Py_XDECREF(sep);
    Py_XDECREF(res);
    return NULL;
}

执行join操作时,首先会统计list中多少个PyUnicodeObject对象,并统计每个对象所维护的字符串有多长, 进行求和执行一次申请空间。再逐一进行字符串拷贝。


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!