0,0
рейтинг
19 июля 2011 в 01:38

Разработка → Ускорение кода на Python средствами самого языка

Каким бы хорошим не был Python, есть у него проблема известная все разработчикам — скорость. На эту тему было написано множество статей, в том числе и на Хабре.


Чаще всего, предлагают следующие решения:
  • Использовать Psyco
  • Переписать часть программы на С используя Python C Extensions
  • Сменить мозгиалгоритм


Безусловно, решения верные. Но у каждого из них есть свои недостатки.
Psyco — прекрасный модуль, достигающий ускорения кода в сотни процентов, но: поддерживаются лишь 32-битный Python версий не выше 2.6, большое потребление памяти и тот факт, что в последнее время разработка psyco сбавила темпы, последнее обновление на сайте датировано 16.07.2010. Возможно, с выходом Psyco v2 ситуация изменится, но пока что, этот модуль применим не всегда.
Python C Extensions (рекомендую отличную статью rushman Пишем модуль расширения для Питона на C) — создатели Python'a сделали всем разработчикам, использующим этот язык, неоценимый подарок — Python/С API, дающий возможность относитенльно прозрачной интеграции Си-шного кода в программы на Python'e. Недостатков у этого решения только два:
  1. «Порог вхождения» у C и Python/C API все же выше, чем у «голого» Python'a, что отсекает эту возможность для разработчиков, не знакомых с C
  2. Одной из ключевых особенностей Python является скорость разработки. Написание части программы на Си снижает ее, пропорционально части переписанного в Си кода к всей программе

Так что, данный метод тоже подойдет не всем.
Смена алгоритма же возможна не всегда, часты ситуации, что и самый быстрый алгоритм выдает разочаровывающие результаты по скорости.

Так что же делать?

Тогда, если для вашего проекта выше перечисленные методы не подошли, что делать? Менять Python на другой язык? Нет, сдаваться нельзя. Будем оптимизировать сам код. Примеры будут взяты из программы, строящей множество Мандельброта заданного размера с заданным числом итераций.
Время работы исходной версии при параметрах 600*600 пикселей, 100 итераций составляло 3.07 сек, эту величину мы возьмем за 100%


Скажу заранее, часть оптимизаций приведет к тому, что код станет менее pythonic, да простят меня адепты python-way.

Шаг 0. Вынос основного кода программы в отдельную

Данный шаг помогает интерпретатору python лучше проводить внутренние оптимизации про запуске, да и при использовании psyco данный шаг может сильно помочь, т.к. psyco оптимизирует лишь функции, не затрагивая основное тело программы.
Если раньше рассчетная часть исходной программы выглядела так:
for Y in xrange(height):
        for X in xrange(width):
                #проверка вхождения точки (X,Y) в множество Мандельброта, itt итераций 

То, изменив её на:
def mandelbrot(height, itt, width):
    for Y in xrange(height):
        for X in xrange(width):
             #проверка вхождения точки (X,Y) в множество Мандельброта, itt итераций 
mandelbrot(height, itt, width)

мы получили время 2.4 сек, т.е. 78% от исходного.

Шаг 1. Профилирование

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

python -m cProfile sample.py
Ключ интерпетатора -m позволяет запускать модули как отдельные программы, если сам модуль предоставляет такую возможность.
Результатом этой команды будет получение «профиля» программы — таблицы, вида
4613944 function calls (4613943 primitive calls) in 2.818 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
1 2.309 2.309 2.766 2.766 mand_slow.py:22(mandelbrot)
...

С её помощью, легко определить места, требующие оптимизации (строки с наибольшими значениями ncalls (кол-во вызовов функции), tottime и percall (время работы всех вызовов данной функции и каждого отдельного соответственно)).

Для удобства можно добавить ключ -s time, отсортировав вывод профилировщика по времени выполнения.

В моем случае интересной частью вывода было (время выполнение отличается от указанного выше, т.к. профилировщик добавляет свой «оверхед»):
4613944 function calls (4613943 primitive calls) in 2.818 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
1 2.309 2.309 2.766 2.766 mand_slow.py:22(mandelbrot)
3533224 0.296 0.000 0.296 0.000 {abs}
360000 0.081 0.000 0.081 0.000 {math.atan2}
360000 0.044 0.000 0.044 0.000 {math.cos}
360000 0.036 0.000 0.036 0.000 {math.sqrt}
...

