Opened 3 years ago

Closed 3 years ago

#27237 closed enhancement (fixed)

Clean up various Cython cimports

Reported by: jdemeyer Owned by:
Priority: trivial Milestone: sage-8.7
Component: cython Keywords:
Cc: tscrim Merged in:
Authors: Jeroen Demeyer Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: 2c720ee (Commits, GitHub, GitLab) Commit: 2c720ee5d620be70c5ec20fa296355469d0a94fe
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

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

Change History (13)

comment:1 Changed 3 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/27237

comment:2 Changed 3 years ago by jdemeyer

  • Commit set to 0a0f06a6030c47b7dd5b123bc07e7622479974a5
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

0a0f06aUse more declarations from Cython upstream

comment:3 Changed 3 years ago by jdemeyer

  • Cc tscrim added
  • Description modified (diff)

comment:4 Changed 3 years ago by git

  • Commit changed from 0a0f06a6030c47b7dd5b123bc07e7622479974a5 to c149f177379d254b5479a186a7e61322a661490a

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

c149f17Use more declarations from Cython upstream

comment:5 Changed 3 years ago by git

  • Commit changed from c149f177379d254b5479a186a7e61322a661490a to 169649aaae478dafe45359ded859ceeb0e56ae3f

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

169649aUse more declarations from Cython upstream

comment:6 Changed 3 years ago by git

  • Commit changed from 169649aaae478dafe45359ded859ceeb0e56ae3f to 2c720ee5d620be70c5ec20fa296355469d0a94fe

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

2c720eeUse more declarations from Cython upstream

comment:7 Changed 3 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to positive_review

comment:8 Changed 3 years ago by tscrim

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.

comment:9 Changed 3 years ago by jdemeyer

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.

comment:10 Changed 3 years ago by jdemeyer

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

comment:11 Changed 3 years ago by tscrim

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.

comment:12 Changed 3 years ago by jdemeyer

comment:13 Changed 3 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/27237 to 2c720ee5d620be70c5ec20fa296355469d0a94fe
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.