对于超过64个字符的字符串，什么会影响Python字符串比较性能？

Question

我试图评估比较两个字符串是否会随着它们的长度增加而变慢。我的计算表明比较字符串应该需要一个摊销常数时间，但我的Python实验产生了奇怪的结果：

下面是字符串长度（1到400）与时间（毫秒）的关系图。自动垃圾收集已禁用，并且gc。在每次迭代之间运行collect。

我每次比较100万随机字符串，计算匹配如下。这个过程重复50次，然后取所有测量时间的最小值。

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1

什么可能解释长度64左右突然增加？

注意：假设v1和v2是两个长度为n的随机字符串列表，COUNT是它们的长度，则可以使用下面的代码段来尝试再现该问题。

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)

进一步注意：我做了两个额外的测试：将字符串与进行比较是而不是==完全抑制了问题，性能约为210ms/1M比较。既然提到了实习，我确保在每个字符串后面添加一个空格，这应该可以防止实习；这不会改变任何事情。那么是不是除了实习之外的其他事情？

Answer 1

我只是在胡乱猜测，但你问的是“可能是什么”，而不是什么原因。这里有一些可能性：

• CPU缓存线大小为64字节，较长的字符串会导致缓存未命中

Answer 2

Python可以“插入”短字符串；将它们存储在特殊缓存中，并重新使用该缓存中的字符串对象。

然后比较字符串时，它将首先测试它是否是相同的指针（例如一个内嵌字符串）：

if (a == b) {
    switch (op) {
    case Py_EQ:case Py_LE:case Py_GE:
        result = Py_True;
        goto out;
// ...

只有当指针比较失败时，它才会使用大小检查和memcmp来比较字符串。

通常只会对标识符（函数名、参数、属性等）进行实习，但不会对运行时创建的字符串值进行实习。

另一个可能的罪魁祸首是字符串常量；代码中使用的字符串文本在编译时存储为常量，并在整个过程中重用；同样，只创建了一个对象，对这些对象的身份测试速度更快。

对于不相同的字符串对象，Python测试等长、等首字符，然后对内部C字符串使用memcmp（）函数。如果字符串没有被插入或以其他方式重用相同的对象，那么所有其他速度特性都归结为memcmp（）函数。