Итак, профиль получен, теперь займемся оптимизацией вплотную.

Шаг 2. Анализ профиля

Видим, что на первом месте по времени стоит наша основная функция mandelbrot, за ней идет системная функция abs, за ней несколько функций из модуля math, далее — одиночные вызовы функций, с минимальными временными затратами, они нам не интересны.

Итак, системные функции, «вылизаные» сообществом, нам врядли удастся улучшить, так что перейдем к нашему собственному коду:

Шаг 3. Математика

Сейчас, код выглядит так:
pix = img.load() #загрузим массив пикселей
def mandelbrot(height, itt, width):
    step_x = (2 - width / 1.29) / (width / 2.6) - (1 - width / 1.29) / (width / 2.6) #шаг по оси х 
    for Y in xrange(height):
        y = (Y - height / 2) / (width / 2.6) #для Y рассчет шага не так критичен как для Х, его отсутствие положительно повлияет на точность
        x = - (width / 1.29) / (width / 2.6)
        for X in xrange(width):
            x += step_x
            z = complex(x, y)

            phi = math.atan2(y, x - 0.25)
            p = math.sqrt((x - 0.25) ** 2 + y ** 2)
            pc = 0.5 - 0.5 * math.cos(phi)

            if p <= pc: #если лежит в области кардиоиды - отмечаем
                pix[X, Y] = (255, 255, 255)
                continue

            Z_i = 0j
            for i in xrange(itt): #проверка на выход за "границы бесконечности"
                Z_i = Z_i ** 2 + z
                if abs(Z_i) > 2:
                    color = (i * 255) // itt
                    pix[X, Y] = (color, color, color)
                    break
            else:
                pix[X, Y] = (255, 255, 255)
        print("\r%d/%d" % (Y, height)),

Заметим, что оператор возведения в степень ** — довольно «общий», нам же необходимо лишь возведение во вторую степень, т.е. все конструкции вида x**2 можно заменить на х*х, выиграв таким образом еще немного времени. Посмотрим на время:
1.9 сек, или 62% изначального времени, достигнуто простой заменой двух строк:
p = math.sqrt((x - 0.25) ** 2 + y ** 2)
...
Z_i = Z_i **2 + z

на:
p = math.sqrt((x - 0.25) * (x - 0.25) + y * y)
...
Z_i = Z_i * Z_i + z


Шажки 5, 6 и 7. Маленькие, но важные

Прописная истина, о которой знают все программисты на Python — работа с глобальными переменными медленней работы с локальными. Но часто забывается факт, что это верно не только для переменных но и вообще для всех объектов. В коде функции идут вызовы нескольких функций из модуля math. Так почему бы не импортировать их в самой функции? Сделано:
def mandelbrot(height, itt, width):
    from math import atan2, cos, sqrt
    pix = img.load() #загрузим массив пикселей

Еще 0.1сек отвоевано.
Вспомним, что abs(x) вернет число типа float. Так что и сравнивать его стоит с float а не int:
if abs(Z_i) > 2:  ------> if abs(Z_i) > 2.0: 

Еще 0.15сек. 53% от начального времени.

И, наконец, грязный хак.
В конкретно этой задаче, можно понять, что нижняя половина изображения, равна верхней, т.о. число вычислений можно сократить вдвое, получив в итоге 0.84сек или 27% от исходного времени.

Заключение

Профилируйте. Используйте timeit. Оптимизируйте. Python — мощный язык, и программы на нем будут работать со скоростью, пропорциональной вашему желанию разобраться и все отполировать:)
Цель данной статьи, показать, что за счет мелких и незначительных изменения, таких как замен ** на *, можно заставить зеленого змея ползать до двух раз быстрее, без применения тяжелой артиллерии в виде Си, или шаманств psyco.
Также, можно совместить разные средства, такие как вышеуказанные оптимизации и модуль psyco, хуже не станет:)

Спасибо всем кто дочитал до конца, буду рад выслушать ваши мнения и замечания в комментариях!

