python - 为什么某些实现在Python中运行缓慢？

Question

我有一个函数的三种实现，用于检查字符串（或空格分隔的短语）是否是回文式：

def palindrome(str_in):
    def p(s, i, j):
        if i >= j:
            return True
        elif s[i] != s[j]:
            return False
        else:
            return p(s, i+1, j-1)
    return p(str_in.replace(' ', '').lower(), 0, len(str_in)-1)

def palindrome1(s):
    st = s.replace(' ', '').lower()
    return st == st[::-1]

def palindrome2(s):
    st = s.replace(' ', '').lower()
    i, j = 0, len(st)-1
    while i < j:
        if st[i] != st[j]:
            return False
        else:
            i += 1
            j -= 1
    return True

现在，我认为 palindrome()在理论上是最佳的，因为不会发生反转并且不会发生额外的内存，但是python没有尾调用优化。 palindrome2()是 palindrome()的命令性版本，但仍比 palindrome1()花费更长的时间。为什么是这样？

以下是分析结果（运行： python -m cProfile file.py）：

         12 function calls in 45.341 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.232    0.232   45.341   45.341 file.py:1(<module>)
        1    2.198    2.198    3.532    3.532 file.py:300(palindrome1)
        1   39.442   39.442   40.734   40.734 file.py:304(palindrome2)
        1    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    2.396    1.198    2.396    1.198 {method 'lower' of 'str' objects}
        1    0.843    0.843    0.843    0.843 {method 'read' of 'file' objects}
        2    0.231    0.115    0.231    0.115 {method 'replace' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {open}
        1    0.000    0.000    0.000    0.000 {sys.setrecursionlimit}

这是分析结果（运行： pypy -m cProfile hw2.py）：

         11 function calls in 12.470 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.011    0.011   12.470   12.470 hw2.py:1(<module>)
        1    2.594    2.594    6.280    6.280 hw2.py:303(palindrome1)
        1    0.852    0.852    4.347    4.347 hw2.py:307(palindrome2)
        1    0.000    0.000    0.000    0.000 {len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        2    3.263    1.631    3.263    1.631 {method 'lower' of 'str' objects}
        1    1.832    1.832    1.832    1.832 {method 'read' of 'file' objects}
        2    3.918    1.959    3.918    1.959 {method 'replace' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {sys.setrecursionlimit}

这是我的回文构造函数：

def palindrome_maker(n):
    from random import choice
    alphabet = ' abcdefghijklmnopqrstuvwxyz'
    front = ''.join([choice(alphabet) for _ in range(n//2)])
    back = front[::-1]
    return front + (choice(alphabet) if n%2==1 else '') + back

顺便说一句：该配置文件显示了调用长度为 999999999的字符串的函数的性能。

Answer 1

好的，让我们从头开始讨论。 CPython将可见的文本编译为字节码，这是一种表示形式，虚拟机（即解释器）更容易理解。

由于此开销，palindrome和palindrome2函数都比palindrome1慢。 CPython中有一个名为dis的简洁模块。如果在编译函数上使用它，它将显示其内部表示。因此，让我们这样做：

>>> dis.dis(palindrome)
  2           0 LOAD_CLOSURE             0 (p)
              3 BUILD_TUPLE              1
              6 LOAD_CONST               1 (<code object p at 0x01B95110, file "<stdin>", line 2>)
              9 LOAD_CONST               2 ('palindrome.<locals>.p')
             12 MAKE_CLOSURE             0
             15 STORE_DEREF              0 (p)

  9          18 LOAD_DEREF               0 (p)
             21 LOAD_FAST                0 (str_in)
             24 LOAD_ATTR                0 (replace)
             27 LOAD_CONST               3 (' ')
             30 LOAD_CONST               4 ('')
             33 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             36 LOAD_ATTR                1 (lower)
             39 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             42 LOAD_CONST               5 (0)
             45 LOAD_GLOBAL              2 (len)
             48 LOAD_FAST                0 (str_in)
             51 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             54 LOAD_CONST               6 (1)
             57 BINARY_SUBTRACT
             58 CALL_FUNCTION            3 (3 positional, 0 keyword pair)
             61 RETURN_VALUE

现在让我们将其与 palindrome1函数进行比较：

>>> dis.dis(palindrome1)
  2           0 LOAD_FAST                0 (s)
              3 LOAD_ATTR                0 (replace)
              6 LOAD_CONST               1 (' ')
              9 LOAD_CONST               2 ('')
             12 CALL_FUNCTION            2 (2 positional, 0 keyword pair)
             15 LOAD_ATTR                1 (lower)
             18 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             21 STORE_FAST               1 (st)

  3          24 LOAD_FAST                1 (st)
             27 LOAD_FAST                1 (st)
             30 LOAD_CONST               0 (None)
             33 LOAD_CONST               0 (None)
             36 LOAD_CONST               4 (-1)
             39 BUILD_SLICE              3
             42 BINARY_SUBSCR
             43 COMPARE_OP               2 (==)
             46 RETURN_VALUE

因此，这就是CPython或多或少看到的（实际上，它们被编码为二进制形式，目前不相关）。然后，虚拟机遍历这些行并逐一执行它们。

因此，第一个显而易见的事情是：更多的行==更多的执行时间。这是因为必须解释每一行并且必须执行适当的C代码。由于循环和递归调用，除了 palindrome1以外，两个函数中都有很多行执行。因此，从本质上讲，这就像您尝试跑几圈，但Python表示“不，不，不，您必须肩负20公斤的重量”。圈数越多（即执行的字节码越多），您获得的速度就越慢。通常，这种性能下降在CPython中应该是线性的，但是真的有谁知道而无需阅读CPython的代码？我听说应该在CPython中实现一种称为 inline caching的技术，这会大大影响性能。我不知道它是否完成。

另一件事是，Python中的调用非常昂贵。 ABI给出了如何在低层进行调用（即将寄存器压入堆栈并进行跳转）。 C / C ++紧随其后。现在，Python的功能远不止这些。创建了一些帧（可以进行分析（例如，在发生异常时进行分析），最大递归检查等），所有这些都将导致性能损失。

因此 palindrome函数可以进行大量调用。递归在Python中效率低下。特别是这就是为什么 palindrome2比 palindrome1更快的原因。

另一件事是 palindrome1具有 [::-1]可以转换为用C实现的 BUILD_SLICE调用。因此，尽管这样做的必要性更高（没有理由创建字符串的另一个副本），但它仍然更快那么其他功能仅仅是因为中间层（即字节码）最小。编译器无需在字节码解释上浪费时间。

另一个重要的事情是，必须用垃圾回收您在Python中创建的每个对象。并且由于这些对象通常比纯C对象大（例如，由于引用计数器），因此花费更多时间。嗯，顺便说一下，增加和减少参考计数器也要花费时间。还有一个叫做GIL（全局解释器锁）的东西，它在每个命令处获取并释放一个锁，以便字节码是线程安全的。即使对于单线程应用程序完全没有必要。但是Python不知道您不会在某个时候运行线程，它每次都必须这样做。这就是所有这些，因此您不必担心大多数C / C ++编码人员必须处理的棘手问题。 :)

现在，PyPy是另一个故事。它内部有一个名为JIT = Just In Time的编译器。它需要做什么，它需要任何Python字节码并将其即时转换为机器代码，然后可以重复使用。因此，对函数的初始调用具有此编译开销，但是它仍然更快。最终根本没有字节码，所有功能都完全在CPU上运行。但是，这并不意味着PyPy的速度与用C编写的函数一样快（例如 [::-1]）。仅仅因为有很多优化是在C级别上完成的，我们不知道如何在PyPy或任何其他Python解释器中实现。这是由于语言的性质-它是动态的。现在，是否真的不可能是另外一个故事，这一点也不明显，但是目前我们还不知道该怎么做。

tl; dr;内置函数（或更一般地说，在Python中运行的C代码）总是至少与同等的纯Python代码一样快，并且在大多数情况下要快得多