Python：Python进阶：Python字符串驻留技术_python字符串驻留机制

由于字符串是任何编程语言中不可或缺的一个部分，因此，如果有快速操作字符串的能力，就有可以迅速的提高整体的性能。
本文，我们将深入研究Python 的内部实现，并了解 Python如何使用一种名为字符串驻留 （string Interning）的技术，实现解释器的高性能。以下是本文的提纲

1.什么是字符串驻留

1. 字符串驻留是编译器/解释器的优化方法，它通过 缓存一般性的字符串，从而节省字符串处理任务的空间和时间。
   事实上这种优化方法不会每次都创建一个新的 字符串副本，而是仅为每个适当的不可变值保留一个字符串副本，并使用指针引用之。
2. string interning 一般译为 “ 字符串驻留或字符串留用” 在某些 语言中可能习惯使用 string pool （字符串常量池）的概念，其实这是对同一种机制的不同表述。
   

2. 为什么要驻留字符串

1. 首先字符串驻留提升了字符串比较的速度。 如果没有驻留，当我们要比较两个字符串是否相等时，它的时间复杂度将会上升到 o(n) ，即需要检查两个字符串中的每个字符，才能判断他们是否相等。
2. 但是，如果两个字符串使用的是同一个对象的引用，那么我们只需要判断检查指针是否相同，就足以判断出两个字符串是否相同，不需要逐一检查每个字符串。
3. 字符串驻留技术减少了内存占用，Python避免内存中 充斥多余的字符串对象，通过享元设计模式共享和重用已经定义的对象，从而优化内存占用。

3. Python的字符串驻留

在Python中使用 is 运算符 ，检查两个对象是否引用同一个内存对象。注意在 Python3.8 版本之后，需要使用 == 来判断两个对象是否相等。

"python" == 'python'  # true
1==2 # false
"Python" == 'python'  # false
1
2
3

4. Python 字符驻留原理

在 CPython 中，字符串的引用被一个名为 interned 的 python字典所存储，访问和管理。该字典在第一调用字符串驻留时，被延迟的初始化，并持有全部已驻留字符串对象的引用。

4.1 如何驻留字符串

在 CPython 中，负责驻留字符串的核心函数是 PyUnicode_InternInplace 它定义在 unicodeobject.c 中，当调用时，它会创建一个准备容纳所有驻留字符串的字典 Interned , 然后登记入参中的对象，然后另其键和值都使用相同的对象引用

void PyUnicode_InternInplace(PyObject **p)
{
	PyObject *s = p;
	........
	// Lazing build the dicrionary to hold interned strings
	if (interned ==NULL) {
    	interned  = PyDict_New();
    	if (interned ==NULL)
    	{
			PyErr_Clear();
			return;
        }
    }
    PyObject *t;
    // make an entry to the interned dictionary for the given object
    t = PyDict_SetDefault(interned, s, s);
    ......
    // set the state of the string to be INTERNED
    _PyUnicode_STATE(s).interned = SSTATE_INTERNED_MORTAL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.2 如何清理驻留的字符串

清理函数从 interned 字典中遍历所有的字符串，调整这些对象的引用计数，并把它们标记为 NOT_INTERNED， 使其被垃圾回收，一旦所有的字符串被标记为 NOT_INTERNED，则 interned 字典会被清空并删除。

这个清理函数就是 _PyUnicode_ClearInterned ，在 unicodeobject.c 中定义

void _PyUnicode_ClearInterned(PyThreadState *tstate)
{
	// Get all the keys to the interned dictionary
	PyObject *keys = PyDict_Keys(interned);
	.......
	// Interned Unicode strings are not forcibly deallocated
	// rather ,we give them their stolen references back
	// and then clear and DECREF the interned dict
	for(Py_ssize_t i = 0; i< n; i++)
	{
		PyObject *s = PyList_GET_ITEM(keys,i);
		.....
		switch (PyUnicode_CHECK_INTERNED(s)){
		case SSTATE_INTERNED_IMMORTAL:
			   Py_SET_REFCNT(s,Py_REFCNT(s)+1);
			   break;
		case SSTATE_INTERNED_MORTAL:
		     // Restore the two references(key and balue) ignored
		     // by PyUnicode_InterInPlace()
		     Py_SET_REFCNT(s,Py_REFCNT(s) +2);
		     break;
		case SSTATE_NOTINTERNED:
		default:
			Py_UNREACHABLE();
        }
        // making the string to be  NOT_INTERNED
        _PyUnicode_STATE(s).interned = SSTATE_NOT_INTERNED;
	}
	// decreasing the refernece to the initialized and
	// access可以是object
	Py_DECREF(keys);
	// clearing the dictionary
	PyDict_Clear(interned);
	// clearing the object interned
	Py_CLEAR(interned);
}
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

5. 字符串驻留的实现

这一小节主要讲：Python会驻留哪些字符串

5.1. 变量、常量与函数名

CPython 对常量（例如函数名，变量名，字符串字面量等）执行字符串驻留。

5.2 字典的键

CPthon 还会驻留任何字典对象的字符串键

5.3 任何对象的属性

CPython中对象的属性可以通过 setattr 函数显式地设置，也可以作为类成员的一部分隐式的设置，或者在其数据类型中定义。
CPython会驻留所有这些属性名，以便实现快速的查找。

5.4 显式地驻留

Python还支持通过 sys模块中的 intern 函数进行显示地字符串驻留。

6 字符串驻留的其他发现

只有在编译期的字符串会被驻留，解释时或编译时指定的字符串会被驻留，而动态创建的字符串则不会

7. 总结

驻留（interning）：实际上是共享字符串字面量的一种优化措施，CPython还会在小的整数上采用这种技术，防止重复创建“热门”数字：如 0 ，-1,42，但是注意 CPython并不会驻留所有字符串和整数，而且驻留条件的细节，也并没有文档说明