日期 分类 Python

Python中的字符串是经常使用的数据类型,每个字符串对象的新建和销毁都涉及到很多的资源开销。所以,在Python内部对字符串对象的处理进行了优化,其中最主要的优化就是intern机制。

字符串对象结构

在CPython源码中,字符串对象用PyStringObject表示,结构如下:

[stringobject.h]
typedef struct {
    PyObject_VAR_HEAD
    long ob_shash;
    int ob_sstate;
    char ob_sval[1];
} PyStringObject;

ob_sval是一个只有一个字符的字符数组,实际ob_sval是作为一个字符指针指向一个长度为ob_size+1个字节的内存,ob_size保存在PyObject_VAR_HEAD结构中。ob_shash是该对象的hash值,该值一般用于计算该对象作为key在hash数组中的位置。ob_sstate用于标记该对象是否被intern机制处理过。

[stringobject.h]
#define PyString_CHECK_INTERNED(op) (((PyStringObject *)(op))->ob_sstate)

Intern机制

了解了字符串对象的结构之后,接着看下字符串对象创建

[stringobject.c]
PyObject* PyString_FromString(const char *str)
{
    register size_t size;
    register PyStringObject *op;

    ... // 创建PyStringObject对象

    // intern长度较短的PyStringObject对象
    if (size == 0) {
        PyObject *t = (PyObject *)op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *)t;
        nullstring = op;
    } else if (size == 1) {
        PyObject *t = (PyObject *)op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *)t;
        characters[*str & UCHAR_MAX] = op;
    }
    return (PyObject *)op;
}

可以看到,字符串对象在被创建之后会被进行PyString_InternInPlace处理,这个PyString_InternInPlace就是具体的Intern机制的处理。

PyString_InternInPlace(PyObject **p)
{
    register PyStringObject *s = (PyStringObject *)(*p);
    PyObject *t;
    if (s == NULL || !PyString_Check(s))
        Py_FatalError("PyString_InternInPlace: strings only please!");
    /* If it's a string subclass, we don't really know what putting
       it in the interned dict might do. */
    if (!PyString_CheckExact(s))
        return;
    if (PyString_CHECK_INTERNED(s))
        return;
    if (interned == NULL) {
        interned = PyDict_New();
        if (interned == NULL) {
            PyErr_Clear(); /* Don't leave an exception */
            return;
        }
    }
    t = PyDict_GetItem(interned, (PyObject *)s);
    if (t) {
        Py_INCREF(t);
        Py_DECREF(*p);
        *p = t;
        return;
    }

    if (PyDict_SetItem(interned, (PyObject *)s, (PyObject *)s) < 0) {
        PyErr_Clear();
        return;
    }
    /* The two references in interned are not counted by refcnt.
       The string deallocator will take care of this */
    Py_REFCNT(s) -= 2;
    PyString_CHECK_INTERNED(s) = SSTATE_INTERNED_MORTAL;
}

上面代码基本流程就是:检查字典结构interned中是否存在已新建字符串对象s作为key的对象,如果存在,销毁s,返回该对象,如果不存在,在interned中设置对象s同时作为keyvalue,最后对s减少两次引用计数。

用Python代码表示大致如下:

interned = None

def intern(string):
    if string is None or not type(string) is str:
        raise TypeError

    if string.is_interned:
        return string

    if interned is None:
        global interned
        interned = {}

    t = interned.get(string)
    if t is not None:
        return t

    interned[string] = string
    string.is_interned = True
    return string

不过这里对于对象销毁和引用计数的修改都没有进行说明。

多字符的不同处理

由上面源码部分我们可以知道对于长度为0和1的字符串都会进行Intern,但是长度大于1的字符串有没有进行Intern呢?观察下面语句

>>> 'foo' is 'foo'
True
>>> 'foo!' is 'foo!'
False

可以看出对于长度大于1的字符串是否Intern,貌似取决于字符串包含的字符。事实上这个猜想是对的,这部分字符串的Intern是在源码编译成字节码的阶段完成的

[codeobject.c]
PyCodeObject *
PyCode_New(int argcount, int nlocals, int stacksize, int flags,
           PyObject *code, PyObject *consts, PyObject *names,
           PyObject *varnames, PyObject *freevars, PyObject *cellvars,
           PyObject *filename, PyObject *name, int firstlineno,
           PyObject *lnotab)

           ...
           /* Intern selected string constants */
           for (i = PyTuple_Size(consts); --i >= 0; ) {
               PyObject *v = PyTuple_GetItem(consts, i);
               if (!PyString_Check(v))
                   continue;
               if (!all_name_chars((unsigned char *)PyString_AS_STRING(v)))
                   continue;
               PyString_InternInPlace(&PyTuple_GET_ITEM(consts, i));
           }

可以看到,在生成新PyCodeObject对象时,对于字符串常量确实应用了Intern机制,不过如果不满足all_name_chars条件就不会Intern,所以all_name_chars函数决定了字符串是否会被Intern

#define NAME_CHARS \
    "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz"

/* all_name_chars(s): true iff all chars in s are valid NAME_CHARS */

static int
all_name_chars(unsigned char *s)
{
    static char ok_name_char[256];
    static unsigned char *name_chars = (unsigned char *)NAME_CHARS;

    if (ok_name_char[*name_chars] == 0) {
        unsigned char *p;
        for (p = name_chars; *p; p++)
            ok_name_char[*p] = 1;
    }
    while (*s) {
        if (ok_name_char[*s++] == 0)
            return 0;
    }
    return 1;
}

上面代码中很容易可以看出,字符串中包含0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz之外的字符就不会被Intern。似乎这里我们已经掌握了关于Python的Intern机制的所有知识,但是再看如下几个语句

>>> 'foo' + 'bar' is 'foobar'
True
>>> ''.join(['f']) is ''.join(['f'])
True
>>> ''.join(['f', 'o', 'o']) is ''.join(['f', 'o', 'o'])
False
>>> 'a' * 20 is 'aaaaaaaaaaaaaaaaaaaa'
True
>>> 'a' * 21 is 'aaaaaaaaaaaaaaaaaaaaa'
False
>>> 'foooooooooooooooooooooooooooooo' is 'foooooooooooooooooooooooooooooo'
True

是不是又有些难以理解了?这个现象涉及到编译器优化的知识,简单说就是在编译阶段,编译器把'foo' + 'bar'这种语句直接编译成了'foobar',把'a' * 2编译成'aa',所以'a' * 2'aa'是一个东西,但是编译器优化也不会无限制的优化,会有长度限制,所以'a' * 21 is 'aaaaaaaaaaaaaaaaaaaaa'并不成立。至于join的操作,编译器则不会进行优化,join的结果完全是动态生成的。通过dis反汇编可以验证这一结果。


参考资料