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

Question

这里有两个测量值：

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

如您所见，比较两个匹配的字符串比比较两个大小相同但不匹配的字符串更快。这非常令人不安：在字符串比较期间，我认为 Python 是逐字符测试字符串，因此 "toto"=="toto" 的测试时间应该比 "toto"=="1234" 长，因为它需要四次测试对一个不匹配的比较。也许比较是基于哈希的，但在这种情况下，两次比较的时间应该相同。

为什么？

Answer 1

结合我的评论和@khelwood 的评论：

TL;DR:
在分析两次比较的字节码时，它揭示了 'time' 和 'time' 字符串分配给了同一个对象。因此，up-front 身份检查（在C-level）是提高比较速度的原因。

相同对象分配的原因是，作为 实现细节 ，CPython 实习生字符串仅包含 'name characters'（即 alpha 和下划线字符）。这将启用对象的身份检查。

字节码：

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

分配时间：

'speed-up' 也可以在使用赋值进行时间测试中看到。将两个变量赋值（和比较）到同一个字符串比将两个变量赋值（和比较）到不同的字符串更快。进一步支持假设，底层逻辑正在执行对象比较。这将在下一节中得到证实。

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 在他们的评论中提供的帮助，source code 对于 unicodeobject.c 首先执行指针比较，如果 True，则立即执行 returns。

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);
}

附录：

Reference answer 很好地说明了如何读取反汇编的字节码输出。感谢@Delgan
很好地描述了 CPython 的字符串实习。来自@ShadowRanger

Answer 2

比较匹配的字符串并不总是更快。相反，比较共享相同 id 的字符串总是更快。证明身份确实是这种行为的原因（正如@S3DEV 出色地解释的那样）是这个：

>>> 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 和 z 之间的比较比 x 之间的比较慢和 y，这是因为 x 和 z 不共享相同的 ID）。

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

Why is it faster to compare strings that match than strings that do not?

python

performance

comparison