I just realized the Python does not provide a fast way of popping an 
item from a list, just append. I.e. there is a PyList_Append, but no 
PyList_Pop. And in Python's code for _listobject.c, the function listpop 
is declared static. When using a list as a stack (a common case for 
Python lists), a fast pop is just as important as a fast append.

Since the function listpop is static, the fastest way to pop a list is 
to grab the method named "pop" from the PyTypeObject. This might not be 
obvious to everyone, so I think it is an optimization that Cython should do.

Sturla Molden

cdef extern from "Python.h":

    ctypedef object (*PyCFunction)(object self, object args)

    ctypedef struct PyMethodDef:
        char *ml_name
        PyCFunction ml_meth

    ctypedef struct PyTypeObject:
        PyMethodDef *tp_methods

    PyTypeObject PyList_Type

cdef PyCFunction __listpop = NULL

cpdef listpop(list self, Py_ssize_t n=-1):

    global __listpop

    cdef PyMethodDef *ptr
    cdef int ok = 0

    if not __listpop:
        ptr = PyList_Type.tp_methods;
        while ptr:
            if str(ptr[0].ml_name) == "pop":
               __listpop = ptr.ml_meth
               ok = 1
            ptr += 1
        if not ok:
            raise ValueError, \
              'Could not find method "pop" in list type object'
    return __listpop(self, (int(n),))

Cython-dev mailing list

Reply via email to