Оптимизация кода Python

posted in Development on by

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

Хотя, на первый взгляд кажется, что Python и быстрый код не совместимые понятия, это не совсем правда.

Все тесты проводились на Python 3.3.3 и, само собой, не обошлось без IPython, который ну просто killer-feature этого языка.

Строки

Python предоставляет довольно удобные возможности по работе с строками, тем не менее, не все способы одинаково быстры. Так что просто возьмем несколько строк и попробуем их объеденить тем или иным способом.

str1 = 'val1'
str2 = 'val2'
str3 = 'val3'

Честно говоря, получившиеся замеры скорости конкатенации строк вышли несколько озадачивающими. На мой взгляд, они противоречат не только рекомендациям не использовать + как медленную операцию 1, но и здравому смыслу 2

%timeit res = 'str1: ' + str1 + ' str2: ' + str2 + ' str3: ' + str3 # (1)
%timeit res = 'str1: %s str2: %s str3: %s' % (str1, str2, str3)
%timeit res = 'str1: {} str2: {} str3: {}'.format(str1, str2, str3)  # (2)
%timeit res = 'str1: {0} str2: {1} str3: {2}'.format(str1, str2, str3) # (3)
%timeit "".join(['str1: ', str1, 'str2: ', str2, 'str3: ', str3]) # (4)
1000000 loops, best of 3: 446 ns per loop
1000000 loops, best of 3: 453 ns per loop
1000000 loops, best of 3: 675 ns per loop
1000000 loops, best of 3: 416 ns per loop
1000000 loops, best of 3: 375 ns per loop

Как видно из тестов, самый лучший, да и самый читабельный вариант – использовать функцию format явно указывая порядковый номер подставляемой подстроки 3.

Часто рекомендуемый вариант с join 4 дает достаточно посредственную скорость, что, отчасти, связанно с необходимостью формировать дополнительный список подстрок для объединения. Если же список подстрок уже имеется, то этот вариант будет лучшим.

l = ['str1: ', str1, 'str2: ', str2, 'str3: ', str3]
%timeit "".join(l)
1000000 loops, best of 3: 220 ns per loop

Массивы и списки

К сожалению, в Python отсутствуют привычные C++ разработчикам массивы. При этом, доступны списки, в CPython реализованные массивами указателей, обеспечивающие константный доступ к элементам. Кроме того, есть массивы из модуля array, массивы из NumPy.

Я ожидал что наилучший результат в произвольном RW доступе покажут массивы из NumPy, но, с учетом того что они были разработаны не для этого, предположение оказалось ложным. Поэтому, приведу тесты в порядке возрастания для массива размером 1000000 элементов. Для массивов данных в 10-100 элементов вариант с преаллокацией оказывается более быстрым, но дальше начинает отставать.

count = 1000000

%%timeit
l = [i for i in range(count)]
10 loops, best of 3: 60.9 ms per loop

Кстати, C/C++ разработчики, обратит внимание на следующий момент. Казалось бы более быстрый способ с предварительной аллокацией массива нужного размера оказывается более медленным вариантом по сравнению с использованием List comprehensions. Все дело в том, что Python – интерпретируемый язык и любая встроенная функция дает ощутимый прирост производительности.

%%timeit
l = [0]*count
for i in range(count):
    l[i] = i
10 loops, best of 3: 76.9 ms per loop

При использовании NumPy массивов важно сразу указать тип размещаемых в нем данных, почему это важно будет понятно из пункта “Сравнение типов”, иначе скорость работы будет еще ниже.

%%timeit
import numpy as np

l = np.array(np.zeros(count), dtype=int) # (1)
for i in range(count):
    l[i] = i
10 loops, best of 3: 106 ms per loop

Приведенный ниже пример использует тип array не по назначению и, как следствие, скорость работы соответствующая.

%%timeit
from array import array

l = array('i', (i for i in range(count)))
1 loops, best of 3: 275 ms per loop

Мне кажется, результат интересный: самый быстрый способ является самым очевидным способом. После C++ это даже немного удивительно

Умножение и деление

