Постфиксный калькулятор в Cython

,

Привет.

Я пытаюсь разработать постфиксный калькулятор на Cython, переведенный с рабочей версии Numpy. Это моя первая попытка. Функция калькулятора получает выражение постфикса в списке и матрицу образцов. Затем он должен вернуть вычисленный массив.

Пример ввода:

postfix = ['X0', 'X1', 'add']
samples = [[0, 1], 
           [2, 3], 
           [4, 5]]
result = [1, 5, 9]

example_cython.pyx

#cython: boundscheck=False, wraparound=False, nonecheck=False

import numpy
from libc.math cimport sin as c_sin

cdef inline calculate(list lst, double [:,:] samples):
    cdef int N = samples.shape[0]
    cdef int i, j
    cdef list stack = []
    cdef double[:] Y = numpy.zeros(N)

    for p in lst:
        if p == 'add':
            b = stack.pop()
            a = stack.pop()
            for i in range(N):
                Y[i] = a[i] + b[i]
            stack.append(Y)
        elif p == 'sub':
            b = stack.pop()
            a = stack.pop()
            for i in range(N):
                Y[i] = a[i] - b[i]
            stack.append(Y)
        elif p == 'mul':
            b = stack.pop()
            a = stack.pop()
            for i in range(N):
                Y[i] = a[i] * b[i]
            stack.append(Y)
        elif p == 'div':
            b = stack.pop()
            a = stack.pop()
            for i in range(N):
                if abs(b[i]) < 1e-4: b[i]=1e-4
                Y[i] = a[i] / b[i]
            stack.append(Y)
        elif p == 'sin':
            a = stack.pop()
            for i in range(N):
                Y[i] = c_sin(a[i])
            stack.append(Y)
        else:
            if p[0] == 'X':
                j = int(p[1:])
                stack.append (samples[:, j])
            else:
                stack.append(float(p))
    return stack.pop ()


# Generate and evaluate expressions
cpdef test3(double [:,:] samples, object _opchars, object _inputs, int nExpr):
    for i in range(nExpr):
        size = 2
        postfix = list(numpy.concatenate((numpy.random.choice(_inputs, 5*size),
                                        numpy.random.choice(_inputs + _opchars, size),
                                        numpy.random.choice(_opchars, size)), 0))
        #print postfix

        res = calculate(postfix, samples)

main.py

import random
import time
import numpy
from example_cython import test3

# Random dataset
n = 1030
nDim=10
samples = numpy.random.uniform(size=(n, nDim))

_inputs = ['X'+str(i) for i in range(nDim)]
_ops_1 = ['sin']
_ops_2 = ['add', 'sub', 'mul', 'div']
_opchars = _ops_1 + _ops_2
nExpr = 1000
nTrials = 3

tic = time.time ()
for i in range(nTrials): test3(samples, _opchars, _inputs, nExpr)
print ("TEST 1: It took an average of {} seconds to evaluate {} expressions on a dataset of {} rows and {} columns.".format(str((time.time () - tic)/nTrials), str(nExpr), str(n), str(nDim)))

setup.py

from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext

ext_modules=[ Extension("example_cython",
              ["example_cython.pyx"],
              libraries=["m"],
              extra_compile_args = ["-Ofast", "-ffast-math"])]

setup(
  name = "example_cython",
  cmdclass = {"build_ext": build_ext},
  ext_modules = ext_modules)

Конфигурация:

Python 3.6.2 |Anaconda, Inc.| (default, Sep 21 2017, 18:29:43)
[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)] on darwin

>>> numpy.__version__
'1.13.1'
>>> cython.__version__
'0.26.1'

Компиляция и запуск:

