Издательский дом ООО "Гейм Лэнд"ЖУРНАЛ ХАКЕР #123, МАРТ 2009 г.

Сказ о летающем змее. Агрессивная оптимизация программ на Python’e

Алексей Черкес (aleksey.cherkes@gmail.com)




Python применяется там, где скорость разработки программы и простота сопровождения кода важнее скорости его работы. Он нужен для быстрого создания надежных, легко изменяемых программ. Благодаря динамической типизации и большому количеству встроенных высокоуровневых типов данных, Python позволяет быстро создавать лаконичный, выразительный и надежный код. У этих достоинств есть и обратная сторона: низкая скорость выполнения программ.

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

Маленькие хитрости

Интерпретатор Python обладает некоторыми особенностями, которые могут влиять на скорость выполнения программ. Знание этих особенностей поможет в написании более эффективного кода.

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

Например, map(operator.add, l1, l2), скорее всего, будет работать быстрее, чем map(lambda x,y: x+y, v1, v2). Такой подход значительно повышает читабельность кода.
Строки в Python - это неизменяемые объекты (immutable objects). Ты не можешь изменять значения единожды созданной строки, – можно только создать новую и присвоить ей измененное значение старой. Конкатенация строк ' '.join(seq) будет выполняться гораздо быстрее, чем явный цикл с оператором +=. В первом случае новая строка создается один раз и в нее сразу записывается нужное значение. Во втором - каждая итерация порождает новый объект, который на следующей итерации уже не нужен. Это гораздо медленнее, плюс возрастает нагрузка на сборщик мусора. То же самое касается оператора «%» для формирования строк по шаблону. Он куда эффективнее прямого суммирования.

Многие функции, порождающие последовательности, имеют альтернативную версию, использующую генераторы. Например, при каждом вызове range(n) в памяти создается список длиной n. А вот при вызове xrange(n) в памяти вообще не создается никаких коллекций, только генератор, который вычисляет элементы последовательности «ленивым» образом. Не забудь про generator expressions, – часто про них забывают и пользуются list comprehensions.

Полезно также держать в голове базовые алгоритмы, на которых основана работа с коллекциями. Конечно, комфортный синтаксис Python убивает бдительность, но нужно стараться :). Словари и множества реализованы на деревьях, поэтому, например, при большом N проверка принадлежности элемента коллекции (a in b) проходит в среднем быстрее для словарей и множеств, чем для списков или кортежей, для которых в этих случаях выполняется полный перебор. Добавление или удаление элементов списка в хвосте выполняется быстрее, чем в середине, так как для этого не нужно перестраивать список.

Из-за динамической природы языка, процедура поиска переменной по ее имени выполняется дольше в сравнении с компилируемыми языками. Вызов функции - тоже затратная операция, по вышеуказанным причинам. Вызов метода объекта obj.foo() по сложности сравним с поиском элемента в словаре со строковыми ключами. Поиск имен происходит быстрее для локальных, чем для глобальных переменных. Конечно, обычно на это не стоит обращать внимания. Но, например, в теле цикла с огромным числом итераций стоит пойти на хитрость: по возможности вынести как можно больше действий из тела цикла, сделать предварительные вычисления.

Очевидно, что операция импорта - очень медленная, ведь интерпретатору нужно полностью выполнить весь запрашиваемый модуль. Обычно все операции импорта модулей прописывают в начале скрипта. Но бывают случаи, когда модуль используется редко. Тогда можно не указывать его в начале скрипта, чтобы он не отъедал время при инициализации, а написать приблизительно следующее:

module_name = None

def delay_import():
global module_name
if module_name is None:
import module_name

