Cython实现不比纯python快

对于一个练习，我写了一个异或双向链表

%%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

当我分析异形列表的循环时，我得到：

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% 以内。

分析中的三个罪魁祸首看起来是 Node 的__init__(这在这里是不可避免的)，并且__get__和__set__prev_xor_next属性。我的观点是，你不希望prev_xor_next属性(或者如果你这样做，它应该是只读的)，因为它使得应该在Python中访问的Cython内部。

无论您是否删除该属性，您都在这里使用 Cython，因此您可以直接写入底层 C 属性_prev_xor_next。您可能需要在append开始时(也许在其他函数中)设置cdef Node cur_last以确保 Cython 知道cur_last的类型 - 我认为它应该能够解决它，但如果您在运行时得到AttributeErrors，那么这就是您需要做的。

此更改使我的速度提高了 30%(即它仍然比常规列表慢，但这是一个明显的改进)。

我将概述一个更剧烈的变化，我可能应该就你关于这个问题的第一个问题提出建议。这确实是一个模糊的大纲，因此没有努力让它工作......

Node完全是XORList类的内部：它不应该从 Python 中使用，并且XORList中所有Nodes的生存期都直接与列表相关联。因此，它们应该在销毁其拥有XORList时销毁(或者如果列表缩小等)，因此不需要进行引用计数。因此Node应该是 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)

XORList需要一个__dealloc__函数，该函数循环遍历每个Node上的列表调用destroy_node(无论如何，在您的版本中它也需要一个__dealloc__函数！
CurrentNode需要保持 Cython 类，因为这是您的"迭代器"接口。它显然不能再继承Node.我会把它改成：
```
cdef class XORListIterator:
cdef Node* current_node
cdef XORList our_list
```
属性our_list的要点是确保XORList至少与CurrentNode一样长 - 如果最终得到不再存在的XORList的迭代器，则current_node属性将无效。current_node不属于XORListIterator，因此不需要析构函数。

我认为这个方案的危险在于确保如果对XORList的任何更改不会完全使任何现有XORListIterators无效，以至于您崩溃。我怀疑这也是您当前版本的问题。

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

我的替代方案避免了大量的引用计数(无论是在计算时间和"你必须考虑它"时间方面)，所以我希望它更接近。它保留了每append内存分配小的缺点，这对于链表结构来说是不可避免的。

附录：解决关于"Cython类的便利性"的评论。在我看来，使用 Cython 类与结构体相比的两个优点是：

你会得到一些相当接近结构的东西，但不必担心 C 指针，并且引用计数得到了处理。很明显，对于这个问题，你正在对指针做奇怪的事情，并且必须明确处理引用计数，所以我认为这不适用于你。
你可以从Python使用它 - 你不仅限于Cython。在这种情况下，我认为这完全是XORList的实现细节，不应该向 Python 用户公开。

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

可能还值得补充的是，构造 Cython 类可能是它们较慢的功能之一 - 为了支持可能的继承，构造过程非常"间接"。您已经设法创建了一个几乎都是构建的基准 - 我猜这是一个略微偏斜的基准，实际情况可能并不那么糟糕。

相关内容

最新更新

热门标签：