Clean up various Cython cimports

[jdemeyer]

This includes much simpler implementations of permutation_iterator_transposition_list() and map_to_list using Cython list comprehensions instead of C API calls.

CC: @tscrim

Component: cython

Author: Jeroen Demeyer

Branch/Commit: 2c720ee

Reviewer: Marc Mezzarobba

Issue created by migration from https://trac.sagemath.org/ticket/27237

[jdemeyer]

Branch: u/jdemeyer/ticket/27237

[jdemeyer]

New commits:

0a0f06a

Use more declarations from Cython upstream

[jdemeyer]

Commit: 0a0f06a

[sagetrac-git]

Changed commit from 0a0f06a to c149f17

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

c149f17

Use more declarations from Cython upstream

[sagetrac-git]

Changed commit from c149f17 to 169649a

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

169649a

Use more declarations from Cython upstream

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2c720ee

Use more declarations from Cython upstream

[sagetrac-git]

Changed commit from 169649a to 2c720ee

[mezzarobba]

Reviewer: Marc Mezzarobba

[tscrim]

comment:8

Did anyone check if the changes to permutation_cython.pyx resulted in a slowdown? I have a memory of having it this way because it was the fastest way to create the output list.

[jdemeyer]

comment:9

I didn't specifically check this case, but I know that Cython generates reasonably efficient code for list comprehensions. Maybe there is room for improvement, but it can't be much. In any case, it should be fixed upstream in Cython and not by writing ugly C API code. Then every list comprehension benefits from it, not just these two in permutation_cython.pyx.

[jdemeyer]

comment:10

Here are some timings on a simple example, using either a list comprehension or the C API calls:

%load_ext cython

%%cython
from cpython.object cimport PyObject

cdef extern from "Python.h":
    void Py_INCREF(PyObject *)
    PyObject * PyInt_FromLong(long ival)
    list PyList_New(Py_ssize_t size)
    void PyList_SET_ITEM(list l, Py_ssize_t, PyObject *)

def listcomp1(long n):
    cdef long i
    return [i*i for i in range(n)]

def listcomp2(long n):
    cdef long i
    cdef list T = PyList_New(n)
    for i in range(n):
        PyList_SET_ITEM(T, i, PyInt_FromLong(i*i))
    return T


%timeit -r20 listcomp1(1)
10000000 loops, best of 20: 109 ns per loop

%timeit -r20 listcomp2(1)
10000000 loops, best of 20: 100 ns per loop

%timeit -r20 listcomp1(1000)
100000 loops, best of 20: 10.7 µs per loop

%timeit -r20 listcomp2(1000)
100000 loops, best of 20: 7.7 µs per loop

%timeit -r20 listcomp1(1000000)
100 loops, best of 20: 13.3 ms per loop

%timeit -r20 listcomp2(1000000)
100 loops, best of 20: 15 ms per loop

[tscrim]

comment:11

Thanks for running the tests (I was just going to do them this morning). The benefit to doing the listcomp2 way in my mind was that it takes advantage of knowing the size of the list ahead of time. Maybe with the list comprehension, it can figure that out as well? It is interesting to me that there is a crossing point with the list sizes. For "small" lists, it seems the listcomp2 is faster (which is the case this was used for as permutation groups of large n are usually too big for testing). Anyways, fair enough point that the Cython code should be improved instead of unrolling it here. The slowdown probably will not be so impactful on any actual experiments.

[jdemeyer]

comment:12

I opened a Cython issue: cython/cython#2844

[vbraun]

Changed branch from u/jdemeyer/ticket/27237 to 2c720ee