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

Question

我正在尝试评估是否比较两个字符串随着它们的长度增加而变慢.我的计算建议比较字符串应该采用摊销的常数时间,但我的Python实验会产生奇怪的结果:

下面是字符串长度(1到400)与时间(以毫秒为单位)的关系图.禁用自动垃圾收集,并gc.collect在每次迭代之间运行.

我每次比较100万个随机字符串,计算匹配如下.过程重复50次,然后取所有测量时间的min.

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)

进一步说明:我做了两个额外的测试:比较字符串is而不是==完全抑制问题,性能大约是210ms/1M比较.由于已经提到实习,我确保在每根弦之后增加一个空格,这样可以防止实习; 这不会改变任何事情.那不是实习吗？

Answer 1

Python 可以 "实习"短字符串; 将它们存储在特殊缓存中,并重新使用该缓存中的字符串对象.

然后在比较字符串时,它首先测试它是否是相同的指针(例如一个实习字符串):

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

只有当指针比较失败时,它才会使用大小检查并memcmp比较字符串.

通常只对标识符(函数名,参数,属性等)进行实习,但不适用于在运行时创建的字符串值.

另一个可能的罪魁祸首是字符串常量; 代码中使用的字符串文字在编译时存储为常量并在整个过程中重用; 再次只创建一个对象,并且身份测试更快.

对于不相同的字符串对象,Python测试相等长度,相等的第一个字符然后使用memcmp()内部C字符串上的函数.如果您的字符串未被实习或以其他​​方式重复使用相同的对象,则所有其他速度特性都归结为该memcmp()功能.