Performance drop using cython

Question

I wanted to make some code faster using cython's capability to use efficient indexing: http://docs.cython.org/src/tutorial/numpy.html

Basically the code represents the dependency of buttons on a game board of the game http://www.hacker.org/cross/index.php

# file test_so_cy.pyx
import time
import numpy as np
cimport numpy as np

DTYPE = np.uint8
ctypedef np.uint8_t DTYPE_t

def time_fmt(td):
    return "{:.2f} s".format(td)

def derive_equations(np.ndarray[DTYPE_t, ndim=2] field not None):
    cdef unsigned int n, m, i, j, x, y
    t1 = time.time()
    n, m = len(field), len(field[0])
    # generate equations for dimensions n and m
    eqs = []
    block = 2  # as soon as a 2 is hit there isnt any influence
    for i in xrange(n):
        for j in xrange(m):
            eq = 0L
            if field[i][j] == block:
                eqs.append([i*m+j ,field[i][j], eq])
                continue

            # rows upwards
            for x in xrange(i-1, -1, -1):
                if field[x][j] == block: break
                eq ^= 1L << (x*m+j)

            # rows downwards
            for x in xrange(i, n):
                if field[x][j] == block: break
                eq ^= 1L << (x*m+j)

            # cols left
            for y in xrange(j-1, -1, -1):
                if field[i][y] == block: break
                eq ^= 1L << (i*m+y)

            # cols right
            # j+1 to avoid resetting the influence of itself
            for y in xrange(j+1, m):
                if field[i][y] == block: break
                eq ^= 1L << (i*m+y)

            eqs.append([i*m+j, field[i][j], eq])

    t2 = time.time()
    print 'preprocess time:', time_fmt(t2 - t1)
    return n, m, eqs


def main():
    field = np.array(
[[0,1,0,0,0,0,0,0,0,0,0,1,1,1,0,2,1,0,0,2,1,0,1,1,0,0,0,0,0],
 [0,1,0,0,1,1,0,1,0,0,0,1,1,0,0,1,0,1,0,0,1,0,1,1,1,0,1,1,1],
 [1,1,0,1,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0,1,0,1,1,0,0,1,0,0,2],
 [0,0,0,0,1,0,1,1,0,1,1,1,0,1,0,1,1,0,0,0,1,1,0,0,2,1,1,0,1],
 [0,1,0,1,1,1,1,1,2,1,1,0,1,0,0,0,0,0,0,1,0,0,1,0,2,0,1,0,1],
 [0,1,1,0,0,1,1,0,1,0,0,1,1,1,0,1,1,1,0,0,1,1,1,0,1,0,1,1,1],
 [0,0,0,1,0,1,1,0,1,0,0,1,1,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,1],
 [1,0,1,0,1,1,0,0,0,0,0,1,0,0,2,0,1,1,0,0,0,0,1,0,0,2,1,0,0],
 [1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,1,0,1,1,0,1,0,1,0,1,0,1,1,1],
 [0,0,1,0,0,1,1,0,1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,1,2],
 [1,0,1,1,0,0,1,0,1,1,1,0,1,2,1,1,1,2,1,0,1,1,1,0,0,0,0,0,0],
 [0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1],
 [1,1,0,0,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,0,0,0,0],
 [1,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,0,0,1,1,1,1,1,0,1,0,1,0,1],
 [1,0,0,0,1,1,0,0,2,0,1,1,2,0,0,1,0,1,0,1,0,2,1,1,1,1,0,0,2],
 [1,0,1,1,1,1,1,0,0,1,1,0,1,1,0,0,1,0,0,0,2,1,0,1,0,1,0,1,1],
 [0,0,1,1,1,0,0,0,0,0,2,1,0,1,0,1,0,1,1,1,1,0,0,1,1,1,1,0,1],
 [0,1,0,1,2,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,1,0],
 [0,1,0,0,2,0,0,0,1,0,1,0,0,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1],
 [1,0,0,1,0,0,1,0,1,0,0,2,0,1,1,1,1,1,0,0,1,0,1,0,1,1,0,1,1],
 [0,0,1,0,1,1,0,0,1,0,0,0,1,1,1,0,0,1,0,0,1,0,1,2,0,1,1,0,2],
 [0,1,1,0,1,0,1,1,0,0,1,0,0,0,1,1,0,1,0,1,1,1,1,1,2,0,1,2,0],
 [0,0,0,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1,1,1,2,0,0,1,0,0,1,1,0],
 [0,0,1,1,0,1,1,0,0,1,1,1,1,0,0,1,0,0,1,1,1,0,0,0,1,1,1,0,1],
 [0,2,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,1,0,1,0,0,0,1,1],
 [0,2,1,1,1,1,1,1,1,1,0,1,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,1,1],
 [0,1,1,1,0,1,0,0,0,1,0,2,0,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,0],
 [0,1,1,1,1,1,0,1,0,1,0,1,0,0,0,0,0,1,0,0,0,0,1,1,0,0,0,0,0],
 [1,0,0,0,0,1,0,1,0,1,0,1,0,0,1,0,0,1,0,0,1,0,1,0,0,1,2,1,1]], dtype=DTYPE)
    derive_equations(field)

if __name__ == '__main__':
    main()

# file setup_so.py
from distutils.core import setup
from Cython.Build import cythonize
import numpy

setup(
    name = "test_so",
    ext_modules = cythonize('test_so_cy.pyx'),
    include_dirs=[numpy.get_include()]
)

# usage: python setup_so.py build_ext --inplace
# import test_so_cy
# test_so_cy.main()

The problem is that the cython code runs ~3 times slower than the pure python version. (I am using the time module to measure execution time because for bigger matrices its ok).

cython -a tells me that the

if field[x][j] == block: break

lines are still using much python. So it seems that fast indexing still cannot be used. Any ideas what i am doing wrong?

Answer 1

Original speed: 0.14s

14X speedup (0.01s): The field[i][j] will evaluate the field[i] first and then try to evaluate the resulting python object. use the field[i,j] notation for a HUGE boost in speed

5X speedup (0.0018s): type the eq variable cdef long eq

12X s5eedup (0.00012s) : replace the list with a stack made of an np array:

cdef np.ndarray[long, ndim=2] eqs=np.zeros((n*m,3),np.long)
cdef int curr_eqn=0

#append to list code
    if field[i,j] == block:
        eqs[curr_eqn,0]=i*m+j
        eqs[curr_eqn,1]=field[i,j]
        eqs[curr_eqn,2]=eq
        curr_eqn+=1
        continue

total speedup: 1100x