python - Cython实现不比纯python快

Question

为了练习，我编写了一个XOR双链表

%%cython

from cpython.object cimport PyObject
from cpython.ref cimport Py_XINCREF, Py_XDECREF
from libc.stdint cimport uintptr_t

cdef class Node:
    cdef uintptr_t _prev_xor_next
    cdef object val

    def __init__(self, object val, uintptr_t prev_xor_next=0):
        self._prev_xor_next=prev_xor_next
        self.val=val

    @property
    def prev_xor_next(self):
        return self._prev_xor_next
    @prev_xor_next.setter
    def prev_xor_next(self, uintptr_t p):
        self._prev_xor_next=p

    def __repr__(self):
        return str(self.val)


cdef class CurrentNode(Node):
    cdef uintptr_t _node, _prev_ptr
    def __init__(self, uintptr_t node, uintptr_t prev_ptr=0):
        self._node = node
        self._prev_ptr= prev_ptr

    @property
    def val(self):
        return self.node.val
    @property
    def node(self):
        ret=<PyObject *> self._node
        return <Node> ret
    @property
    def prev_ptr(self):
        return self._prev_ptr

    cdef CurrentNode forward(self):
        if self.node.prev_xor_next!=self._prev_ptr:
            return CurrentNode(self.node.prev_xor_next^self._prev_ptr, self._node)

    cdef CurrentNode backward(self):
        if self._prev_ptr:
            pp=<PyObject*>self._prev_ptr
            return CurrentNode(self._prev_ptr, self._node^(<Node> pp).prev_xor_next)

    def __repr__(self):
        return str(self.node)

cdef class XORList:
    cdef PyObject* first
    cdef PyObject* last
    cdef int length

    def __init__(self):
        self.length=0
    @property
    def head(self):
        return (<Node> self.first)

    @property
    def tail(self):
        return (<Node> self.last)

    cdef append(self, object val):
        self.length+=1
        #empty list
        if not self.first:
            t=Node(val)
            tp=(<PyObject*> t)
            self.first=tp
            Py_XINCREF(tp)
            self.last=tp
            Py_XINCREF(tp)

        #not empty
        else:
            new_node=Node(val, <uintptr_t> self.last)
            new_ptr=<PyObject*> new_node
            cur_last=<Node>self.last
            cur_last.prev_xor_next=cur_last.prev_xor_next^(<uintptr_t> new_ptr)
            Py_XINCREF(new_ptr)
            self.last=new_ptr
            Py_XINCREF(new_ptr)

    cpdef reverse(self):
        temp=self.last
        self.last=self.first
        self.first=temp

    def __repr__(self):
        return str(list(iter_XORList(self)))
    def __len__(self):
        return self.length

def iter_XORList(l):
    head=<PyObject*>l.head
    cur=CurrentNode(<uintptr_t> head)
    while cur:
        yield cur
        cur=cur.forward()

import time

start=time.time()
cdef XORList l=XORList()
for i in range(100000):
    l.append(i)
print('time xor ', time.time()-start)

start=time.time()
l1=[]
for i in range(100000):
    l1.append(i)
print('time regular ', time.time()-start)

使用上面的内置列表，在cython链接列表上，我的性能持续下降约10倍。

time xor  0.10768294334411621
time regular  0.010972023010253906

当我分析xorlist的循环时，我得到：

         700003 function calls in 1.184 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.184    1.184 <string>:1(<module>)
        1    0.039    0.039    1.184    1.184 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:108(list_check)
   100000    0.025    0.000    0.025    0.000 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:11(__init__)
    99999    0.019    0.000    0.019    0.000 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:16(__get__)
    99999    0.018    0.000    0.018    0.000 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:19(__set__)
        1    0.000    0.000    0.000    0.000 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:60(__init__)
   100000    0.937    0.000    0.999    0.000 _cython_magic_14cf45d2116440f3df600718d58e4f95.pyx:70(append)
   100000    0.113    0.000    1.146    0.000 line_profiler.py:111(wrapper)
        1    0.000    0.000    1.184    1.184 {built-in method builtins.exec}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   100000    0.018    0.000    0.018    0.000 {method 'disable_by_count' of '_line_profiler.LineProfiler' objects}
   100000    0.015    0.000    0.015    0.000 {method 'enable_by_count' of '_line_profiler.LineProfiler' objects}