running build_ext
skipping 'example_cython.c' Cython extension (up-to-date)
building 'example_cython' extension
/usr/bin/clang -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -fwrapv -O2 -Wall -Wstrict-prototypes -march=core2 -mtune=haswell -mssse3 -ftree-vectorize -fPIC -fPIE -fstack-protector-strong -O2 -pipe -march=core2 -mtune=haswell -mssse3 -ftree-vectorize -fPIC -fPIE -fstack-protector-strong -O2 -pipe -I/Users/vmelo/anaconda3/include/python3.6m -c example_cython.c -o build/temp.macosx-10.9-x86_64-3.6/example_cython.o -Ofast -ffast-math
example_cython.c:2506:15: warning: code will never be executed [-Wunreachable-code]
    if (0 && (__pyx_tmp_idx < 0 || __pyx_tmp_idx >= __pyx_tmp_shape)) {
              ^~~~~~~~~~~~~
example_cython.c:2506:9: note: silence by adding parentheses to mark code as explicitly dead
    if (0 && (__pyx_tmp_idx < 0 || __pyx_tmp_idx >= __pyx_tmp_shape)) {
        ^
        /* DISABLES CODE */ ( )
example_cython.c:2505:9: warning: code will never be executed [-Wunreachable-code]
        __pyx_tmp_idx += __pyx_tmp_shape;
        ^~~~~~~~~~~~~
example_cython.c:2504:9: note: silence by adding parentheses to mark code as explicitly dead
    if (0 && (__pyx_tmp_idx < 0))
        ^
        /* DISABLES CODE */ ( )
2 warnings generated.
/usr/bin/clang -bundle -undefined dynamic_lookup -Wl,-pie -Wl,-headerpad_max_install_names -Wl,-rpath,/Users/vmelo/anaconda3/lib -L/Users/vmelo/anaconda3/lib -Wl,-pie -Wl,-headerpad_max_install_names -Wl,-rpath,/Users/vmelo/anaconda3/lib -L/Users/vmelo/anaconda3/lib -arch x86_64 build/temp.macosx-10.9-x86_64-3.6/example_cython.o -L/Users/vmelo/anaconda3/lib -lm -o /Users/vmelo/Dropbox/SRC/python/random_equation/cython_v2/example_cython.cpython-36m-darwin.so
ld: warning: -pie being ignored. It is only used when linking a main executable

TEST 1: It took an average of 1.2609198093414307 seconds to evaluate 1000 expressions on a dataset of 1030 rows and 10 columns.

На моем i5 1.4Ghz требуется около 1,25 секунды. Тем не менее, аналогичный код C занимает 0,13 секунды.

Приведенный выше код оценивает 1000 выражений, но я стремлюсь к 1 000 000. Таким образом, я должен ускорить этот код Cython с большим отрывом.

Как я писал в начале, версия Numpy работает правильно. Может быть, в этой версии Cython я не должен использовать список в качестве стека? Я все еще не проверяю, правильны ли результаты, генерируемые этим кодом Cython, поскольку я сосредоточен на улучшении его скорости.

Какие-либо предложения?

Благодарю.

Источник

1 ответ

В настоящее время оптимизирована только операция индексации samples[:, j], (Почти) все остальное нетипизировано, и поэтому Cython не может оптимизировать это много.

Я не хочу полностью переписывать вашу (довольно большую) программу, но вот несколько простых идей о том, как ее улучшить.

  1. Исправьте основную логическую ошибку - вам нужна строка Y = numpy.zeros(N) внутри вашей петли. stack.append(Y) не делает копию Y, так что каждый раз, когда вы модифицируете Y Вы также изменяете все другие версии, которые вы положили в стек.

  2. Установить тип для a а также b:

    cdef double[:] a, b # at the start of the program

    Это значительно ускорит индексацию

    Y[i] = a[i] * b[i]

    Тем не менее, это приведет к линии, как a = stack.pop() быть немного медленнее, так как нужно проверить, что результат может быть использован как просмотр памяти. Вам также нужно будет изменить строку

    stack.append(float(p))

    чтобы убедиться, что вы положили что-то пригодное для использования с памятью в стек:

    stack.append(float(p)*np.ones(N))

  3. Измените стек на 2D-просмотр памяти. Я бы посоветовал вам перераспределить его и просто вести подсчет number_on_stack и затем перераспределить стек при необходимости. Затем вы можете изменить:

    stack.append(samples[:, j])

    чтобы:

    if stack.shape[1] < number_on_stack+1:
    # resize numpy array
    arr = stack.base
    arr.resize(... larger shape ..., refcheck=False)
    stack = arr # re-link stack to resized array (to ensure size is suitably updated)
stack[:,number_on_stack+1] = samples[:,j]
number_on_stack += 1

    а также

    a = stack.pop()

    в

    a = stack[:,number_on_stack]
number_on_stack -= 1

    Другие изменения следуют аналогичной схеме. Этот вариант наиболее эффективен, но, вероятно, даст наилучшие результаты.

С помощью cython -a генерирование цветного HTML дает разумное представление о том, какие биты хорошо оптимизированы (желтый код обычно хуже)

Источник
Другие вопросы по тегам