为什么比较匹配的字符串比不匹配的字符串快？

Question

这里有两个测量值：

timeit.timeit('"toto"=="1234"', number=100000000)
1.8320042459999968
timeit.timeit('"toto"=="toto"', number=100000000)
1.4517491540000265

如您所见，比较两个匹配的字符串比比较两个不匹配但长度相同的字符串要快。

这令人非常困惑：在字符串比较期间，我认为Python是逐个字符地测试字符串的，因此"toto"=="toto"的测试时间应该比"toto"=="1234"长，因为它需要进行四次测试，而非匹配比较只需要进行一次测试。也许比较是基于哈希的，但在这种情况下，两种比较的时间应该相同。

为什么？

- Eric

---

字符串驻留，也许？ - Sayse

请检查"toto" is "toto"的值。很可能在同一语句中编译两个相同的字符串文字到同一个字符串对象。如果您的字符串是通过不同方式生成的，则可能会得到不同的结果。 - khelwood

@RiccardoBucco 所谓的“小整数”（从-5到255，如果我没记错的话）实际上是提前进行了记忆化处理，它们总是从缓存中获取。因此，对它们进行身份验证也是非常有意义的。 - Masklinn

@RiccardoBucco 嗯，是的，但你拥有相同身份的原因是小整数被缓存了（在cpython中，作为实现细节）。对于浮点数没有这样的缓存，因此相同字面值的两个实例是不同的对象。由于遇到相同的浮点数（相同的对象，而不是相同的值）的可能性很低（因为它们没有被缓存），所以cpython不会优化这种比较。 - Masklinn

在字符串比较期间，我认为Python是逐个字符测试字符串的。但我真诚地怀疑任何像样的编程语言都不会使用简单的for循环进行字符串比较。Python当然不会这样做，它使用memcmp函数（请参见https://github.com/python/cpython/blob/main/Objects/stringlib/eq.h#L23），该函数可以使用SIMD指令一次比较多个字节，以及其他优化技巧。 - marcelm

Answer 1

结合我和 @khelwood 的评论:

简短概括：
当分析两个比较的字节码时，它揭示了'time'和'time'字符串被分配到相同的对象上。因此，一个提前进行的身份检查（在 C 级别）是增加比较速度的原因。

同一对象赋值的原因是，作为一项实现细节，CPython 会将只包含“名称字符”（即字母和下划线字符）的字符串内部化。这使得对象的身份检查成为可能。

---

字节码：

import dis

In [24]: dis.dis("'time'=='time'")
  1           0 LOAD_CONST               0 ('time')  # <-- same object (0)
              2 LOAD_CONST               0 ('time')  # <-- same object (0)
              4 COMPARE_OP               2 (==)
              6 RETURN_VALUE

In [25]: dis.dis("'time'=='1234'")
  1           0 LOAD_CONST               0 ('time')  # <-- different object (0)
              2 LOAD_CONST               1 ('1234')  # <-- different object (1)
              4 COMPARE_OP               2 (==)
              6 RETURN_VALUE

---

作业时间安排:

在时间测试中，使用赋值操作也可以看到“加速”效果。将两个变量分别赋值（和比较）为相同的字符串，比将两个变量分别赋值（和比较）为不同的字符串更快。这进一步支持假设底层逻辑是执行对象比较。下一节将对此进行确认。

In [26]: timeit.timeit("x='time'; y='time'; x==y", number=1000000)
Out[26]: 0.0745926329982467

In [27]: timeit.timeit("x='time'; y='1234'; x==y", number=1000000)
Out[27]: 0.10328884399496019

---

Python源代码:

正如@mkrieger1和@Masklinn在评论中提供的那样，unicodeobject.c的源代码首先执行指针比较，如果结果为True，则立即返回。

int
_PyUnicode_Equal(PyObject *str1, PyObject *str2)
{
    assert(PyUnicode_CheckExact(str1));
    assert(PyUnicode_CheckExact(str2));
    if (str1 == str2) {                  // <-- Here
        return 1;
    }
    if (PyUnicode_READY(str1) || PyUnicode_READY(str2)) {
        return -1;
    }
    return unicode_compare_eq(str1, str2);
}

---

附录:

• 参考答案 很好地说明了如何读取反汇编的字节码输出。由@Delgan提供
• 参考答案 很好地描述了CPython的字符串缓存技术。由@ShadowRanger提供

- S3DEV

---

为什么如果两个对象表示同一个对象，它们的比较会更快？比较运算符是如何实现的？ - Riccardo Bucco

针对字符串，它的实现在这里：https://github.com/python/cpython/blob/main/Objects/unicodeobject.c#L11134 如预期一样，它首先检查身份(identity)，并提前返回结果。 - mkrieger1

因为相等性检查通常会以身份检查开始，因为这是非常便宜但如果它使您可以绕过“结构”相等性检查则非常有效率。您可以在_PyUnicode_Equal中看到这一点。第11139到11141行是一个C级别的相等性检查，这意味着它比较指针，而在CPython中，这是一个身份比较（因为两个对象不能重叠，因此不能具有相同的指针）。 - Masklinn

@mkrieger1 - 正是我所需要的，谢谢。将其包含在答案中。 - S3DEV

Python是否会全局缓存每个字符串？否则，我认为问题陈述不正确。从一般意义上讲，比较匹配的字符串并不更快，但是将对象与自身进行比较会更快。通常情况下，比较不匹配的字符串可能会更快，因为可以提前退出。 - Yanick Salzmann

CPython目前会对只包含单词字符的字符串进行缓存（即intern）。详情请参见https://dev59.com/qZ_ha4cB1Zd3GeqP5dUP。 - David Hammen

Answer 2

比较匹配的字符串并不总是更快。相反，比较具有相同id的字符串始终更快。证明标识确实是这种行为的原因（正如@S3DEV所 brillantly 解释的那样）是这个:

>>> x = 'toto'
>>> y = 'toto'
>>> z = 'totoo'[:-1]
>>> w = 'abcd'
>>> x == y
True
>>> x == z
True
>>> x == w
False
>>> id(x) == id(y)
True
>>> id(x) == id(z)
False
>>> id(x) == id(w)
False
>>> timeit.timeit('x==y', number=100000000, globals={'x': x, 'y': y})
3.893762200000083
>>> timeit.timeit('x==z', number=100000000, globals={'x': x, 'z': z})
4.205321462000029
>>> timeit.timeit('x==w', number=100000000, globals={'x': x, 'w': w})
4.15288594499998

比较具有相同id的对象总是更快的（如您可以从示例中看到，比较x和y之间的比较要比比较x和z之间的比较慢，这是因为x和z没有共享相同的id）。

- Riccardo Bucco

---

"是否是同一个对象" 的简单测试方法是使用 x is y；id(x) == id(y) 可以得到相同的结果，但它会先做一些转换将 int 对象进行比较，而 x is y 直接比较内存地址而无需进行包装。请注意不要改变原文意思。 - ShadowRanger