PyPy比Python快17倍.Python可以加速吗？

Question

解决了最近出现的代码问题,我发现我的默认Python比PyPy慢约40倍.通过在函数中运行限制调用和限制全局查找,我能够通过此代码将其降低到大约17倍len.

现在,e.py在python 3.6.3上运行5.162秒,在我的机器上在PyPy上运行.297秒.

我的问题是:这是JIT的不可缩短的加速,还是有某种方法可以加速CPython的回答？(没有极端的意思:我可以去Cython/Numba或其他什么？)我如何说服自己,我无能为力？

---

请参阅gist以获取数字输入文件列表.

如问题陈述中所述,它们代表跳跃偏移.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让我在2x内

编辑:我写的最好的Cython可以降到1.32s,比4x多一点的pypy

编辑:cmd按照@viraptor的建议将变量移动到cdef中,使Cython降低到.157秒!近幅度的一个完整的订单更快,而不是说从普通蟒蛇远.尽管如此,我对PyPy JIT的印象非常深刻,PyPy JIT完全免费完成了这一切!

Answer 1

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

更新:将偏移数组转换为指针数组,将其加速另一个因子1.5倍(简单寻址模式+ add从关键路径循环承载的依赖链中删除一个,将其降低到仅4个周期的L1D负载使用简单寻址模式的延迟,而不是6c = 5c + 1c).但我认为我们可以对Python很慷慨而不期望它跟上算法转换以适应现代CPU:P(特别是因为我使用32位指针即使在64位模式下也能确保4585元素阵列仍然只有18kiB所以它适合32kiB L1D缓存.)

此外,更新的替代表达式获取gcc以将其编译为无分支.(add在这个答案中留下了注释和原始输出,因为有趣的是看到无分支与错误预测的分支效果.)

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 perf stat,内部循环是无分支的; 它对条件使用条件移动-O3 -march=skylake.我>=3之所以使用,是因为我希望编译器会这样做. Godbolt编译器资源管理器上的Source + asm

.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

这是? :我的i7-6700k Skylake CPU 的输出 (对于clang版本):

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.下一次迭代的加载地址取决于此迭代的加载+添加,并且无序执行无法隐藏.但它可以重叠更新当前位置值的所有工作.

从更改perf stat ./a.out < input.txt到int没有性能下降(正如预期; short具有与movsxSkylake 相同的延迟),但是内存消耗减半,因此如果需要,更大的阵列可以适合L1D缓存.

我尝试将数组编译到程序中(因为mov它不需要被读取和解析.它也使得大小成为编译时常量.这将运行时间减少到~36.2 +/- 0.1毫秒,从〜下降36.8,所以从文件中读取的版本仍然花费大部分时间是实际问题,而不是解析输入.

如前所述,使用简单寻址模式进行指针追踪,int offsets[] = { file contents with commas added };而不是[rdi]具有1c较低的延迟,并避免[rdi + rdx*4](add变为index += offset).英特尔,因为IvyBridge current = target在寄存器之间具有零延迟整数,因此不会延长关键路径.这是hacky优化的源(带注释)+ asm.典型的运行(文本解析为a mov)std::vector:,90.725 M个周期(3.900 GHz),23.26 +- 0.05 ms(3.18 IPC).有趣的是,它实际上是更多的总指令,但由于循环携带的依赖链的延迟较低,因此运行速度更快.

gcc使用分支,速度大约慢2倍.(根据288.724 M instructions整个程序,14%的分支被错误预测.它只是作为更新值的一部分进行分支,但分支未命中使管道失效,因此它们也会影响关键路径,而数据依赖性不在此处.优化器似乎做出了糟糕的决定.)

重写条件作为perf stat说服gcc去asless看起来不错的asm.

gcc7.1.1 -O3 -march = skylake(用于编译分支的原始源offset[location] = (off>=3) ? off-1 : off+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实现,抱歉.

Answer 2

您可以改进一些小事情，但 pypy（很可能）在这项任务中总是更快。

对于 CPython 和 Cython：

• 不要一次读入整个文件。您可以随时迭代线路，这可以节省（重新）分配成本。但这需要您预先分配数组。
• 也许从列表切换到数组。

对于赛通：

• 标记变量类型。特别是作为 s 的计数器int和作为 s 数组的命令int可以跳过大多数类型检查。