Оптимизация простых циклов, связанных с процессором, с использованием Cython и замена списка

Question

Я пытаюсь оценить некоторые подходы, и я нахожусь на камне преткновения с производительностью.

Почему мой код cython настолько медленный? Мое ожидание в том, что код будет работать довольно быстро (возможно, nano секунд для цикла 2d с 256 ** 2 записями) в отличие от миллисекунд.

Вот мои результаты испытаний:

$ python setup.py build_ext --inplace; python test.py 
running build_ext 
     counter: 0.00236220359802 sec 
     pycounter: 0.00323309898376 sec 
     percentage: 73.1 % 

Мой исходный код выглядит примерно так:

#!/usr/bin/env python 
# encoding: utf-8 
# filename: loop_testing.py 

def generate_coords(dim, length): 
    """Generates a list of coordinates from dimensions and size 
    provided. 

    Parameters: 
     dim -- dimension 
     length -- size of each dimension 

    Returns: 
     A list of coordinates based on dim and length 
    """ 
    values = [] 
    if dim == 2: 
     for x in xrange(length): 
      for y in xrange(length): 
       values.append((x, y)) 

    if dim == 3: 
     for x in xrange(length): 
      for y in xrange(length): 
       for z in xrange(length): 
        values.append((x, y, z)) 

    return values 

Это работает для того, что мне нужно, но медленно. Для данного dim, length = (2, 256), я вижу время на iPython около 2,3 мс.

В попытке ускорить это, я разработал эквивалент cython (я думаю, что это эквивалент).

#!/usr/bin/env python 
# encoding: utf-8 
# filename: loop_testing.pyx 
# cython: boundscheck=False 
# cython: wraparound=False 

cimport cython 
from cython.parallel cimport prange 

import numpy as np 
cimport numpy as np 


ctypedef int DTYPE 

# 2D point updater 
cpdef inline void _counter_2d(DTYPE[:, :] narr, int val) nogil: 
    cdef: 
     DTYPE count = 0 
     DTYPE index = 0 
     DTYPE x, y 

    for x in range(val): 
     for y in range(val): 
      narr[index][0] = x 
      narr[index][1] = y 
      index += 1 

cpdef DTYPE[:, :] counter(dim=2, val=256): 
    narr = np.zeros((val**dim, dim), dtype=np.dtype('i4')) 
    _counter_2d(narr, val) 
    return narr 

def pycounter(dim=2, val=256): 
    vals = [] 
    for x in xrange(val): 
     for y in xrange(val): 
      vals.append((x, y)) 
    return vals 

И призывание времени:

#!/usr/bin/env python 
# filename: test.py 
""" 
Usage: 
    test.py [options] 
    test.py [options] <val> 
    test.py [options] <dim> <val> 

Options: 
    -h --help  This Message 
    -n    Number of loops [default: 10] 
""" 

if __name__ == "__main__": 
    from docopt import docopt 
    from timeit import Timer 

    args = docopt(__doc__) 
    dim = args.get("<dim>") or 2 
    val = args.get("<val>") or 256 
    n = args.get("-n") or 10 
    dim = int(dim) 
    val = int(val) 
    n = int(n) 

    tests = ['counter', 'pycounter'] 
    timing = {} 
    for test in tests: 
     code = "{}(dim=dim, val=val)".format(test) 
     variables = "dim, val = ({}, {})".format(dim, val) 
     setup = "from loop_testing import {}; {}".format(test, variables) 
     t = Timer(code, setup=setup) 
     timing[test] = t.timeit(n)/n 

    for test, val in timing.iteritems(): 
     print "{:>20}: {} sec".format(test, val) 
    print "{:>20}: {:>.3} %".format("percentage", timing['counter']/timing['pycounter'] * 100) 

И для справки, setup.py строить код Cython:

from distutils.core import setup 
from Cython.Build import cythonize 
import numpy 

include_path = [numpy.get_include()] 

setup(
    name="looping", 
    ext_modules=cythonize('loop_testing.pyx'), # accepts a glob pattern 
    include_dirs=include_path, 
) 

EDIT: Ссылка работать версия: https://github.com/brianbruggeman/cython_experimentation

Answer 1

Этот код Cython был медленным из-за narr[index][0] = x работу, которая в значительной мере опирается на Python C-API. Вместо этого используется narr[index, 0] = x, переводится на чистый C и решает эту проблему.

Как указано в @perimosocordiae, использование cythonize с аннотациями - это, безусловно, способ отладки таких проблем.

В некоторых случаях это может быть также стоят явного указания флагов компиляции в setup.py для НКИ,

setup(
    [...] 
    extra_compile_args=['-O2', '-march=native'], 
    extra_link_args=['-O2', '-march=native']) 

Это не должно быть необходимым, если предположить, разумные компиляции по умолчанию флагов. Однако, например, в моей Linux-системе по умолчанию, по-видимому, нет никакой оптимизации и добавления вышеуказанных флагов, что приводит к значительному повышению производительности.

Answer 2

Похоже, ваш код Cython делает некоторые странные вещи с массивами numpy и на самом деле не использует компиляцию C. Чтобы проверить сгенерированный код, запустите

cython -a loop_testing.pyx 

Что произойдет, если вы избегаете Numpy частей и сделать простой Cython перевод функции Python?

EDIT: Похоже, вы можете избежать Cython полностью для довольно приличного ускорения. (~ 30x на моей машине)

def npcounter(dim=2, val=256): 
    return np.indices((val,)*dim).reshape((dim,-1)).T