python - PyPy 比 Python 快 17 倍。 Python可以加速吗？

Question

解决最近的一个 Advent of Code problem ，我发现我的默认 Python 比 PyPy 慢约 40 倍。我能够使用 this code 将其降低到大约 17 倍。通过限制对 len 的调用并通过在函数中运行来限制全局查找。

现在，e.py在 python 3.6.3 上运行 5.162 秒，在我机器上的 PyPy 上运行 0.297 秒。

我的问题是:这是 JIT 不可减少的加速，还是有什么方法可以加速 CPython 的答案？ (缺乏极端手段:我可以去 Cython/Numba 或其他什么？)我如何说服自己我无能为力？

请参阅数字输入文件列表的要点。

如 the problem statement 中所述，它们代表跳跃偏移量。 position += offsets[current] ，并将当前偏移量增加 1。当跳转将您带到列表之外时，您就完成了。

这是给出的示例(需要 5 秒的完整输入要长得多，并且数字更大):

(0) 3  0  1  -3  - before we have taken any steps.
(1) 3  0  1  -3  - jump with offset 0 (that is, don't jump at all). Fortunately, the instruction is then incremented to 1.
 2 (3) 0  1  -3  - step forward because of the instruction we just modified. The first instruction is incremented again, now to 2.
 2  4  0  1 (-3) - jump all the way to the end; leave a 4 behind.
 2 (4) 0  1  -2  - go back to where we just were; increment -3 to -2.
 2  5  0  1  -2  - jump 4 steps forward, escaping the maze.

编码:

def run(cmds):
    location = 0
    counter = 0
    while 1:
        try:
            cmd = cmds[location]
            if cmd >= 3:
                cmds[location] -= 1
            else:
                cmds[location] += 1
            location += cmd
            if location < 0:
                print(counter)
                break
            counter += 1
        except:
            print(counter)
            break

if __name__=="__main__":
    text = open("input.txt").read().strip().split("\n")
    cmds = [int(cmd) for cmd in text]
    run(cmds)

编辑:我用 Cython 编译并运行了代码，将运行时间降低到 2.53 秒，但这仍然比 PyPy 慢了几乎一个数量级。

编辑: Numba gets me to within 2x

编辑:最好的 Cython I could write下降到 1.32 秒，比 pypy 快 4 倍多一点

编辑:移动 cmd正如@viraptor 所建议的那样，将变量转换为 cdef，将 Cython 降低到 0.157 秒!快了近一个完整数量级，并且与常规 python 相差不远。尽管如此，PyPy JIT 给我留下了深刻的印象，它免费完成了所有这些!

Answer 1

作为 Python 的基线，我用 C 编写了它(然后决定使用 C++ 来实现更方便的数组 I/O)。它使用 clang++ 为 x86-64 高效编译。这运行 在 Skylake x86 上使用问题中的代码比 CPython3.6.2 快 82 倍 ，因此即使您的 Python 版本更快，与接近最佳机器代码的速度仍有一些距离。 (是的，我查看了编译器的 asm 输出以检查它是否做得很好)。

让一个好的 JIT 或提前编译器看到循环逻辑是这里性能的关键。 问题逻辑本质上是串行的，因此没有范围让 Python 运行已经编译的 C 来对整个数组(如 NumPy)执行某些操作，因为除非您使用 Cython 或其他东西，否则不会针对此特定问题编译 C .让问题的每一步都回到 CPython 解释器是性能的死亡，因为它的缓慢并没有被内存瓶颈或任何东西所掩盖。

更新:将偏移量数组转换为指针数组将其速度提高 1.5 倍 (简单寻址模式 + 从关键路径循环携带的依赖链中删除 add，将其降低到 4 cycle L1D load-use latency 用于简单寻址模式( when the pointer comes from another load )，而不是 6c = 5c + 1c 用于索引寻址模式 + add 延迟)。

但我认为我们可以对 Python 大方，不要指望它跟上算法转换以适应现代 CPU :P(特别是因为即使在 64 位模式下我也使用 32 位指针来确保 4585 元素数组仍然只是18kiB 所以它适合 32kiB L1D 缓存。就像 Linux x32 ABI 或 AArch64 ILP32 ABI 一样。)

此外，更新的替代表达式让 gcc 编译它，就像 clang 一样。 (注释掉并且原始 perf stat 输出留在这个答案中，因为有趣的是看到无分支与有错误预测的分支的效果。)

unsigned jumps(int offset[], unsigned size) {
    unsigned location = 0;
    unsigned counter = 0;

    do {
          //location += offset[location]++;            // simple version
          // >=3 conditional version below

        int off = offset[location];

        offset[location] += (off>=3) ? -1 : 1;       // branchy with gcc
        // offset[location] = (off>=3) ? off-1 : off+1;  // branchless with gcc and clang.  

        location += off;

        counter++;
    } while (location < size);

    return counter;
}

#include <iostream>
#include <iterator>
#include <vector>

int main()
{
    std::ios::sync_with_stdio(false);     // makes cin faster
    std::istream_iterator<int> begin(std::cin), dummy;
    std::vector<int> values(begin, dummy);   // construct a dynamic array from reading stdin

    unsigned count = jumps(values.data(), values.size());
    std::cout << count << '\n';
}

随着clang4.0.1 -O3 -march=skylake ，内循环是无分支的；它对 >=3 使用条件移动健康)状况。我用过 ? :因为那是我希望编译器会做的。 Source + asm on the Godbolt compiler explorer

