Реализация Cython не быстрее, чем чистый Python - PullRequest
Новая
       24

Реализация Cython не быстрее, чем чистый Python

1 голос
/ 30 октября 2019

Для упражнения я написал двусвязный список 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)

, используя приведенный выше встроенный список, и я последовательно получаю в 10 раз худшую производительность в связанном списке Cython. 

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, кажется, что большую часть времени тратится в специальных методах,

Это подводит меня к моим вопросам:

  1. как я могу ускорить это
  2. Я думал, что типы расширений в Cython реализуются снизу через структуры, так что вызываетих инициализация заняла так много времени

Я также попробовал другую пользовательскую реализацию ординарного двусвязного списка в чистом Python, и его временные характеристики и список XorList схожи с разницей в 10% на моей машине. .

1 Ответ

1 голос
/ 30 октября 2019

Три виновника из вашего профилирования выглядят как Node's __init__ (что здесь неизбежно) и __get__ и __set__ для свойства prev_xor_next. На мой взгляд, вам не нужно свойство prev_xor_next (или если вы это делаете, оно должно быть доступно только для чтения), поскольку оно делает доступным внутреннее содержимое Cython в Python.

Независимо от того, удаляется ли свойствоили нет, вы здесь работаете в Cython, поэтому вы можете писать напрямую в базовый атрибут C _prev_xor_next. Возможно, вам придется установить cdef Node cur_last в начале append (и, возможно, в других функциях), чтобы Cython знал тип cur_last - я думаю, что он сможет его решить, но если вы получите AttributeErrors во время выполнения, это то, что вам нужно сделать.

Это изменение дает мне увеличение скорости на 30% (т.е. оно все еще медленнее, чем обычный список, но это заметное улучшение).

Я опишу более радикальные изменения, которые я, возможно, следовало бы предложить в вашем первом вопросе об этой проблеме. Это действительно расплывчатая схема, поэтому не было предпринято никаких усилий, чтобы заставить его работать ...

  • Node полностью соответствует вашему XORList классу: его не следует использоватьот Python и время жизни всех Nodes в XORList напрямую связано со списком. Поэтому они должны быть уничтожены при уничтожении принадлежащего им 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, поскольку это ваш интерфейс "итератора". Очевидно, он больше не может наследовать от Node. Я бы изменил его на: 

    cdef class XORListIterator:
    cdef Node* current_node
    cdef XORList our_list

    смысл атрибута our_list состоит в том, чтобы гарантировать, что XORList сохраняется как минимум столько же, сколько CurrentNode - если вы в конечном итоге ситератор для XORList, который больше не существует, и атрибут current_node будет недействительным. current_node не принадлежит XORListIterator, поэтому нет необходимости в деструкторе.

Я думаю, опасность этой схемы заключается в том, что если какие-либо изменения в XORList не будутt полностью лишить законной силы любые существующие XORListIterators до точки, где вы получаете сбой. Я подозреваю, что это также будет проблемой с вашей текущей версией.

Я подозреваю, что встроенный list все равно останется конкурентоспособным, так как это хорошо написанная, эффективная структура. Помните, что list.append обычно является простым Py_INCREF, со случайным перераспределением и копированием массива. Ваша всегда включает создание нового объекта Python (Node), а также некоторый связанный подсчет ссылок.

Моя альтернативная схема позволяет избежать большого количества подсчетов ссылок (как с точки зрения вычислительного времени, так и «вам нужноподумайте об этом "время", так что я ожидаю, что это будет гораздо ближе. Это сохраняет недостаток небольшого выделения памяти для каждого append, что неизбежно для структуры связанного списка.

Добавление : для комментария о "удобствекласс Cython ". На мой взгляд, два преимущества использования класса Cython перед структурой:

  1. Вы получаете что-то довольно близкое к структуре, но вам не нужно беспокоиться о C-указателях, и подсчет ссылок взятзабота о. Совершенно очевидно, что для этой проблемы вы делаете странные вещи с указателями и вынуждены обрабатывать подсчет ссылок явно, поэтому я не думаю, что это относится к вам.
  2. Вы можете использовать это из Python - вы нене ограничивается только Cython. В этом случае я думаю, что это полностью детали реализации XORList, которые не должны быть представлены пользователям Python.

Поэтому я думаю, что основные причины использовать классы Cython специально don 't применимо к вашей проблеме. (Конечно, к большому количеству кода эти преимущества применимы!)

Вероятно, также стоит добавить, что построение классов Cython, вероятно, является одной из их более медленных функций - для поддержки возможного наследования процесс построения является довольно "косвенным". Вам удалось создать бенчмарк, который оказывается практически полностью построенным - я думаю, это слегка искаженный бенчмарк, и реальный случай может быть не таким уж плохим.

...