Умножение и деление – еще один сюрприз от авторов Python для C++ разработчиков. Самый быстрый способ поделить/умножить на степень двойки – сдвиги. Все помнят, верно? Верно-то верно, но не везде.

bit_k = 0x80

%timeit bit_k >> 1
%timeit bit_k / 2
10000000 loops, best of 3: 73.3 ns per loop
10000000 loops, best of 3: 52.7 ns per loop
%timeit bit_k << 1
%timeit bit_k * 2
10000000 loops, best of 3: 74.1 ns per loop
10000000 loops, best of 3: 47.4 ns per loop

В Python сдвиги ощутимо медленнее операций умножения/деления.

Сравнение типов

На этот пункт нужно обратить особо пристальное внимание, т.к. на алгоритмах что-то активно считающих, благодаря невнимательному отношению к типу данных, можно получить падение скорости в 2-4 раза (!!!).

Все дело в том, что операции сравнения между целочисленными типами и типами с плавающей запятой необычайно медленные, что хорошо видно из примера ниже. Поэтому, если в процессе оптимизации какая-то функция активно сравнивает что-либо, желательно удостовериться в том, что типы сравниваемых данных совпадают. Например, тесты на Computer Language Shootout нередко подверженны этой проблеме и путем добавления .0 некоторые из них можно ускорить в те самые 2-4 раза.

%timeit 10 < 10.0
%timeit 10.0 < 10.0
%timeit 10 < 10
1000000 loops, best of 3: 213 ns per loop
10000000 loops, best of 3: 33.2 ns per loop
10000000 loops, best of 3: 31.4 ns per loop

Можно предположить, что все дело все в том, что конвертация между типами очень медленная операция:

%timeit float(10)
%timeit int(10.0)
1000000 loops, best of 3: 391 ns per loop
1000000 loops, best of 3: 380 ns per loop

Но, несмотря на то, что конвертация операция действительно очень медленная, дело не в этом:

def comparation():
    1 < 10.0

def conversion():
    int(10.0)

import dis

print("Comparation:")
dis.dis(comparation)
print("Conversion:")
dis.dis(conversion)
Comparation:
  2           0 LOAD_CONST               1 (1)
              3 LOAD_CONST               2 (10.0)
              6 COMPARE_OP               0 (<)
              9 POP_TOP              
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE        
Conversion:
  5           0 LOAD_GLOBAL              0 (int)
              3 LOAD_CONST               1 (10.0)
              6 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
              9 POP_TOP              
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

А в том, что инструкция VM Python COMPARE_OP неэффективно обрабатывает параметры разных типов.

Циклы

Все принципы оптимизации в Python схожи, и циклы не исключение. Если что-то можно заменить на встроенные функции – надо менять, т.к. VM довольно медленная.

%%timeit
val = 0
for i in range(1000):
    val += i
10000 loops, best of 3: 60.1 µs per loop
%%timeit
from functools import reduce
from operator import add

reduce(add, range(1000))
10000 loops, best of 3: 81.8 µs per loop

Встроенная функция из Python может оказаться в ~1.7 раз быстрее самописной:

%%timeit
from functools import reduce

reduce(lambda res, x: res+x, range(1000))
10000 loops, best of 3: 144 µs per loop

И лямбды тут практически ни при чем.

from functools import reduce
from operator import add

%timeit reduce(lambda res, x: res+x, range(1000))

def my_add(res, x):
    return res + x
%timeit reduce(my_add, range(1000))

%timeit reduce(add, range(1000))
10000 loops, best of 3: 144 µs per loop
10000 loops, best of 3: 139 µs per loop
10000 loops, best of 3: 76.8 µs per loop

Глобальные и локальные переменные

oldlist = [str(i) for i in range(500)]
[cc lang='python']
newlist = []

def f_global():
    for word in oldlist:
        newlist.append(word.upper())

%timeit f_global()
10000 loops, best of 3: 108 µs per loop
def f_local(l):
    newlist = []
    for word in l:
        newlist.append(word.upper())
    return newlist

%timeit newlist = f_local(oldlist)
10000 loops, best of 3: 90 µs per loop

