Медленная индексация памяти Cython. - PullRequest
Новая
       29

Медленная индексация памяти Cython.

0 голосов
/ 28 января 2019

У меня очень разреженная матрица, скажем, 5000x3000, с плавающей запятой двойной точности.80% этой матрицы - нули.Мне нужно вычислить сумму каждой строки.Все это в Python / Cython.Я хотел ускорить процесс.Поскольку мне нужно вычислить эту сумму несколько миллионов раз, я подумал, что если я сделаю индексы ненулевых элементов и суммирую только их, это будет быстрее.Результат оказывается намного медленнее, чем оригинальное суммирование всех нулей методом "грубой силы".

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

#cython: language_level=2
import  numpy as np
cimport numpy as np
import time


cdef int Ncells = 5000, KCells = 400, Ne= 350
cdef double x0=0.1, x1=20., x2=1.4, x3=2.8, p=0.2

# Setting up weight
all_weights = np.zeros( (Ncells,KCells) )
all_weights[  :Ne,   :Ne ] = x0
all_weights[  :Ne, Ne:   ] = x1  
all_weights[Ne:  ,   :Ne ] = x2
all_weights[Ne:  , Ne:   ] = x3  
all_weights = all_weights * (np.random.rand(Ncells,KCells) < p)

# Making a memory view
cdef np.float64_t[:,:] my_weights = all_weights

# make an index of non zero weights
x,y    = np.where( np.array(my_weights) > 0.)  
#np_pawid  = np.column_stack( (x   ,y   ) )
np_pawid  = np.column_stack( (x   ,y   ) ).astype(int)
cdef np.int_t[:,:] pawid = np_pawid

# Making vector for column sum
summEE = np.zeros(KCells)
# Memory view
cdef np.float64_t [:] my_summEE = summEE
cdef int cc,dd,i

# brute-force summing
ntm = time.time()
for cc in range(KCells):
    my_summEE[cc] = 0
    for dd in range(Ncells):
        my_summEE[cc] += my_weights[dd,cc]
stm = time.time()
print "BRUTE-FORCE summation        : %f s"%(stm-ntm)

my_summEE[:] = 0
# summing only non zero indices
ntm = time.time()
for dd,cc in pawid:
    my_summEE[cc] += my_weights[dd,cc]
stm = time.time()
print "INDEX summation              : %f s"%(stm-ntm)

my_summEE[:] = 0
# summing only non zero indices unpacked by zip
ntm = time.time()
for dd,cc in zip(pawid[:,0],pawid[:,1]):
    my_summEE[cc] += my_weights[dd,cc]
stm = time.time()
print "ZIPPED INDEX summation       : %f s"%(stm-ntm)

my_summEE[:] = 0
# summing only non zero indices unpacked by zip
ntm = time.time()
for i in range(pawid.shape[0]):
    dd = pawid[i,0]
    cc = pawid[i,1]
    my_summEE[cc] += my_weights[dd,cc]
stm = time.time()
print "INDEXING over INDEX summation: %f s"%(stm-ntm)

# Numpy brute-froce summing
ntm = time.time()
sumwee = np.sum(all_weights,axis=0)
stm = time.time()
print "NUMPY BRUTE-FORCE summation  : %f s"%(stm-ntm)

#>
print
print "Number of brute-froce summs  :",my_weights.shape[0]*my_weights.shape[1]
print "Number of indexing    summs  :",pawid.shape[0]
#<

Я запустил его на Raspberry Pi 3, но, похоже,такие же результаты на ПК тоже.

BRUTE-FORCE summation        : 0.381014 s
INDEX summation              : 18.479018 s
ZIPPED INDEX summation       : 3.615952 s
INDEXING over INDEX summation: 0.450131 s
NUMPY BRUTE-FORCE summation  : 0.013017 s

Number of brute-froce summs  : 2000000
Number of indexing    summs  : 400820

NUMPY BRUTE-FORCE in Python  : 0.029143 s

Может кто-нибудь объяснить, почему код Cython в 3-4 раза медленнее, чем numpy?Почему индексирование, которое уменьшает количество суммирования с 2000000 до 400820, в 45 раз медленнее?Это не имеет никакого смысла.

1 Ответ

0 голосов
/ 28 января 2019

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

  2. По умолчанию Cython обрабатывает отрицательные индексы и выполняетпроверка границ.Вы можете отключить их несколькими способами .Очевидным способом является добавление @cython.wraparound(False) и @cython.boundscheck(False) в качестве декораторов к определению вашей функции.Имейте в виду, что они на самом деле делают - единственное отключение этих функций на cdef ed numy массивах или типизированных представлениях памяти и не применимо ко многим другим (так что не применяйте их везде везде как вещи типа «груз-культ»).

Хороший способ узнать, где могут возникнуть проблемы, - запустить cython -a <filename> и посмотреть аннотированный HTML-файл.Области с желтым цветом потенциально не оптимизированы, и вы можете расширить строки, чтобы увидеть лежащий в основе C-код.Очевидно, что в этом отношении беспокоятся только часто вызываемые функции и циклы - тот факт, что ваш код для установки массивов Numpy содержит вызовы Python, не вызывает проблем.

Несколько измерений:

Как вы написали 

BRUTE-FORCE summation        : 0.008625 s
INDEX summation              : 0.713661 s
ZIPPED INDEX summation       : 0.127343 s
INDEXING over INDEX summation: 0.002154 s
NUMPY BRUTE-FORCE summation  : 0.001461 s

В функции 

BRUTE-FORCE summation        : 0.007706 s
INDEX summation              : 0.681892 s
ZIPPED INDEX summation       : 0.123176 s
INDEXING over INDEX summation: 0.002069 s
NUMPY BRUTE-FORCE summation  : 0.001429 s

В функции с проверкой границ и выключением: 

BRUTE-FORCE summation        : 0.005208 s
INDEX summation              : 0.672948 s
ZIPPED INDEX summation       : 0.124641 s
INDEXING over INDEX summation: 0.002006 s
NUMPY BRUTE-FORCE summation  : 0.001467 s

Мои предложения помогают, ноне слишком резко.Мои различия не так драматичны, как вы видите (даже для вашего неизмененного кода).Numpy по-прежнему выигрывает - по предположению:

  1. Я подозреваю, что это многопоточность.
  2. прямая сумма по всему массиву будет иметь предсказуемые схемы доступа к памяти, что может сделать ее более эффективной, чемменьшее количество операций с непредсказуемым доступом к памяти
...