字符串intern机制 | 字符串驻留 | Python源码

2022-03-08 04:58:25

有次聊天，有人说字符串驻留技术还是蛮好的。看着别人一脸认真的样子，我一脸赞同的点点头，现在来补一补这东西是啥。

先看看字符串相关定义

PyStringObject 定义

# Include/stringobject.h
typedef struct {
    PyObject_VAR_HEAD
    long ob_shash;
    int ob_sstate;
    char ob_sval[1];

} PyStringObject;

PyObject_VAR_HEAD 中的 ob_size ，记录变长对象的内存大小，ov_sval 作为字符指针指向一段内存，这段内存就是实际字符串。比例 test_str 的 ob_size 则为11。

ob_shash 则是该对象的哈希值，这在 dict 类型中是非常有用的，作为 key 值存在。

ob_sstate 则是表明该对象是否经过 intern 机制处理，简单来说就是即值同样的字符串对象仅仅会保存一份，放在一个字符串储蓄池中，是共用的，当然，肯定不能改变，这也决定了字符串必须是不可变对象

PyStringObject 创建

# Include/stringobject.h

PyAPI_FUNC(PyObject *) PyString_FromStringAndSize(const char *, Py_ssize_t);
PyAPI_FUNC(PyObject *) PyString_FromString(const char *);
PyAPI_FUNC(PyObject *) PyString_FromFormatV(const char*, va_list)
				Py_GCC_ATTRIBUTE((format(printf, 1, 0)));
PyAPI_FUNC(PyObject *) PyString_FromFormat(const char*, ...)
				Py_GCC_ATTRIBUTE((format(printf, 1, 2)));

从定义来看，可以用很多种方式创建PyStringObject,最常用为PyString_FromString

# Objects/stringobject.c
# null 以及单字符串，内部使用 interned 缓存了，命中直接返回

static PyObject *interned;

void
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_SETREF(*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;
}

# 字符串创建
PyObject *
PyString_FromString(const char *str)
{
    register size_t size;
    register PyStringObject *op;

    assert(str != NULL);
    size = strlen(str);
    if (size > PY_SSIZE_T_MAX - PyStringObject_SIZE) {
        PyErr_SetString(PyExc_OverflowError,
            "string is too long for a Python string");
        return NULL;
    }
    if (size == 0 && (op = nullstring) != NULL) {
#ifdef COUNT_ALLOCS
        null_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    }
    if (size == 1 && (op = characters[*str & UCHAR_MAX]) != NULL) {
#ifdef COUNT_ALLOCS
        one_strings++;
#endif
        Py_INCREF(op);
        return (PyObject *)op;
    }

    /* Inline PyObject_NewVar */
    op = (PyStringObject *)PyObject_MALLOC(PyStringObject_SIZE + size);
    if (op == NULL)
        return PyErr_NoMemory();
    (void)PyObject_INIT_VAR(op, &PyString_Type, size);
    op->ob_shash = -1;
    op->ob_sstate = SSTATE_NOT_INTERNED;
    Py_MEMCPY(op->ob_sval, str, size+1);
    /* share short strings */
    if (size == 0) {
        PyObject *t = (PyObject *)op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *)t;
        nullstring = op;
        Py_INCREF(op);
    } else if (size == 1) {
        PyObject *t = (PyObject *)op;
        PyString_InternInPlace(&t);
        op = (PyStringObject *)t;
        characters[*str & UCHAR_MAX] = op;
        Py_INCREF(op);
    }
    return (PyObject *) op;
}

总结就是：

判断字符串是否过长，过长，则返回 null 指针
判断是否是空串，空串，则将引用
分配内存，并将字符串复制到 op->ob_sval 中

PyStringObject 内存布局

\	\	ob_size	ob_shash	ob_sstate	ob_sval
REF	TYPE	6	-1	0	P	y	t	h	o	n	\0

缓存池过渡

In [6]: a = 'thisistest'

In [7]: b = 'thisistest'

In [8]: a is b
Out[8]: True

In [9]: id(a) == id(b)
Out[9]: True

按照上述解释，长字符串，应该是重新创建。结果提示内存地址都一样，那么说明字符串驻留不仅仅是指创建这一块，应该是一种优化方式。验证代码里存在定义，用法也存在，那我们看看定义。

什么是“字符串驻留”？

字符串驻留是一种编译器/解释器的优化方法，它通过缓存一般性的字符串，从而节省字符串处理任务的空间和时间。

这种优化方法不会每次都创建一个新的字符串副本，而是仅为每个适当的不可变值保留一个字符串副本，并使用指针引用之。每个字符串的唯一拷贝被称为它的intern，并因此而得名 String Interning。

现代编程语言如 Java、Python、PHP、Ruby、Julia 等等，都支持字符串驻留，以使其编译器和解释器做到高性能。

为什么要驻留字符串？

字符串驻留提升了字符串比较的速度。如果没有驻留，当我们要比较两个字符串是否相等时，它的时间复杂度将上升到 O(n)，即需要检查两个字符串中的每个字符，才能判断出它们是否相等。

但是，如果字符串是固定的，由于相同的字符串将使用同一个对象引用，因此只需检查指针是否相同，就足以判断出两个字符串是否相等，不必再逐一检查每个字符。由于这是一个非常普遍的操作，因此，它被典型地实现为指针相等性校验，仅使用一条完全没有内存引用的机器指令。

字符串驻留减少了内存占用。 Python 避免内存中充斥多余的字符串对象，通过享元设计模式共享和重用已经定义的对象，从而优化内存占用。

哪些可以驻留呢？

包含 ASCII 字符和下划线的字符串会被驻留。在编译期间，当对字符串字面量进行驻留时，CPython 确保仅对匹配正则表达式[a-zA-Z0-9_]*的常量进行驻留，因为它们非常贴近于 Python 的标识符。

# join不驻留
In [11]: a = 'thisistest'

In [12]: a
Out[12]: 'thisistest'

In [13]: a is "".join(a)
Out[13]: False

In [14]: a == "".join(a)
Out[14]: True

#  仅对匹配正则表达式[a-zA-Z0-9_]*的常量进行驻留
In [15]: A = 'This is test'

In [16]: B = 'This is test'

In [17]: A is B
Out[17]: False

Intern 机制的大致原理很好理解，然而影响结果的还有 CPython 解释器的其它编译及运行机制，字符串对象受到这些机制的共同影响。实际上，只有那些“看起来像” Python 标识符的字符串才会被处理。源代码StringObject.h的注释中写道：

/* … … This is generally restricted to strings that “looklike” Python identifiers, although the intern() builtin can be used to force interning of any string … … */

这些机制的相互作用，不经意间带来了不少混乱的现象：

# 长度超过20，不被intern VS 被intern
'a' * 21 is 'aaaaaaaaaaaaaaaaaaaaa'
>>> False
'aaaaaaaaaaaaaaaaaaaaa' is 'aaaaaaaaaaaaaaaaaaaaa'
>>> True

# 长度不超过20，不被intern VS 被intern
s = 'a'
s * 5 is 'aaaaa'
>>> False
'a' * 5 is 'aaaaa'
>>> True


# join方法，不被intern VS 被intern
''.join('hi') is 'hi'
>>> False
''.join('h') is 'h'
>>> True

# 特殊符号，不被intern VS 被"intern"
'python!' is 'python!'
>>> False
a, b = 'python!', 'python!'
a is b
>>> True

参考文献

字符串驻留： https://zhuanlan.zhihu.com/p/351244769

码农公寓

先看看字符串相关定义

哪些可以驻留呢？

相关文章