Модуль module_name будет импортирован во время вызова функции delay_import(). Самое главное - расширения на С. Они могут быть очень эффективными. Классический пример - модуль NumPy (реализация на С матриц и многомерных массивов, плюс библиотека всего необходимого для математических вычислений). По производительности она спокойно догоняет коммерческий MatLab. Но так как Python гораздо более гибок, чем скриптовый язык MatLab, то связку NumPy + Python можно рассматривать как очень удачный open-source проект, который не дает спать по ночам жадным капиталистам. Если ты думаешь, что писать Python-расширения на С - долгое и нудное занятие, советую обратить внимание на проект PyRex. Это компилируемый язык, похожий на Python. Код на этом языке можно смешивать с кодом Python в одной программе, а писать с его помощью модули расширений почти так же просто, как и скрипты на самом Python!

Профилирование

Профайлер - это инструмент для замера времени выполнения различных участков кода. В Python «из коробки» доступно сразу три вида профайлеров (batteries included!). Это модули profile (или cProfile), timeit и hotspot.

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

Модуль profile позволяет анализировать производительность кода в сложных проектах. Он не требует для работы почти никаких изменений в уже написанном коде, в применении прост и способен выдавать разнообразную статистику: количество вызовов каждой функций, среднее время их работы по отдельности и т.д. Также он позволяет трассировать вызовы функции и выдавать информацию о дереве вызовов.

Использовать модуль очень просто. В самом заурядном случае достаточно импортировать модуль profile и вызвать profile.run('main_function()'), передав в качестве параметра функцию, с которой начинается работа. Ниже приведен более сложный пример использования профайлера. Скрипт выводит на консоль табличку для пяти самых затратных по времени работы (без учета дочерних вызовов) функций. Метод strip_dirs() обрезает полные пути в именах файлов:

import profile
import pstats

def main():
# твоя программа
pass

profile.run('main()', 'main_prof')
stats = pstats.Stats('main_prof')
stats.strip_dirs()
stats.sort_stats('time')
stats.print_stats(5)

Сырая статистика, собранная во время данного запуска, сохраняется в файле 'main_prof'. Класс stats анализирует информацию, прочитанную из таких файлов, и выдает в более понятном для простых парней виде. Разрешается объединять информацию из нескольких таких файлов – для общего анализа информации, собранной за несколько запусков (функция stats.add()).

Модуль cProfile делает то же самое, что и модуль profile. Оба модуля обладают почти одинаковым интерфейсом и в большинстве случаев взаимозаменяемы. Разница в том, что cProfile реализован как расширение на языке С, в то время как profile написан исключительно средствами самого Python. Поэтому cProfile обладает меньшей погрешностью и большей высокой скоростью выполнения, но его сложнее портировать на альтернативные платформы. Модуль profile, наоборот, теоретически может запуститься на любом интерпретаторе Python.

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

from timeit import Timer

x = 123

t1 = Timer('x * 2', 'from __main__ import x')
t2 = Timer('x + x', 'from __main__ import x')

number_of_calls = 10**7
time1 = t1.timeit(number = number_of_calls)
time2 = t2.timeit(number = number_of_calls)

print time1 / time2

В результате, на своей машине я получил 1.26. Выходит, моя версия интерпретатора складывает число с самим собой приблизительно на 15-20% быстрее, чем умножает это число на 2. Сложение для целых чисел выполняется быстрее умножения.

JIT-компиляция

Если ты считаешь, что твой код работает слишком медленно (обязательно убедись, что это не паранойя!), то не торопись браться за низкоуровневую оптимизацию. Да, я знаю, руки чешутся, но попытайся себя перебороть - есть более надежные и простые методы повысить производительность.

Иногда достаточно сделать финт ушами: зачем усложнять медленно работающий код, если можно просто заменить виртуальную машину, на которой он выполняется, на более быструю? Дело в том, что стандартная реализация языка (СPython) перед выполнением подпрограмм компилирует их в свое внутреннее представление – байт-код (что-то вроде высокоуровневого ассемблера). Это стандартный подход реализации интерпретаторов. Он используется при реализации многих других технологий (например, Java). Интерпретатор компилирует код вызываемых функций лишь единожды, при первом вызове. При повторных вызовах ему уже не нужно чесать репу над твоими каракулями - он просто пользуется сохраненным в памяти байт-кодом.

