Cython：纯C循环优化

Question

引用Cython 文档的话：

Cython recognises the usual Python for-in-range integer loop pattern:
    for i in range(n):
        ...
If i is declared as a cdef integer type, it will optimise this into a pure C loop

我写了一个简单的Cython函数，其中一个版本使用Python的range，另一个版本使用for-from Pyrex记法（它被认为是过时的）：

 def loop1(int start, int stop, int step):
    cdef int x, t = 0
    for x in range(start, stop, step):
        t += x
    return t

def loop2(int start, int stop, int step):
    cdef int x, t = 0
    for x from start <= x < stop by step:
        t += x
    return t

通过查看.c文件，我注意到这两个循环被处理的方式非常不同：

第一个实际上是创建了一个Python范围，使用Python对象。并且它还包含了50行不必要的Python-to-C C-to-Python的转换代码。

第二个已经被优化为一个漂亮的纯C循环：

__pyx_t_1 = __pyx_v_stop;
__pyx_t_2 = __pyx_v_step;
for (__pyx_v_x = __pyx_v_start; __pyx_v_x < __pyx_t_1; __pyx_v_x+=__pyx_t_2) {

我是否遗漏了什么信息，还是这是一个需要我报告的bug？

- Vincent

Answer 1

文档中提到了以下内容：

自动范围转换

这将把形如 for i in range(...) 的语句转换为当 i 是任何 cdef 类型的整数时，for i from ... 的形式，并且可以确定方向（即步长的符号）。

我想 Cython 希望在编译时知道步长的符号，以便在 C 循环的结束条件中生成 < 或 >。

另请参见Cython Trac 上的 Ticket #546

- Janne Karila

---

我还尝试用unsigned int替换int，但结果仍然相同。而且我不知道如何告诉Cython步长的符号。 - Vincent

Answer 2

我知道这是一个非常老的问题，但对于通过谷歌搜索并最终到达此处的人，我将发布一个答案。

https://github.com/cython/cython/issues/3310#issuecomment-707252866

for i in range(start, stop, step):
    ...

to this:

i = start - step
for _ in range(((stop - start) + (step - 1))//step):
    i += step
    ...    

- Underscore_

Answer 3

实际上，只要起始点、终止点和步长是C变量，就可以将任何一个针对范围的for循环转换为完全优化的C循环。你只需要写得巧妙一些。

首先看看loop1()：

def loop1(int start, int stop, int step):
    cdef int x, t = 0
    for x in range(start, stop, step):
        t += x
    return t

Cython（当前）无法优化此问题，因为它不知道step的符号。事实证明，这个问题的最简单解决方案是稍微更一般性的问题的解决方案。具体而言：

def loop1(int start, int stop, int step):
    cdef:
        int x
        int count
        int t = 0
    for count, x in enumerate(range(start, stop, step)):
        t += x
    return t

< p > count 变量看起来没用，但是问题的另一个版本可能会在循环体中使用它。

现在，手动计算索引:

def loop1(int start, int stop, int step):
    cdef:
        int x
        int count
        int length
        int t = 0
    length = len(range(start, stop, step))  # could optimize this further
    for count in range(length):
        x = start + count*step
        t += x
    return t

我已经尝试过这个方法，我知道它会生成纯C代码（除了length =这一行）。事实上，我已经在nogil块中成功使用了它。cython -a显示循环本身的输出全部为白色。

这将创建两个额外的变量，以及一些未使用的存储等，但我认为任何半好的编译器都应该能够在-O2上消除这些问题。因此，它适用于高性能循环。

- Kevin

---

这是有道理的，但如果您知道步长的符号，Pyrex语法for x from start <= x < stop by step仍然更方便。不过，如果Cython能够像这里讨论的那样处理range(a,b,c)语法，那就太好了。 - Vincent

最后一条评论是3年前，推荐了一个类似于我的解决方案。我不知道Cython开发人员现在在做什么，但那个bug不是他们正在处理的。 - Kevin