Производительность вложенной петли в numba

Question

По соображениям производительности, я начал использовать Numba помимо NumPy. Мой алгоритм Numba работает, но я чувствую, что он должен быть быстрее. Есть один момент, который замедляет его. Вот фрагмент кода:

@nb.njit 
def rfunc1(ws, a, l): 
    gn = a**l 
    for x1 in range(gn): 
     for x2 in range(gn): 
      for x3 in range(gn): 
       y = 0.0 
       for i in range(1, l): 
        if numpy.all(ws[x1][0:i] == ws[x2][0:i]) and 
        numpy.all(ws[x1][i:l] == ws[x3][i:l]): 
         y += 1 
        if numpy.all(ws[x1][0:i] == ws[x2][0:i]) and 
        numpy.all(ws[x1][i:l] == ws[x3][i:l]): 
         y += 1 

На мой взгляд, команда if замедляет его вниз. Есть ли способ лучше? (То, что я пытаюсь достичь здесь связан с предыдущей публикуемой проблемой: Count possibilites for single crossovers) ws является массивом NumPy размера (gn, l) содержащего 0 «S и 1» s

Answer 1

Учитывая логику желания гарантировать, что все элементы равны, то может воспользоваться тем фактом, что, если они не равны, вы можете провести короткое замыкание (т.е. прекратить сравнение) вычисления. Я слегка модифицирован оригинальная функция так, что (1) не повторять то же сравнения в два раза, и (2) сумма у за все вложенные циклы, так что было возвращение, что можно было бы сравнить:

@nb.njit 
def rfunc1(ws, a, l): 
    gn = a**l 
    ysum = 0 
    for x1 in range(gn): 
     for x2 in range(gn): 
      for x3 in range(gn): 
       y = 0.0 
       for i in range(1, l): 
        if np.all(ws[x1][0:i] == ws[x2][0:i]) and np.all(ws[x1][i:l] == ws[x3][i:l]): 
         y += 1 
         ysum += 1 

    return ysum 


@nb.njit 
def rfunc2(ws, a, l): 
    gn = a**l 
    ysum = 0 
    for x1 in range(gn): 
     for x2 in range(gn): 
      for x3 in range(gn): 
       y = 0.0 
       for i in range(1, l): 

        incr_y = True 
        for j in range(i): 
         if ws[x1,j] != ws[x2,j]: 
          incr_y = False 
          break 

        if incr_y is True: 
         for j in range(i,l): 
          if ws[x1,j] != ws[x3,j]: 
           incr_y = False 
           break 
        if incr_y is True: 
         y += 1 
         ysum += 1 
    return ysum 

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

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

l = 7 
a = 2 
gn = a**l 
ws = np.random.randint(0,2,size=(gn,l)) 
In [23]: 

%timeit rfunc1(ws, a , l) 
1 loop, best of 3: 2.11 s per loop 


%timeit rfunc2(ws, a , l) 
1 loop, best of 3: 39.9 ms per loop 

In [27]: rfunc1(ws, a , l) 
Out[27]: 131919 

In [30]: rfunc2(ws, a , l) 
Out[30]: 131919 

Это дает вам 50x скорость вверх.

Answer 2

Вместо того, чтобы просто «иметь чувство», где узким местом является, почему не профиль ваш код и найти именно где?

Первой целью профилирования является проверка репрезентативной системы для определения того, что происходит медленно (или с использованием слишком большого количества ОЗУ, или из-за слишком большого объема ввода-вывода или сетевого ввода-вывода).

Профилирование обычно добавляет накладные расходы (может быть характерно замедление от 10x до 100x), и вы по-прежнему хотите, чтобы ваш код использовался как можно ближе к реальной ситуации. Извлеките тестовый кейс и изолируйте часть системы, которую необходимо протестировать. Предпочтительно, это будет написано уже в своем собственном наборе модулей.

Основные методы включают волшебство %timeit в IPython, time.time(), и timing decorator (см. Пример ниже). Вы можете использовать эти методы для понимания поведения операторов и функций.

Тогда у вас есть cProfile, который даст вам представление о проблеме на высоком уровне, чтобы вы могли обратить ваше внимание на важные функции.

Далее, посмотрите на line_profiler,, который будет профилировать выбранные вами функции по очереди. Результат будет включать в себя подсчет количества раз, когда вызывается каждая строка, и процент времени, затраченного на каждую строку. Это именно то, что вам нужно, чтобы понять, что работает медленно и почему.

perf stat помогает понять количество инструкций, которые в конечном итоге выполняются на процессоре, и насколько эффективно используются кеши процессора. Это позволяет осуществлять расширенную настройку матричных операций.

heapy может отслеживать все объекты внутри памяти Python. Это отлично подходит для поиска странных утечек памяти.Если вы работаете с многолетними системами, вам будет интересен , тогда dowser вас заинтересовал: он позволяет вам заглядывать живые объекты в длительный процесс через интерфейс веб-браузера.

Чтобы помочь вам понять, почему ваше использование ОЗУ очень велико, посмотрите memory_profiler. Это особенно полезно для отслеживания использования ОЗУ с течением времени на маркированной диаграмме, поэтому вы можете объяснить коллегам (или вам самим), почему некоторые функции используют больше ОЗУ, чем ожидается.

Пример: Определение декоратора для автоматизации измерений

from functools import wraps 

def timefn(fn): 
    @wraps(fn) 
    def measure_time(*args, **kwargs): 
     t1 = time.time() 
     result = fn(*args, **kwargs) 
     t2 = time.time() 
     print ("@timefn:" + fn.func_name + " took " + str(t2 - t1) + " seconds") 
     return result 
    return measure_time 

@timefn 
def your_func(var1, var2): 
    ... 

Для получения дополнительной информации, я предлагаю читать High performance Python (Micha Gorelick; Ян Ozsvald) синхронизации, из которого был получен выше.