Но байт-код - это еще не машинные инструкции, которые подаются процессору. Его тоже нужно интерпретировать! Почему бы не сделать так, чтобы выполняемая программа не компилировалась интерпретатором в байт-код, а переводилась непосредственно в процессорные команды? Такой подход широко используется (например, в .Net) и называется JIT-компиляцией.

Существует модуль расширения для CPython, который добавляет возможности JIT-компиляции в интерпретатор. Имя ему - PsyCo. Для инициализации достаточно написать всего три строчки в главном модуле программы – дальнейшее использование абсолютно прозрачно для программиста. Именно поэтому модуль легко включается в уже готовые проекты. Рассмотрим вариант его использования. Вставь этот код в начало своего главного модуля, и PsyCo заработает по полной программе:

import psyco
psyco.full()
from psyco.classes import *
# Текст программы

Этот модуль обладает более богатыми возможностями для настройки. Например, функция profile() позволяет PsyCo произвести ревизию имеющихся функций и автоматически определить те, для которых оптимизация будет иметь смысл. Для каждой функции производится приблизительная оценка отношения производительности с оптимизацией и без нее. Пользователь может задать порог отношения, при котором оптимизация будет применяться. Можешь, например, сказать: «Не запускай JIT-компилятор для функции foo, если ожидаемое повышение производительности ниже 20%». Кроме этого, PsyCo позволяет задавать ограничения на используемую память и вести лог своей работы.

В стандартной библиотеке Python есть небольшой скрипт pystone.py, тестирующий производительность интерпретатора на базовых операциях (вызов методов, поиск имен, сравнение строк и т.п). Я попробовал сравнить его производительность с PsyCo и без. Так вот, включение PsyCo ускоряет работу теста более чем на 450%! Конечно, это синтетический тест, в нем просто многократно прогоняются одни и тот же метод. В реальных проектах PsyCo стабильно дает повышение производительности приблизительно на 20% и выше.

Не всегда дела обстоят так радостно. К сожалению, PsyCo реализован только для i386-совместимых процессоров. Это делает невозможным его применение, если ты пишешь под какие-то экзотические платформы. Если тебе нужен простой способ включать PsyCo, только когда он есть в системе, воспользуйся этим кодом:

if __name__ == '__main__':
try:
import psyco
psyco.full()
# необходимая инициализация
except ImportError:
pass

В редких случаях производительность программы после бездумного применения PsyCo ухудшается. Связано это с тем, что JTI-компиляция сложнее, чем генерация обычного байт-кода, поэтому она дает эффект, только если обработанная функция используется многократно. Если же программа состоит из большого количества редко вызываемых функций, то возможна потеря производительности.

На сегодняшний день PsyCo перестал интенсивно развиваться, так как разработчики занялись более масштабным детищем - проектом PyPy. Несмотря на это, PsyCo не теряет своей актуальности.

Стратегия

Известный специалист в области компьютерных наук Дональд Кнут говорит, что ранняя оптимизация - корень всех зол. Не зря эти слова так часто цитируют в специальной литературе и свободном интернете! На практике получается, что узкие места в программном коде находятся совсем не там, где их обычно ищут. Действительно, сложность компиляторов стала настолько высока, что редко удается угадать, какой именно машинный код будет сгенерирован даже для таких низкоуровневых языков, как С. Более того, стала сложна и сама техника, на которой выполняются программы. Имея ассемблерный код, и то сложно без испытаний сказать, насколько эффективно современный процессор будет выполнять те или иные его куски. В нашем случае появляется еще один осложняющий фактор – это интерпретатор. Оптимизирован он может быть многими способами, и одна и та же программа на разных реализациях Python будет работать совершенно по-разному.
Я (вместе с Дональдом Кнутом) советую тебе не заморачиваться на оптимизации раньше времени. Всегда пиши лаконичный и наглядный код. Представь, что ты создаешь код в первую очередь не для машины, а для человека, который будет его читать. Ускорить хорошо продуманную и спроектированную программу гораздо легче, чем кривую, но «оптимизированную».

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

WWW

Содержание