因此，忽略对 append的调用，似乎大部分时间都花在了特殊方法上。

这使我想到了以下问题：


我怎样才能加快速度
我认为Cython中的扩展类型是通过结构实现的，所以导致它们初始化的时间太长了


我还尝试了在纯python中对普通双向链表的另一种自定义实现，并且它与cython xorlist的时序在我的机器上相差10％以内。

Answer 1

分析中的三个罪魁祸首是Node的__init__（在这里是不可避免的），以及__get__和__set__的prev_xor_next属性。我的观点是，您不希望使用prev_xor_next属性（或者如果您这样做的话，它应该是只读的），因为它可以使Python内部的Cython内部访问。

无论是否删除该属性，都在此处使用Cython，以便可以直接写入基础C属性_prev_xor_next。您可能需要在cdef Node cur_last的开头（以及可能在其他函数中）设置append，以确保Cython知道cur_last的类型-我认为它应该可以解决，但是如果您得到 在运行时，这就是您需要做的。

这项更改使我的速度提高了30％（即，它的速度仍然比常规列表慢，但这是一个明显的改进）。



我将概述一个更剧烈的变化，我可能应该在关于这个问题的第一个问题上提出建议。这确实是一个模糊的大纲，因此没有为使其工作而作任何努力。


AttributeErrors完全在 Node类的内部：不应在Python中使用它，并且 XORList中所有 Nodes的生存期都直接与列表绑定。因此，应该在销毁自己的 XORList时破坏它们（或者如果列表缩小，等等），因此不必进行引用计数。因此， XORList应该是C结构而不是Python对象：

cdef struct Node:
    uintptr_t prev_xor_next
    PyObject* val

# with associated constructor- and destructor-like functions:
cdef Node* make_node(object val, uintptr_t prev_xor_next):
    cdef Node* n = <Node*>malloc(sizeof(Node))
    n.val = <PyObject*>val
    Py_XINCREF(n.val)
    n.prev_xor_next = prev_xor_next
    return n

cdef void destroy_node(Node* n):
    Py_XDECREF(n.val)
    free(n)

Node需要一个 XORList函数，该函数循环遍历在每个 __dealloc__上调用 destroy_node的列表（在您的版本中也需要一个 Node函数！）
__dealloc__需要保持Cython类，因为这是您的“迭代器”界面。它显然不再可以从 CurrentNode继承。我将其更改为：

cdef class XORListIterator:
    cdef Node* current_node
    cdef XORList our_list

属性 Node的目的是确保 our_list至少与 XORList一样长-如果最终得到的 CurrentNode迭代器不再存在，则 XORList属性将无效。 current_node不是 current_node的所有者，因此不需要析构函数。


我认为这种方案的危险在于，确保对 XORListIterator所做的任何更改都不会完全使任何现有的 XORList失效，直至崩溃。我怀疑这也是您当前版本的问题。



我怀疑内置的 XORListIterators仍然会保持竞争力，因为它是一个编写良好，高效的结构。请记住， list通常是简单的 list.append，偶尔会有数组重新分配和复制。您总是需要创建一个新的Python对象（ Py_INCREF）以及一些相关的引用计数。

我的替代方案避免了很多引用计数（在计算时间和“您必须考虑它”时间方面），因此我希望它会更紧密。它保留了每个 Node较小的内存分配的缺点，这对于链表结构是不可避免的。



附录：解决有关“ Cython类的便利性”的评论。我认为使用Cython类和struct的两个优点是：


您可以获得与结构相当接近的东西，但不必担心C指针，并且引用计数已得到照顾。很明显，对于这个问题，您对指针做了奇怪的事情，并且必须显式地处理引用计数，因此我认为这不适用于您。
您可以从Python使用它-您不仅限于Cython。在这种情况下，我认为这完全是 append的实现细节，不应向Python用户公开。


因此，我认为专门使用Cython类的主要原因不适用于您的问题。 （当然，对于很多代码来说，优点确实适用！）

可能还值得补充的是，构造Cython类可能是其较慢的功能之一-为了支持可能的继承，构造过程是“间接的”。您已经成功创建了一个基准，该基准几乎是所有构建的基准-我想这是一个稍微偏斜的基准，实际情况可能还不错。