PyPy比Python快17倍. Python可以加速吗?
解决了最近的
Advent of Code problem,我发现我的默认Python比PyPy慢了约40倍.通过限制对len的调用并通过在函数中运行来限制全局查找,我能够通过
this code将其降低到大约17倍.
现在,e.py在python 3.6.3上以5.162秒运行,在我的机器上在PyPy上运行.297秒. 我的问题是:这是JIT的不可缩短的加速,还是有某种方法可以加速CPython的回答? (没有极端的意思:我可以去Cython / Numba或其他什么?)我如何说服自己,我无能为力? 请参阅gist以获取数字输入文件列表. 如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.32s,略高于4x pypy 编辑:按照@viraptor的建议,将cmd变量移动到cdef中,使Cython降低到.157秒!几乎快了整整一个数量级,而且距离常规python不远.尽管如此,我对PyPy JIT的印象非常深刻,PyPy JIT完全免费完成了这一切! 解决方法
作为Python的基线,我用C编写了这个(然后决定使用C来实现更方便的数组I / O).它使用clang有效地编译x86-64.在Skylake x86上运行速度比问题代码CPython3.6.2快82倍,因此即使速度更快的Python版本仍然有几个因素可以跟上接近最佳的机器代码. (是的,我查看了编译器的asm输出,以检查它是否做得很好).
更新:将偏移数组转换为指针数组会将其加速另一个因子1.5倍(简单的寻址模式从关键路径循环承载的依赖链中删除一个加法,将其简化为4 cycle L1D load-use latency以实现简单的寻址模式,而不是6c = 5c 1c).但我认为我们可以对Python很慷慨而不期望它跟上算法转换以适应现代CPU:P(特别是因为我使用32位指针即使在64位模式下也能确保4585元素阵列仍然只有18kiB所以它适合32kiB L1D缓存.) 此外,更新的替代表达式获取gcc以将其编译为无分支. (注释掉了,并且在这个答案中留下了原始的perf stat输出,因为看到无分支与具有错误预测的分支的影响很有意思.) unsigned jumps(int offset[],unsigned size) { unsigned location = 0; unsigned counter = 0; do { //location += offset[location]++; // simple version int off = offset[location]; offset[location] += (off>=3) ? -1 : 1; // "conditional" version // 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); 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没有性能下降(如预期; 我尝试将数组编译到程序中(作为int offsets [] = {添加了逗号的文件内容};因此不必读取和解析它.它还使大小成为编译时常量.这减少了运行时间到~36.2 / – 0.1毫秒,低于~36.8,所以从文件读取的版本仍然花费大部分时间是实际问题,而不是解析输入. 如前所述,使用简单的寻址模式(如[rdi]而不是[rdi rdx * 4])进行指针追踪具有1c的较低延迟,并避免添加(index = offset变为current = target).英特尔,因为IvyBridge在寄存器之间具有零延迟整数运动,因此不会延长关键路径.这是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个指令(3.18 IPC).有趣的是,它实际上是更多的总指令,但由于循环携带的依赖链的延迟较低,因此运行速度更快. gcc使用分支,速度大约慢2倍. (根据整个程序中的perf stat,14%的分支被错误预测.它只是作为更新值的一部分进行分支,但分支未命中使管道停止,因此它们也会影响关键路径,因为数据依赖性不在此处这似乎是优化器的糟糕决定.) 将条件重写为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实现,抱歉. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |