5.3.11 Faster Iteration through a Python List or Tuple

For example, define a function mysum in Cython as follows. Note the trick of void pointers to avoid Cython reference counting, etc:

def mysum(x):
    cdef object seq
    cdef int len,i
    cdef object item
    cdef object total
    total = 0
    cdef PyObject** X
    X = FAST_SEQ_UNSAFE(x)
    for i from 0 <=i<len:
        item = <object>X[i]
        total = total + item
    return (total)
The call to FAST_SEQ_UNSAFE gets direct very very unsafe access to the underlying array of PyObject's.

Somewhat surprisingly, this is actually faster than Python's built in sum function:

sage: time sum(range(5*10^6))
CPU times: user 1.59 s, sys: 0.08 s, total: 1.67 s
12499997500000L
sage: time mysum(range(5*10^6))
CPU times: user 1.46 s, sys: 0.03 s, total: 1.49 s
12499997500000L

In the next example, we illustrate the above idea by defining several simplified versions of the range command.

%skip
%cython

def f0(int n):
  return eval('[%s for _ in xrange(%s)]'%(n, n))

def f1(int n):
  v = []
  for i from 0 <= i < n:
      v.append(i)
  return v

def f2(int n):
  cdef int i
  v = [None] * n
  
  for i from 0 <= i < n:
      v[i] = i
  return v

def f3(int n):
  cdef int i
  w = [None] * n
  cdef void** X
  X = FAST_SEQ_UNSAFE(w)
  for i from 0 <= i < n:
      Py_DECREF(<PyObject*>X[i])
      X[i] = PyInt_FromLong(i)
  return w

def f4(int n):
  cdef int i
  v = PyList_New(n)
  for i from 0 <= i < n:
      PyList_SET_ITEM(v, i, <object>PyInt_FromLong(i))
      #WARNING -- maybe I need to incref the ref to the long?!
  return v

The fourth one is the fastest.

See About this document... for information on suggesting changes.