UPD Полезную ссылку в коментариях привел funca.
Владислав Степанов @Utter_step
карма
74,5
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (40)

  • +3
    Так почему бы не импортировать их в самой функции?
    здесь, напротив, рекомендуют так не делать — если функция станет выполняться многократно, то импорты будут создавать лишний оверхед, т.к. python всё равно вынужден их интерпретировать и выполнять. поместить имена в локальный контекст можно другим способом.

    думаю, функция сильно выиграет, если вынесите повторяющиеся вычисления за пределы циклов. например (width / 1.29), (width / 2.6)
    • 0
      Промахнулся с утра…

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

      Днем помещу Ваши замечания в пост, спасибо за коментакрий!
    • +3
      будет ~0 прирост, потому что это самый внешний цикл. практически вся работа в самом вложенном (300 итераций который).
  • 0
    С первым — в общем случае вы правы, но к функциям полученным на шаге 0 это не совсем применимо, чаще всего они отрабатывают один раз. Но для часто вызываемых функций Ваше решение безусловно будет верней.

    Со вторым — не совсем. Интерпретатор при запуске создает кортеж co_constants, в котором лежат значения неизменные для всего вызова функции, так что по сути эти значения будут вычислены единожды при запуске.
  • +3
    >… за счет мелких и незначительных изменения, таких как замен ** на *, можно заставить зеленого змея ползать до двух раз быстрее, без применения тяжелой артиллерии…

    Из чего следует, что питону не хватает умного оптимизатора кода (в случае CPython, на этапе py->pyc), наподобие тех, что есть в си-компиляторах уже годы как. Хватило хотя бы банального сопоставления с известными алгоритмическими паттернами, типа вот этого возведения в квадрат или приведения типов.
    • +11
      Не всё так просто. А всё из-за динамической типизации: в выражении x**2 икс может оказаться объектом с перегруженнным методом __pow__, и тогда замена на __mul__(2) неправомерна, так как спецификация языка не обызявает авторов наделять __pow__ семантикой возведения в степень. Поэтому необходимо сначала доказать, что икс будет вещественным числом (или если доказать невозможно, то «заметить», что в большинстве случаев он является вещественным), и сделать замену (а если не доказали — то вставить проверку типа в том месте, где доказательство сломалось и контролировать правомерность оптимизации).
      • +1
        В этом смысле pypy рулит, т.к. у него как раз вся информация есть о типах реал-тайм, JIT поэтому же теоретически (и иногда практически) может давать более оптимизированный код и большее ускорение, чем статический компилятор.
    • –1
      В качестве умного оптимизатора кода в данном случае должен выступать сам программист. Не умеете писать на Python'е — пишите блин на Visual Basic. Там действительно в большинстве случаев препроцессор и оптимизатор априори умнее программиста, даже подсказки дают что где не так написано.
      • +1
        Для Python'а есть кстати pylint, он иногда помогает вскую чушь исправлять.
  • 0
    Можно не считать арктангенс и потом косинус.
    cos(arctan(y / x)) = x / sqrt(x*x + y*y)
    так как вы p уже посчитали, то
    phi = math.atan2(y, x — 0.25)
    pc = 0.5 — 0.5 * math.cos(phi)
    можно заменить на
    pc = 0.5 — 0.5 * x / p

    С другой стороны эта оптимизация в среднем цикле, а вся работа в самом вложенном. Я даже не уверен замена y ** 2 на y * y и т.д. дала бы видимый прирост.

    P.S. PyPy is the new psyco
    • 0
      Как ни странно, замена pc = 0.5 — 0.5 * x / p, приводит к увеличению времени работы на 0.17сек, т.е. на 5%. Вечером попробую разобраться, интересный момент.

      Замена y ** 2 на y * y дает прирост в ~4%, т.к. даже средний цикл выполняется ширина * высота раз, т.е. в данном случае 600 * 600 = 360000 раз.
      • 0
        Да, но внутренний цикл выполняется в 300 раз чаще. Я понимаю что во многих случаях до него работа и не доходит вовсе. И все-таки, для меня сюрприз что аж 4% прирост
        • 0
          Если интересует — могу в ЛС кинуть код, получившийся наиболее оптимальным.
  • +1
    Последняя оптимизация вообще не понятно, для чего приведена. «А еще я обнаружил, что такая картинка у меня уже давно сгенерирована, поэтому генерация заняла 0с».
    • +4
      Ну это уже так, баловство:)

      Да и на самом деле ситуация немного сложнее чем Вы описали — задачи с симметричными решениями — частая ситуация, поэтому найдя ось симметрии можно действительно сократить время выполнения вдвое.
      Но все же, это далеко от общего случая поэтому и указанно вскользь, как небольшой хак.
      • +1
        ИМХО наоборот эта оптимизация должна была идти первой. После чего разработчик должен почесать затылок и подумать, может быть 1.5сек достаточно для его задачи и имеет ли смысл платить ухудшением кода за дополнительные 18% скорости. Ответ будет зависеть от задачи и далеко не всегда дальнейшая оптимизация будет иметь смысл.
        • –1
          Верно, но а) эта оптимизация не применима в общем случае, в отличии от остальных описанных
          б) я не просто так указывал процентное изменение, 1.5сек вполне достаточно, но код, работающий с 600*600 за 1.5 сек отработает на, скажем 6000*6000 (адекватное разрешение для изучения фрактала) за ~150сек, а тут уж даже десятые доли процента не помешают.
          После всех оптимизаций+хак, 6000*6000 обрабатывается за 79сек, что всяко лучше 150.)
          • 0
            Да, оптимизации иногда важны и нужны. Однако даже в случае 150сек на обработку вашего фрактала, действительно ли 2.5 минуты это много? Ведь изучение может занять ну по крайней мере часы, так что минуту или две будет генерироваться картинка — часто тоже имеет весьма мало значения.

            Я в общем-то к чему — любая цифра должна рассматриваться в контексте. Для какого-то вычисления 2 минуты катастрофически много, а для какой-то работы, которая сама по себе занимает часы, 2 минуты или одна — не более чем статистическая погрешность, и портить из-за нее код не имеет смысла.
  • +1
    blip.tv/pycon-us-videos-2009-2010-2011/introduction-to-python-profiling-1966784

    название видео говорит само за себя. Отличный материал про профилирование на питоне с 2009 pycon
  • +3
    Как-то все слишком мудрено и сравнительно малорезультативно.
    а) На Psyco больше рассчитывать не стоит, вместо него надо смотреть на pypy
    б) Задачка вычислительная => очень легко и полезно было бы использовать cython. Получится сишной расширение, С для этого знать особо не надо, скорость разработки практически такая же как и у Python. (Скорее всего ускорение 2х можно будет получить вообще ничего не делая и просто скомпилировав уже имеющийся cython'ом). При правильной оптимизации можно получить ускорение 100х и больше.
  • 0
    Хороший материал, спасибо за статью.
  • +1
    мне тут сосед подсказывает что
    там
    1) -(width/1.29)/(width/2.6) это константа, width сокращается и 2.6 делится на 1.29.
    2) (2 — width/1.29)/(width/2.6) — (1-w/1.29)/(w/2.6) = (2 — w/1.29 — 1 + w/1.29)/(w/2.6) = (1/(w/2.6)) = 2.6/w :)
    Ладно если второе выполнится 1 раз, то первое выполнится 600 раз при том что это обычная константа.
  • +2
    Psyco умер, pypy — это «все или ничего» (кусок нельзя ускорить), ускорение через смену алгоритма — это абсолютно правильно, но и так понятно, профайлер — это хорошо.

    Но на практике подобные вычисления стоит ускорять через cython или numpy. Не нужно их бояться) Cython не потребует даже переписывать код (можно просто рядом очень небольшой файлик с подсказками положить), numpy переписывать потребует, но, скорее всего, в итоге код короче получится.
  • 0
    Ещё можно экономить на создании объектов. Например, не создавать каждый раз в цикле xrange(width), а сделать в начале функции «width_range = range(width)», а внутри уже «for X in width_range:».
    • 0
      xrange(width) это генератор, а range(width) даст список. Создание генератора довольно простая вещь, тем более он сам себе и итератор. Пробег по списку создаст скрытый итератор в цикле. К тому же при ощутимо большом width будем сильно потреблять память.

      Итог: по моему xrange почти всегда лучше.
      • 0
        С первым абзацем полностью согласен.

        Но то, что xrange «почти всегда лучше» это немного некорректный вывод. Если надо меньше памяти, то, конечно, лучше xrange. Но если надо быстрее (а топик был именно о скорости), то избавившись от создания сотен или тысяч мелких одинаковых объектов, пусть даже генераторов, можно выиграть немного времени. Я проверял.
        • 0
          В любом случай range или xrange создается один раз.
          • 0
            Как это — в любом?
            • 0
              А, вы имели ввиду внутренний цикл. Извиняюсь, не понял.
              А как вы собираетесь «сбрасывать» xrange? Второй раз он не итерируется просто так.
              • 0
                А не, итерируется. Я мучал сам итератор, а не xrange.
                • +1
                  О, и правда. Тогда вообще всё замечательно: width_range=xrange(width) — и расход памяти не увеличивается, и скорость растёт.
              • 0
                См. исходный комментарий:
                Например, не создавать каждый раз в цикле xrange(width), а сделать в начале функции «width_range = range(width)», а внутри уже «for X in width_range:».
        • 0
          При пробеге по списку интерпретатор создает итератор по списку (в прямом смысле вызывая __iter__), что по любому создаст «мелкий одинаковый объект».

          Да, вывод не верный. Более правильно будет: для циклов по целым числам быстрей xrange.

          А range нужен что бы просто создать список. Любой список. Способность пробежаться по нему, к примеру по буквам range('a', 'z') это скорее бонус =)
          • 0
            1) __iter__-__iter__ом, но ведь имеет значение, вызывать __iter__ у уже существующего инстанса или каждый раз создавать его перед вызовом?

            2) range всё-таки может создать не любой список, а только «containing arithmetic progressions» (http://docs.python.org/library/functions.html#range). range('a', 'z') это вообще TypeError.

            3) в конце-концов, можно позвать cProfiler, и проверить:

            import cProfile
            i = 5000
            
            def xrange_xrange():
                for x in xrange(i):
                    for y in xrange(i):
                        (x, y)
            
            def xrange_prerange():
                y_range = range(i)
                for x in xrange(i):
                    for y in y_range:
                        (x, y)
            
            for _ in range(10):
                cProfile.run('xrange_xrange()')
                cProfile.run('xrange_prerange()')
                print '=' * 10
            


            Сокращённый вывод:
            ==========
            3 function calls in 7.061 CPU seconds
            4 function calls in 6.022 CPU seconds
            ==========
            3 function calls in 6.605 CPU seconds
            4 function calls in 5.749 CPU seconds
            ==========
            3 function calls in 6.548 CPU seconds
            4 function calls in 5.927 CPU seconds
            ==========
            3 function calls in 6.052 CPU seconds
            4 function calls in 6.182 CPU seconds
            ==========
            3 function calls in 5.970 CPU seconds
            4 function calls in 5.966 CPU seconds
            ==========
            3 function calls in 7.590 CPU seconds
            4 function calls in 5.955 CPU seconds
            ==========
            3 function calls in 6.167 CPU seconds
            4 function calls in 5.867 CPU seconds
            ==========
            3 function calls in 6.763 CPU seconds
            4 function calls in 6.048 CPU seconds
            ==========
            3 function calls in 5.988 CPU seconds
            4 function calls in 5.690 CPU seconds
            ==========
            3 function calls in 5.827 CPU seconds
            4 function calls in 6.048 CPU seconds
            ==========

            Т.е. эффект от выноса range() за внешний цикл хотя и не очень значительный, но есть.
  • 0
    Просьба к автору: не поленитесь, запустите на PyPy, всем же, думаю, интересно :)
    • 0
      Вечером — обязательно!)
      • +1
        Пока испытываю некоторые проблемы с удалением гланд черезсборкой PIL для PyPy под 64bit виндой.
        Если так и не выйдет — завтра будет под рукой машина под linux, проведу все тесты заново на ней.
      • +1
        Под PyPy так и не удалось завести PIL (RPython вылетал с трейсом:
        Fatal RPython error: NotImplementedError
        про обращении к pixel access object'y PIL'я)

        Однако, если заменить реальную раскраску пикселей на добавление значения цвета в двумерный массив PyPy дает ускорение в 4 раза.
        Но, неизвестно, как бы он отработал взаимодействие с PIL, так что данный результат не стоит считать состоятельным, увы.
  • +3
    Можно значительно улучшить статью, если не заниматься шаманством, а сравнить дизассемблированные листинги.
    import dis
    dis.dis(func)
    

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.