Cython 的实现并不比纯 python 快

Question

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

%%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 属性（或者如果你这样做应该是只读的）因为它使得应该是 Cython 内部的东西可以在 Python.

不管你是否删除属性，你在这里都是在Cython中工作，所以你可以直接写入底层C属性_prev_xor_next。您可能需要在 append 的开头设置 cdef Node cur_last （可能在其他函数中）以确保 Cython 知道 cur_last 的类型 - 我认为它应该能够解决但是如果你在运行时得到 AttributeErrors 那么这就是你需要做的。

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

我将概述一个更彻底的改变，我可能应该在你关于这个问题的第一个问题上提出建议。这确实是一个模糊的大纲，所以没有努力让它发挥作用...

Node 完全在您的 XORList 内部 class：它不应从 Python 开始使用，并且所有 [= XORList 中的 24=] 直接绑定到列表。因此，它们应该在销毁它们拥有的 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__ 函数循环遍历列表调用 destroy_node 每个 Node （它需要一个 __dealloc__无论如何在你的版本中也能正常工作！）
CurrentNode 需要保留 Cython class，因为这是您的 "iterator" 界面。它显然不能再继承自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）以及一些相关的引用计数。

我的替代方案避免了大量引用计数（在计算时间和 "you having to think about it" 时间方面），所以我希望它更接近。它保留了每个 append 的小内存分配的缺点，这对于链表结构来说是不可避免的。

附录：解决关于 "the convenience of a Cython class" 的评论。在我看来，使用 Cython class 与结构的两个优点是：

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

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

可能还值得补充的是，构建 Cython classes 可能是它们较慢的功能之一 - 为了支持可能的继承，构建过程非常 "indirect"。您已经成功地创建了一个几乎所有构建的基准 - 我猜这是一个略有偏差的基准，实际情况可能并没有那么糟糕。

Cython 的实现并不比纯 python 快

Cython implementation no faster than pure python

python

pointers

linked-list

cython

xor