编程珍珠和Python陷阱

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

编程珍珠和Python失败

计算机科学书籍包含了永恒的智慧,但性能的意见永远不会过时。 当阅读“编程珍珠”(作者:Jon Bentley)时, 我发现了很多意见进步带来的编程智慧。

考虑以下问题:

将n个元素的数组向左旋转i个位置。 例如,将“abcdefgh”旋转3得到“defghabc”。 是否可以做到这一点,并与n成正比?

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

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

考虑下用例,算法应该能够设计的高效。

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



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

(A’ B’) ‘ -> BA

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

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

derp = array.array("i", range(10000))def profile_juggle():    for i in range(10000):        juggle_swap(derp, 700)t1 = time.clock()profile_juggle()t2 = time.clock()print("{}: {} seconds".format("juggle swap", t2-t1))

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

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


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

使用列表时会发生什么?

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

def juggle_swap_inlined(xs, start):    length = len(xs)    gcdresult = fractions.gcd(length, start)    for i in range(gcdresult):        t = xs[i]        prev = i        next = i + start        while next != i:            xs[prev] = xs[next]            prev = next            next = (next + start) % length        xs[prev] = t


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

def reverse(xs, a, b):    while b > a:        t = xs[a]        xs[a] = xs[b]        xs[b] = t        b -= 1        a += 1def reverse_swap(xs, start):    length = len(xs)    reverse(xs, 0, start - 1)    reverse(xs, start, length - 1)    reverse(xs, 0, length - 1)

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

测评代码如下:

derp = list(range(10000))def profile_reverse():    for i in range(10000):        reverse_swap(derp, 700)def profile_juggle():    for i in range(10000):        juggle_swap_inlined(derp, 700)def profile_juggle_uninlined():    for i in range(10000):        juggle_swap(derp, 700)def manual_timer():    profiling_sets = [        (profile_reverse, "Reverse Function"),        (profile_juggle, "Juggle Function - Inlined Version"),        (profile_juggle_uninlined, "Juggle Function - Uninlined Version")            ]    for fn, word in profiling_sets:        t1 = time.clock()        fn()        t2 = time.clock()        print("{}: {} seconds".format(word, t2-t1))


我们来看看结果:

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

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

让我们来看看效果:

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

我们可以进一步提高吗?

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

#!python#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, nonecheck=False, overflowcheck=False, cdivision=True# The previous lines sets the compiler flags for Cython, I've turned on all the options which I think improves performancecdef void juggle_swap_c(int cc[], int start, int length):    cdef int gcdresult = gcd(length, start)    cdef int t, prev, next    cdef int i    for i in range(gcdresult):        t = cc[i]        prev = i        while True:            next = (prev + start) % length            if next == i:                break            cc[prev] = cc[next]            prev = next        cc[prev] = tcdef void reverse_c(int xs[], int a, int b):    while b > a:        t = xs[a]        xs[a] = xs[b]        xs[b] = t        b -= 1        a += 1cdef void reverse_swap_c(int xs[], int start, int length):    reverse_c(xs, 0, start - 1)    reverse_c(xs, start, length - 1)    reverse_c(xs, 0, length - 1



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

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

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


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


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


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

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

运行perf, 结果如下:

(反向旋转算法)


(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代码:

 
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+回车)换行