编程珠玑和Python陷阱

Python部落(python.freelycode.com)组织翻译,禁止转载,欢迎转发。

计算机科学书籍包含了永恒的智慧,但有关性能的意见却不是总能奏效。 当阅读“编程珠玑”(作者:Jon Bentley)时, 我发现了很多硬件进步推翻了旧有的编程智慧。

考虑以下问题:

将n个元素的数组向左循环移动i位。 例如,将“abcdefgh”向左循环移动3位得到“defghabc”。 是否可以做到类似原地排序(“”in place“”, 即不占用额外内存)的特点,并且时间复杂度与n成正比?

这个问题模拟了真实计算场景中的几个问题:

    1.在文本编辑器中移动文本可以看作是旋转要移动到新位置的文本。
    2.交换彼此相邻的不相等的内存块。

考虑到这样的使用场景,算法要设计得高效才行。

第一个算法涉及一个微妙的诀窍:取第1个元素,然后将它移动i位到达最终位置,然后把i位上的元素移动到2i的位置,依此类推。 不断重复,直到整个阵列被旋转。

1.jpeg
考虑这个问题的另一种方法是将数组视为两个不同的段,A和B,然后旋转数组与将数组AB转换为数组BA相同。 如果我们可以反转A产生A',那么

(A’ B’) ‘ -> BA

第一种算法读取和写入每个数组元素一次。 反转循环读取和写入每个数组元素两次。 传统的智慧将导致我们得出结论:第一种算法运行得更快。 在编程珠玑这本书里,作者提到是两倍快。 这个结果在21世纪的今天仍然成立吗?

这里是一个在Python中juggle rotate(旋转)算法(第一种算法)的实现:

image.png

通过使用类型化的Python数组,我认为这将导致比列表更好的性能。 不幸的是,我犯了过早优化的罪。

对10000个元素的Python数组运行juggle旋转并重复10000次,得到以下结果:

2.png


我在4GHz的Intel i7-6700K上运行测试。 作为一个快速的健全检查,我的CPU应该能够进行每秒几十亿整数操作。 juggle旋转移动大约10万个整数(10000个元素* 10000次重复),15秒看起来还是长了点,尽管结果如此。

使用列表时会发生什么?
3.png

效果稍好,但仍不是很大。 阅读Python的源代码表明,元素检索过程中,Python将创建PyObject并且封装结果。 每次访问它从未见过的整数时,都会产生此成本。 如果我们用内联函数怎么样?

image.png

4.png


对,没有函数内联。 不太好的地方像map()和filter, 其本质上是一遍又一遍地调用函数
反向旋转如何?

image.png

从两端开始,我们每次循环一个并交换元素,我们做3段反转。 很简单。

测评代码如下:

image.png


我们来看看结果:
5.png

此刻,因为反向操作看上去很慢,导致总体速度较慢。

好了,我们可以运行一个带JIT的Python环境,如PyPy 。

让我们来看看效果:
6.png

我们设法实现了10倍的加速功能和200倍的加速功能。 反向旋转现在比之前的juggle旋转快得多。

我们可以进一步提高吗?

通过用Cython ,并加入某种类型的注释,代码可以编译,消除更多的开销。 这里是转换后的函数 

image.png

7.png


另一方面,如果我们的CPU可以通过每秒数十亿的指令,那么全力处理千万个整数应该在百分之一秒量级,我们的反向交换算法做到了这一点 -- 0.07秒。

所有这一切都还是给我们留下了一个问题: 为什么反向旋转比juggle旋转速度更快,尽管其代码看上去做了更多工作和开销?

我在C中重新实现了这两个函数,我们在Linux下使用perf。

8.png


有趣的是,我们的C代码似乎比我们的Cython优化的代码慢,编译的Python代码如何运行的比C还快?
我将元素的数量增加到100万个整数,我们现在做了5000次重复,让我们再次重复Cython的结果

9.png


现在,来看看我们的C程序执行速度如何:

10.png

 关于基准测试的重要课程:始终确保它们运行足够长,以使结果不受其他因素的影响。

从我们的基准测试中,C的结果是,从中我们可以推断出Cython已经生成了非常纯的C。通过剖析我们的C程序,我们应该能够获得关于性能的结论性结果。

运行perf, 结果如下:

11.png

(反向旋转算法)


12.png

(juggle旋转算法)


有几个统计数据我想强调:

    1.看看L1数据缓存加载(L1-dcache-loads),反向交换的负载是juggle程序的两倍,这是我们所期望的:内存访问的两倍。
    2.反向交换算法在L1数据和最后级高速缓存(LLC)中具有少得多的高速缓存未命中,而juggle算法在高速缓存中的缺失带来了其速度上相当大的代价。

简而言之,与计算得时间成本相比,主存储器访问的时间成本是更昂贵的。 在SKYLAKE微架构的CPU中, 访问RAM的成本是42个周期+ 51纳秒 。 CPU高速缓存基于一个假设,即代码将频繁访问这些都是相互接近和数据访问在时间上接近的数据。 通过将这些数据放在高速缓存中,CPU只需要访问更快的高速缓存,而不是不断地访问主存储器。

有些人可能想知道,怎么会有128%的缓存未命中? 有一个复杂的答案https://sites.utexas.edu/jdm4372/2013/07/14/notes-on-the-mystery-of-hardware-cache-performance-counters/,CPU可能会尝试多次检索缓存中的某结果。

再看看juggle代码:
1.jpeg 
juggle算法通过在某个偏移处不断跳跃来访问存储器。 在较大的跳跃时,这对于CPU高速缓存是有害的 - 没有访问彼此接近的数据不断导致高速缓存未命中。 回顾perf的结果,在juggle算法中,有3200万最后一级缓存未命中, 与之相比在反向旋转中,只有6万3千个。

在反向旋转中,从两端以顺序方式访问存储器,数据访问是接近的,因此尽管读取和写入的次数是两次,但是我们获得了更好的速度。

值得注意的是,两种算法都具有相同的渐近增长函数,都是O(n)算法,但是由于缓存使用,它们在运行时间上具有不同的幅度。 还值得注意的是,在C ++中,反向旋转用作std :: rotate实现的一部分。

如果你想运行这个博客中的任何代码,他们都收集在这里:
https://github.com/FrozenXZeus/pyfails

结论:

    1.高速缓存访问模式相当重要! 他们可以经常打破性能瓶颈。
    2.谨防过早“优化” 。 仔细分析和验证你的假设。
    3.在将代码部署到生产时可考虑不同的Python解释器和Cython编译器。 一个例子是Pyston, Dropbox写的一个Python JIT。

作者: Franklin He
译者: zylpascal123
原文: https://hackernoon.com/programming-pearls-and-python-fails-c4fc2962c3ed#.2bhguxa0v

英文原文:https://hackernoon.com/programming-pearls-and-python-fails-c4fc2962c3ed#.bvzusi6ny
译者:zylpascal
 

2月15日11:00到13:00网站停机维护,13:00前恢复
iPy智能助手 双击展开
查看更多聊天记录
(Ctrl+回车)换行