如何在Python中使用字符串常量池（String Interning）？

Question

我对Python中sys.intern在字典查找时的性能优势感到好奇。为了测量这一点，我编写了以下代码片段：

不使用interning：

import random
from uuid import uuid4

keys = [str(uuid4()) for _ in range(1_000_000)]
values = [random.random() for _ in range(1_000_000)]
my_dict = dict(zip(keys, values))
keys_sample = random.choices(keys, k=50_000)

def get_values(d, ks):
    return [d[k] for k in ks]

测试结果（使用ipython）：

%timeit get_values(my_dict, keys_sample)
8.92 ms ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

使用interning：

import sys
import random
from uuid import uuid4

keys = [sys.intern(str(uuid4())) for _ in range(1_000_000)]
values = [random.random() for _ in range(1_000_000)]
my_dict = dict(zip(keys, values))
keys_sample = random.choices(keys, k=50_000)

def get_values(d, ks):
    return [d[k] for k in ks]

测试结果：

%timeit get_values(my_dict, keys_sample)
8.83 ms ± 17.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

从上述结果可以看出，在两种情况下都没有明显的差异。我还尝试增加字典大小和采样数量，但结果仍然相当。是不是我在使用sys.intern时方法有误？或者这个测试存在什么问题？

David Z · Answer

uuid4()函数设计用于生成唯一的标识符，因此在这种情况下对它使用sys.intern实际上不会带来任何性能提升，除非极其不幸地发生了碰撞。

>>> ids = [str(uuid4()) for _ in range(1_000_000)]
>>> len(ids)
1000000
>>> len(set(ids))
1000000

若要观察到sys.intern带来的性能提升，应该使用大量重复的字符串进行测试。只有当你需要限制内存使用，并且在不同位置创建了相同的字符串时，使用sys.intern才有价值。然而，这种场景相对较少见。

adeneo · Answer

在上述情境中，你提到的是Python手册中关于sys.intern功能的一个段落：

将字符串加入到“内部化”字符串表，并返回内部化的字符串，即原始字符串或其副本。内部化字符串有助于提升字典查找时的一点性能——如果字典中的键已经被内部化，而且查找的键也内部化了，那么在哈希之后可以直接通过指针比较而非字符串比较来进行键的比较。[...]

（引用自：Python 3 文档）

在你进行的这个基准测试中，你遭遇了Python处理字符串时的两个优化机制，这使得在当前条件下无法从intern()中获取性能提升。

当你对字符串列表执行random.choice()时，选取的样本列表实际上包含了指向同一组字符串的不同引用。当Python比较两个指向同一字符串的引用时，并不会执行实际的字符串比较——因为指向相同字符串的两个引用肯定相等。换言之，若a is b成立，则a == b必然成立。
当你比较两个字符串是否相等，而a is not b时，Python会执行另外一项检查以避免字符串比较。它会检查a和b的哈希值，如果hash(a) != hash(b)，说明这两个字符串不可能相等。同时，为了避免多次计算，字符串对象会缓存其哈希值。

因此，在这个字典查找的过程中存在两种情况：要么比较的是相同的两个字符串，这时引用相等的优化可以避免字符串比较；要么比较的是不同的字符串，这时哈希值比较的优化有很高的概率可以避免字符串比较。

为了展示sys.intern()的确能在某些情况下发挥效用，我们需要构建一个（尽管有点刻意为之的）基准测试场景。比如，想象有一个服务器从网络套接字接收字符串，并将这些字符串与硬编码在字典中的字符串进行比较。在这种情况下，套接字收到的字符串与字典中的字符串通常不会有引用相等性。

为了模拟这种情况，我创建了一个函数，它会复制keys_sample中的每一个字符串，这样一来Python就不能利用优化#1（即引用相等性）。此外，它还给每个字符串前添加了一千个'a'字符，以尽可能增加字符串比较的代价。

import sys
import random
from uuid import uuid4


N = 100_000


def copy_string_list(l):
    """ copies of each string in l.

    Warning: Never do this in real code, it is slower and has no benefit"""
    return [(a + '.')[:-1] for a  in l]


def get_values(d, ks):
    return [d[k] for k in ks]


def generate_keys(intern, copy_strings):
    keys = ['a' * 1000 + str(uuid4()) for _ in range(N)]
    if intern:
        keys = [sys.intern(key) for key in keys]
    values = [random.random() for _ in range(N)]
    my_dict = dict(zip(keys, values))
    keys_sample = random.choices(keys, k=N // 2)
    if copy_strings:
        keys_sample = copy_string_list(keys_sample)
    if intern:
        keys_sample = [sys.intern(key) for key in keys_sample]
    return my_dict, keys_sample


print("Looking up interned strings")
my_dict, keys_sample = generate_keys(intern=True, copy_strings=True)
%timeit get_values(my_dict, keys_sample)
print("Looking up non-interned strings")
my_dict, keys_sample = generate_keys(intern=False, copy_strings=True)
%timeit get_values(my_dict, keys_sample)
print("Neither interning nor copying")
my_dict, keys_sample = generate_keys(intern=False, copy_strings=False)
%timeit get_values(my_dict, keys_sample)

Results:

Looking up interned strings
10.7 ms ± 129 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
Looking up non-interned strings
19.9 ms ± 120 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
Neither interning nor copying
10.5 ms ± 238 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)