Numba vs Cython循环优化

Question

考虑以下四种功能(python,numba,cython和smart给定的相同的整数输入时),其计算相同的反应

def python(n):
    total = 0
    for m in range(1,n+1):
        total += m
    return total

from numba import jit
numba = jit(python)

cpdef int cython(int n):
    cdef int total = 0
    cdef int m
    for m in range(1, n+1):
        total += m
    return total

def smart(n):
    return n * (n + 1) // 2

他们的执行时间让我感到有些惊讶

1. numba运行时间独立于n(虽然cython是线性的n)
2. numba 比...慢 smart

这立即引发了两个问题:

1. 为什么Numba,但不是Cython,能够把它变成一个恒定时间算法？
2. 鉴于Numba 确实设法将其转换为常量时间算法,为什么它比纯Python的常量时间函数慢smart？

由于我不是汇编程序maven,查看生成的代码并没有真正给我提供很多线索,除此之外,Numba生成的中间LLVM代码仍然出现(尽管我可能误解了)包含循环......我绝对迷失在最终由此产生的x64中.(除非有人问,否则我不会发布生成的代码,因为它们相当长.)

我在x64 Linux上,在Jupyter笔记本中运行它,所以我怀疑Cython正在使用用于编译Python的GCC 4.4.7; 和llvmlite 0.20.0,这意味着LLVM 4.0.x.

编辑:

我也有时间

smart_numba = jit(smart)

和

cpdef int smart_cython(int n):
    return n * (n + 1) // 2

smart_numba并numba给出相同的时间,比(纯Python)慢 25%,慢于smart175%smart_cython.

这是否表明Cython在高效跨越Python /低级边界方面做得非常好,而Numba做得不好？或者还有别的东西吗？

Answer 1

1. 这似乎是一个LLVM VS GCC的事情-见编译探险例子在这里,这比什么numba吐出噪音更小.我在程序集中有点丢失,但相当清楚GCC输出有一个循环(jgeto .L6)而clang输出没有.另请参阅GCC bugtracker上的此问题.

2. 在我的机器上(Windows x64)numba并没有明显慢smart,只有大约9 ns.这个开销似乎是由于numba的类型调度机制 - 如果你通过选择一个特定的重载来消除它,那么numba版本比python版本更快

这是我的时间

In [73]: %timeit numba_sum(10000)
182 ns ± 1.69 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

In [74]: %timeit smart(10000)
171 ns ± 2.26 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

# pick out int64 overload
i64_numba_sum = numba_sum.get_overload((numba.int64,))

In [75]: %timeit i64_numba_sum(10000)
94 ns ± 1.41 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)