.LBB1_4:                                # =>This Inner Loop Header: Depth=1
    mov     ebx, edi               ; silly compiler: extra work inside the loop to save code outside
    mov     esi, dword ptr [rax + 4*rbx]  ; off = offset[location]
    cmp     esi, 2
    mov     ecx, 1
    cmovg   ecx, r8d               ; ecx = (off>=3) ? -1 : 1;  // r8d = -1 (set outside the loop)
    add     ecx, esi               ; off += -1 or 1
    mov     dword ptr [rax + 4*rbx], ecx  ; store back the updated off
    add     edi, esi               ; location += off  (original value)
    add     edx, 1                 ; counter++
    cmp     edi, r9d
    jb      .LBB1_4                ; unsigned compare against array size

这是 perf stat ./a.out < input.txt 的输出(对于 clang 版本)，在我的 i7-6700k Skylake CPU 上:

21841249        # correct total, matches Python

 Performance counter stats for './a.out':

         36.843436      task-clock (msec)         #    0.997 CPUs utilized          
                 0      context-switches          #    0.000 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               119      page-faults               #    0.003 M/sec                  
       143,680,934      cycles                    #    3.900 GHz                    
       245,059,492      instructions              #    1.71  insn per cycle         
        22,654,670      branches                  #  614.890 M/sec                  
            20,171      branch-misses             #    0.09% of all branches        

       0.036953258 seconds time elapsed

由于循环中的数据相关性，平均每时钟指令数远低于 4。下一次迭代的加载地址取决于本次迭代的加载+添加，乱序执行无法隐藏这一点。但是，它可以重叠更新当前位置值的所有工作。

更改自 int至 short没有性能下降(正如预期的那样； movsx has the same latency as mov on Skylake)，但内存消耗减半，因此如果需要，更大的阵列可以放入 L1D 缓存。

我尝试将数组编译到程序中(如 int offsets[] = { file contents with commas added }; 所以它不必被读取和解析。它还使大小成为编译时常量。这将运行时间减少到 ~36.2 +/- 0.1 毫秒，从 ~36.8 下降，所以从文件读取的版本仍然把大部分时间花在实际问题上，而不是解析输入。(与 Python 不同，C++ 的启动开销可以忽略不计，我的 Skylake CPU 上升到最大时钟速度由于 Skylake 中的硬件 P 状态管理，在不到一毫秒的时间内完成。)

如前所述，使用简单的寻址模式(如 [rdi])进行指针追踪而不是 [rdi + rdx*4]具有 1c 更低的延迟，并避免了 add ( index += offset 变成 current = target )。 Intel 因为 IvyBridge 具有零延迟整数 mov寄存器之间，这样就不会延长关键路径。这是 the source (with comments) + asm for this hacky optimization .典型的运行(文本解析为 std::vector ): 23.26 +- 0.05 ms , 90.725 M 周期 (3.900 GHz), 288.724 M instructions (3.18 IPC)。有趣的是，它实际上是更多的总指令，但由于循环携带的依赖链的延迟较低，因此运行速度要快得多。

gcc 使用一个分支，它大约慢 2 倍。 (14% 的分支根据 perf stat 在整个程序中被错误预测。 它只是作为更新值的一部分的分支，但分支未命中会导致管道停滞，因此它们也会影响关键路径，以数据依赖的方式不要在这里。这似乎是优化器的一个糟糕决定。)

将条件重写为 offset[location] = (off>=3) ? off-1 : off+1;说服 gcc 使用看起来不错的 asm 去无分支。

gcc7.1.1 -O3 -march=skylake (对于使用 (off <= 3) ? : -1 : +1 的分支编译的原始源代码)。

Performance counter stats for './ec-gcc':

     70.032162      task-clock (msec)         #    0.998 CPUs utilized          
             0      context-switches          #    0.000 K/sec                  
             0      cpu-migrations            #    0.000 K/sec                  
           118      page-faults               #    0.002 M/sec                  
   273,115,485      cycles                    #    3.900 GHz                    
   255,088,412      instructions              #    0.93  insn per cycle         
    44,382,466      branches                  #  633.744 M/sec                  
     6,230,137      branch-misses             #   14.04% of all branches        

   0.070181924 seconds time elapsed

对比 CPython(Arch Linux 上的 Python3.6.2) :

perf stat python ./orig-v2.e.py
21841249

 Performance counter stats for 'python ./orig-v2.e.py':

       3046.703831      task-clock (msec)         #    1.000 CPUs utilized          
                10      context-switches          #    0.003 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               923      page-faults               #    0.303 K/sec                  
    11,880,130,860      cycles                    #    3.899 GHz                    
    38,731,286,195      instructions              #    3.26  insn per cycle         
     8,489,399,768      branches                  # 2786.421 M/sec                  
        18,666,459      branch-misses             #    0.22% of all branches        

       3.046819579 seconds time elapsed

我没有安装 PyPy 或其他 Python 实现，抱歉。