В данном случае все дело в инструкциях использующихся для загрузки локальных и глобальных переменных LOAD_GLOBAL и LOAD_FAST соответственно. Как видно из тестов, на Python 3.3.3 при правильной организации доступа к данным можно получить ускорение порядка 20%.

import dis

print("Global data:")
dis.dis(f_global)
print("Local data:")
dis.dis(f_local)
Global data:
  4           0 SETUP_LOOP              33 (to 36)
              3 LOAD_GLOBAL              0 (oldlist)
              6 GET_ITER            
        >>    7 FOR_ITER                25 (to 35)
             10 STORE_FAST               0 (word)

  5          13 LOAD_GLOBAL              1 (newlist)
             16 LOAD_ATTR                2 (append)
             19 LOAD_FAST                0 (word)
             22 LOAD_ATTR                3 (upper)
             25 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             28 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             31 POP_TOP              
             32 JUMP_ABSOLUTE            7
        >>   35 POP_BLOCK            
        >>   36 LOAD_CONST               0 (None)
             39 RETURN_VALUE        
Local data:
  2           0 BUILD_LIST               0
              3 STORE_FAST               1 (newlist)

  3           6 SETUP_LOOP              33 (to 42)
              9 LOAD_FAST                0 (l)
             12 GET_ITER            
        >>   13 FOR_ITER                25 (to 41)
             16 STORE_FAST               2 (word)

  4          19 LOAD_FAST                1 (newlist)
             22 LOAD_ATTR                0 (append)
             25 LOAD_FAST                2 (word)
             28 LOAD_ATTR                1 (upper)
             31 CALL_FUNCTION            0 (0 positional, 0 keyword pair)
             34 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             37 POP_TOP              
             38 JUMP_ABSOLUTE           13
        >>   41 POP_BLOCK            

  5     >>   42 LOAD_FAST                1 (newlist)
             45 RETURN_VALUE

Вызов функции VS сохранение и вызов

В рекомендациях по оптимизации кода на Python можно встретить упоминания того, что если функцию, вызывающуюся много раз подряд сначала сохранить в какой-либо переменной, а потом вызывать, то код более быстрым (в ущерб читабельности, конечно). Причина все та же – глобальные данные (в данном случае функция) загружаются дольше чем локальные. Теперь в роли медленной команды выступает LOAD_ATTR, а в качестве быстрой, как и раньше, LOAD_FAST.

def direct_call():
    newlist = []
    newlist.append(1)
    return newlist

def store_and_call():
    newlist = []
    na = newlist.append
    na(1)
    return newlist


import dis
print("Direct call:")
dis.dis(direct_call)
print("Store and call:")
dis.dis(store_and_call)
Direct call:
  2           0 BUILD_LIST               0
              3 STORE_FAST               0 (newlist)

  3           6 LOAD_FAST                0 (newlist)
              9 LOAD_ATTR                0 (append)
             12 LOAD_CONST               1 (1)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 POP_TOP              

  4          19 LOAD_FAST                0 (newlist)
             22 RETURN_VALUE        
Store and call:
  7           0 BUILD_LIST               0
              3 STORE_FAST               0 (newlist)

  8           6 LOAD_FAST                0 (newlist)
              9 LOAD_ATTR                0 (append)
             12 STORE_FAST               1 (na)

  9          15 LOAD_FAST                1 (na)
             18 LOAD_CONST               1 (1)
             21 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             24 POP_TOP              

 10          25 LOAD_FAST                0 (newlist)
             28 RETURN_VALUE

Кажется, на этом полезные рекомендации заканчиваются, в крайнем случае мне больше ничего работающего и не требующего установки чего-то нетривиального и сложного, например PyCUDA, Numba и т.д. не попалось. А про PyCUDA, Numba я, наверное, напишу отдельно и чуть позже.

Похожие заметки:

  1. Устанавливаем OpenCV 3 для Python 3 на macOS
  2. Список языков и его обработка
  3. Python 3.4, asyncio

2 Comments → Оптимизация кода Python

Leave a Reply