Автоматична оптимізація алгоритмів за допомогою швидкого зведення матриць ступінь

Нехай ми хочемо обчислити десятимільйонна число Фібоначчі програми на Python. Функція, що використовує тривіальний алгоритм, на моєму комп'ютері буде виробляти обчислення більше 25 хвилин. Але якщо застосувати до функції спеціальний оптимізуючий декоратор, функція обчислює відповідь всього за 18 секунд (у 85 разів швидше):


Справа в тому, що перед виконанням програми інтерпретатор Python компілює всі її частини в спеціальний байт-код. Використовуючи метод, описаний хабрапользователем SkidanovAlex, даний декоратор аналізує отриманий байт-код функції і намагається оптимізувати застосовується там алгоритм. Далі ви побачите, що ця оптимізація може прискорювати програму не в певну кількість разів, а асимптотично. Так, чим більшою буде кількість ітерацій в циклі, тим більше прискориться оптимізована функція у порівнянні з вихідною.

Ця стаття розповість про те, в яких випадках і яким чином декоратора вдається робити подібні оптимізації. Також ви зможете самі завантажити і протестувати бібліотеку cpmoptimize, що містить даний декоратор.

Теорія
Два роки тому SkidanovAlex опублікував цікаву статтю з описом інтерпретатора обмеженого мови, який підтримує наступні операції:
# Присвоїти змінної іншу змінну або константу
x = y
x = 1

# Додати або відняти з змінної іншу змінну або константу
x += y
x += 2
x -= y
x -= 3

# Помножити на константу змінну
x *= 4

# Запустити цикл із константным числом ітерацій
loop 100000
...
end

Значення змінних у мові повинні бути числами, їх розмір не обмежений (підтримується довга арифметика). Насправді змінні зберігаються як цілі числа в Python, який перемикається в режим довгої арифметики, якщо число виходить за межі апаратно підтримується чотирьох — або восьмибайтового типу.

Розглянемо випадок, коли довга арифметика не використовується. Тоді час виконання операцій не буде залежати від значень змінних, а значить в циклі всі ітерації будуть виконуватися за однаковий час. Якщо виконувати такий код «в лоб», як у звичайних інтерпретаторів, цикл виконається за час , де n — кількість ітерацій. Іншими словами, якщо код n ітерацій працює за час t, то код ітерацій буде працювати за час (див. складність обчислень).

Інтерпретатор з оригінальної статті представляє кожну підтримувану мовою операцію зі змінними у вигляді певної матриці, на яку множиться вектор з вихідними значеннями змінних. В результаті множення ми отримуємо вектор з новими значеннями змінних:



Таким чином, для виконання послідовності операцій потрібно по черзі домножать вектор на матрицю, відповідну чергової операції. Інший спосіб — користуючись асоціативністю, матриці можна спершу помножити одне на одного, а потім помножити вихідний вектор на готовий твір:



Для виконання циклу ми повинні обчислити число n — кількість ітерацій в циклі, а також матрицю B — послідовне твір матриць, відповідних операцій з тіла циклу. Потім потрібно n раз помножити вихідний вектор на матрицю B. Інший спосіб — можна спочатку звести матрицю B ступінь n, а потім помножити вектор зі змінними на результат:



Якщо при цьому використовувати алгоритм бінарного зведення в ступінь, цикл можна буде виконати за значно менший час . Так, якщо код n ітерацій працює за час t, то код ітерацій буде працювати за час (всього лише в два рази повільніше, а не в n разів повільніше, як у попередньому випадку).

У підсумку, як і було написано вище, чим більше буде кількість ітерацій в циклі n, тим в більшу кількість разів прискорюється оптимізована функція. Тому ефект від оптимізації буде особливо добре помітний для великих n.

Якщо довга арифметика все-таки використовується, оцінки часу вище можуть бути неправильні. Наприклад, при обчисленні n-го числа Фібоначчі значення змінних з ітерації в ітерацію стають все більше, і операції з ними сповільнюються. Асимптотическую оцінку часу роботи програми в такому випадку зробити складніше (потрібно враховувати довжину значень змінних на кожній ітерації і використовувані методи множення чисел) і тут вона наведено не буде. Тим не менш, після застосування даного методу оптимізації асимптотика поліпшується навіть у такому випадку. Це добре помітно на графіку:


Ідея
Якщо десятки років тому програмісту було б помножити змінну в програмі на 4, то він використав би не операцію множення, а її більш швидкий еквівалент — бітовий зсув вліво на 2. Тепер компілятори самі вміють робити подібні оптимізації. У боротьбі за скорочення часу розробки з'явилися язики з високим рівнем абстракції, нові зручні технології та бібліотеки. При написанні програм дедалі більшу частину свого часу розробники витрачають на пояснення того комп'ютера, повинна зробити програма (помножити число на 4), а не того, їй це зробити ефективно використовувати бітовий зсув). Таким чином, задача створення ефективного коду частково переноситься на компілятори та інтерпретатори.

Зараз компілятори вміють замінювати різні операції на більш ефективні, пророкувати значення виразів, видаляти або змінювати місцями частини коду. Але компілятори ще не замінюють сам алгоритм обчислень, написаний людиною, на асимптотично більш ефективний.

Реалізацію описуваного методу, представлену в оригінальній статті, проблематично використовувати в реальних програмах, так як для цього доведеться переписати частину коду на спеціальну мову, а для взаємодії з цим кодом доведеться запускати сторонній скрипт з інтерпретатором. Однак, автор статті пропонує використовувати свої напрацювання на практиці в оптимізують компіляторах. Я спробував реалізувати даний метод для оптимізації програм на Python у вигляді, дійсно придатному для використання в реальних проектах.

Якщо використовувати написану мною бібліотеку, для застосування оптимізації достатньо буде дописати перед функцією, яку треба прискорити, одну сходинку із застосуванням спеціального декоратора. Цей декоратор самостійно оптимізує цикли, якщо це можливо, і ні за яких обставин не «ламає» програму.

Приклади використання
Розглянемо низку задач, у яких може стане в нагоді наш декоратор.

Приклад №1. Довгі цикли

Нехай у нас є деяка послідовність, що відповідає правилу, зображеної на схемі, і нам потрібно обчислити її n-ий член:

У такому разі інтуїтивно зрозуміло, як з'являється черговий член послідовності, однак потрібен час, щоб придумати і довести відповідну йому математичну формулу. Тим не менш, ми можемо написати тривіальний алгоритм, що описує наше правило, і запропонувати комп'ютера самому придумати, як швидко рахувати відповідь на наше завдання:
from cpmoptimize import cpmoptimize, xrange

@cpmoptimize()
def f(n):
step1 = 1
step2 = 1
res = 1
for i in xrange(n):
res += step2
step2 += step1
step1 += 1
return res

Цікаво, що якщо запустити цю функцію для , усередині буде запущений цикл ітерацій. Без оптимізації така функція не закінчила б працювати ні за який мислимий проміжок часу, але з декоратором вона виконується менше секунди, повертаючи при цьому правильний результат.

Приклад №2. Числа Фібоначчі

Для швидкого обчислення n-го числа Фібоначчі є швидкий, але нетривіальний алгоритм, заснований на тій же ідеї про зведення матриць в ступінь. Досвідчений розробник може реалізувати його за кілька хвилин. Якщо коду, де проводяться подібні обчислення, не потрібно працювати швидко (наприклад, якщо необхідно одноразово обчислити число Фібоначчі з номером, меншим 10 тисяч), для економії свого робочого часу розробник, швидше за все, вирішить заощадити зусилля і за кілька секунд написати рішення «в лоб».

Якщо програма все-таки повинна працювати швидко, або доведеться докласти зусилля і написати складний алгоритм, або ж можна скористатися методом автоматичної оптимізації, застосувавши до функції наш декоратор. Якщо n досить велика, в обох випадках продуктивність програм вийде майже однаковою, але в другому випадку розробник витратить менше свого робочого часу.

Ви можете порівняти час роботи описаних методів нижче за таблицями і графіками для малих і для великих n.

Справедливості заради слід зазначити, що для обчислення чисел Фібоначчі є ще один алгоритм, відомий як fast doubling. Він кілька виграє попередні алгоритми по часу, так як в ньому виключені зайві додавання і множення чисел. Час обчислень через цей алгоритм також представлено на графіках для порівняння.

Графіки


Результати вимірювань часу
Function "fib":

(*) Testcase "big":
+--------+----------+--------------+--------------+--------------+-------+
| arg | naive, s | cpm, s | matrixes, s | fast dbl, s | match |
+--------+----------+--------------+--------------+--------------+-------+
| 0 | 0.00 | 0.00 | 0.00 | 0.00 | True |
| 20000 | 0.01 | 0.00 (2.5x) | 0.00 (3.0x) | 0.00 (5.3x) | True |
| 40000 | 0.03 | 0.01 (5.8x) | 0.00 (1.8x) | 0.00 (4.9x) | True |
| 60000 | 0.07 | 0.01 (7.7x) | 0.01 (1.4x) | 0.00 (4.8x) | True |
| 80000 | 0.11 | 0.01 (9.6x) | 0.01 (1.3x) | 0.00 (4.6x) | True |
| 100000 | 0.16 | 0.01 (11.7x) | 0.01 (1.2x) | 0.00 (4.3x) | True |
| 120000 | 0.24 | 0.02 (11.6x) | 0.02 (1.2x) | 0.00 (5.0x) | True |
| 140000 | 0.31 | 0.02 (14.6x) | 0.02 (1.1x) | 0.00 (4.1x) | True |
| 160000 | 0.40 | 0.03 (13.8x) | 0.03 (1.1x) | 0.01 (4.2x) | True |
| 180000 | 0.51 | 0.04 (14.2x) | 0.03 (1.1x) | 0.01 (4.3x) | True |
| 200000 | 0.63 | 0.04 (15.9x) | 0.04 (1.1x) | 0.01 (4.6x) | True |
| 220000 | 0.78 | 0.05 (16.1x) | 0.04 (1.1x) | 0.01 (4.8x) | True |
| 240000 | 0.90 | 0.05 (16.6x) | 0.05 (1.1x) | 0.01 (4.8x) | True |
| 260000 | 1.07 | 0.06 (17.3x) | 0.06 (1.1x) | 0.01 (4.6x) | True |
| 280000 | 1.26 | 0.06 (21.4x) | 0.06 (1.1x) | 0.01 (4.1x) | True |
| 300000 | 1.41 | 0.07 (19.2x) | 0.07 (1.1x) | 0.02 (4.4x) | True |
+--------+----------+--------------+--------------+--------------+-------+


На практиці ми можемо зустрітись з більш складною ситуацією, якщо послідовність чисел замість відомої рекурентної формули:


Задається дещо ускладненою формулою, наприклад, такий:


В такому разі ми не зможемо знайти реалізацію описаних вище алгоритмів в Інтернеті, а на те, щоб придумати алгоритм із зведенням матриць в ступінь, піде суттєве час. Тим не менш, ми можемо написати рішення «в лоб» і застосувати декоратор, тоді комп'ютер придумає швидкий алгоритм за нас:
from cpmoptimize import cpmoptimize

@cpmoptimize()
def f(n):
prev3 = 0
prev2 = 1
prev1 = 1
for i in xrange(3, n + 3):
cur = 7 * (2 * prev1 + 3 * prev2) + 4 * prev3 + 5 * i + 6
prev3, prev2, prev1 = prev2, prev1, cur
return prev3

Приклад №3. Сума геометричної прогресії

Нехай нам необхідно обчислити суму count членів геометричної прогресії, для якої задано перший член start і знаменник coeff. В даній задачі декоратор знову здатний оптимізувати наше тривіальне рішення:
from cpmoptimize import cpmoptimize

@cpmoptimize()
def geom_sum(start, coeff, count):
res = 0
elem = start
for i in xrange(count):
res += elem
elem *= coeff
return res

Графік

Приклад №4. Зведення в ступінь

Нехай нам необхідно звести число a невід'ємну цілу ступінь n. У такій задачі декоратор фактично буде замінювати тривіальне рішення на алгоритм бінарного зведення в ступінь:
from cpmoptimize import cpmoptimize

@cpmoptimize()
def power(a, n):
res = 1
for i in xrange(n):
res *= a
return res

Графік

Посилання для скачування
Встановити бібліотеку можна з допомогою pip:
sudo pip install https://github.com/borzunov/cpmoptimize/archive/v0.1.tar.gz

Вихідний код бібліотеки з прикладами доступний на github під вільною ліцензією MIT.

Приклади застосування оптимізації знаходяться в папці "tests/". Кожен приклад складається з функції, що представляє рішення «в лоб», її оптимізованого варіанту, а також функцій, які представляють відомі складні, але швидкі рішення даної задачі. Ці функції поміщені в скрипти, які запускають їх на різних групах тестів, заміряють час їх роботи і будують відповідні таблиці. Якщо встановлена бібліотека matplotlib, скрипти також будуть будувати графіки залежності часу роботи функцій від вхідних даних (звичайні або логарифмічні) і зберігати їх в папку "tests/plots/".

Опис бібліотеки
При створенні бібліотеки я скористався тим, що байт-код програми, який створює інтерпретатор Python, на етапі виконання можна аналізувати і змінювати без втручання в інтерпретатор, що дає широкі можливості по розширенню мови (див., наприклад, реалізація конструкції goto). Переваги описуваного методу зазвичай проявляються при використанні довгої арифметики, яка також вбудована в Python.

З цих причин реалізація описуваної оптимізації в Python стала для мене більш цікавим завданням, хоча, звичайно, її застосування в компіляторах C++ дозволило б створювати ще більш швидкі програми. До того ж, оптимізований декоратором код на Python, як правило, обганяє код «в лоб» на C++ завдяки більш гарною асимптотику.

При модифікації байт-коду я використовував модуль byteplay, надає зручний інтерфейс для дизассемблирования і асемблювання байт-коду. На жаль, модуль ще не був портований на Python 3, тому весь проект я реалізовував на Python 2.7.

Назва бібліотеки cpmoptimize є скороченням від слів "compute the power of a matrix and optimize". Обсяг статті не дозволяє докладно розповісти про процес аналізу та модифікації байт-коду, однак я постараюся докладно описати, які можливості надає дана бібліотека і на яких засадах ґрунтується її робота.

Власний xrange

cpmoptimize.xrange(stop)
cpmoptimize.xrange(start, stop[, step])

Вбудований тип xrange в Python 2 в цілях оптимізації не підтримує довгі цілі типу long в якості аргументів:
>>> xrange(10 ** 1000)
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
OverflowError: Python int too large to convert to C long

Так як при використанні нашої бібліотеки цикли з кількістю операцій близько можуть виконуватися менше, ніж за секунду, і стати в програмі звичайною справою, бібліотека надає власну реалізацію типу xrange на чистому Python (всередині бібліотеки, вона називається CPMRange). Вона підтримує всі можливості звичайного xrange і, крім того, аргументи типу long. Такий код не призведе до помилок і швидко розрахувати правильний результат:
from cpmoptimize import cpmoptimize, xrange

@cpmoptimize()
def f():
res = 0
for i in xrange(10 ** 1000):
res += 3
return res

print f()

Тим не менш, якщо у вашому випадку кількість ітерацій в циклах невелика, ви можете продовжувати використовувати разом з декоратором вбудований xrange.

Функція cpmoptimize

cpmoptimize.cpmoptimize(strict=False iters_limit=5000, types=(int, long), opt_min_rows=True, opt_clear_stack=True)

Застосування декоратора
Функція cpmoptimize приймає параметри виробленої оптимізації і повертає декоратор, що враховує ці параметри, який і потрібно застосувати до оптимізованної функції. Це можна зробити, використовуючи спеціальний синтаксис (з символом «собака») або без нього:
from cpmoptimize import cpmoptimize

@cpmoptimize()
def f(n):
# Деякий код

def naive_g(n):
# Деякий код

smart_g = cpmoptimize()(naive_g)

Перед внесенням змін в байт-код вихідна функція копіюється. Таким чином, у коді вище функції f smart_g у підсумку виявляться оптимізованими, а naive_g — ні.

Пошук циклів for
Декоратор шукає в байт-код функції стандартні цикли for, при цьому цикли while і цикли for генераторних і списковых виразів ігноруються. Вкладені цикли поки не підтримуються (оптимізується тільки самий внутрішній цикл). Коректно обробляються конструкції for-else.

типи
Декоратор не може оптимізувати цикл незалежно від того, які типи змінних використовуються в ньому. Справа в тому, що, наприклад, Python дозволяє визначити тип, який при кожному збільшенні записує рядок у файл. В результаті застосування оптимізації кількість зроблених у функції множень могло б змінитися. З-за цього кількість рядків у файлі стало б іншим і оптимізація б зламала програму.

Крім того, при операціях з матрицями змінні складаються і множаться неявним чином, бо типи змінних можуть «перемішуватись». Якщо одна з констант або змінних мала б тип float, ті змінні, які повинні були б після виконання коду мати тип int, могли б теж отримати тип float (так як додавання int float повертає float). Така поведінка може викликати помилки в програмі і також неприйнятно.

Щоб уникнути небажаних побічних ефектів, декоратор оптимізує цикл, тільки якщо всі константи і змінні, використовувані в ньому, мають допустимий тип. Спочатку допустимими типами є int long, а також успадковані від них типи. Якщо одна з констант або змінних має тип long, ті змінні, які повинні були б після виконання коду мати тип int, теж можуть отримати тип long. Однак, так як int long в Python достатньою мірою взаємозамінні, це не повинно призводити до помилок.

У разі, якщо ви хочете змінити набір допустимих типів (наприклад, щоб додати підтримку float), ви повинні передати кортеж з потрібних типів у параметрі types. Типи, що входять в цей кортеж чи успадковані від типів, що входять в цей кортеж, будуть вважатися допустимими. На ділі перевірка того, що яке-небудь значення value має допустимий тип, буде здійснюватися за допомогою виразу isinstance(value, types).

Умови оптимізації циклу
Кожен знайдений цикл повинен задовольняти ряду умов. Частина з них перевіряється вже при застосуванні декоратора:
  1. Тіло циклу повинно складатися тільки з інструкцій присвоювання, унарных та бінарних операцій, які можуть бути скомпоновані в складні вирази. Воно не може містити умов, викликів інших функцій, операторів return yield і т. д..
  2. Від операндів може вимагатися умова передбачуваності: на кожній ітерації циклу їх значення повинно бути одним і тим же, причому воно не повинно залежати від результатів будь-яких обчислень на попередній ітерації. При цьому:
    • Всі операнди додавання і віднімання, а також операнд плюс мінуса можуть бути непередбачуваними.
    • Хоча б один операнд множення повинен бути передбачуваний (аналогічно тому, що в оригінальному інтерпретаторі підтримувалося лише множення на константу).
    • Всі операнди зведення в ступінь, операцій ділення і взяття залишку і побітових операцій повинні бути передбачувані.
  3. Всі константи, що використовуються в циклі, повинні мати дійсний тип.
Якщо ці умови виконуються, перед циклом встановлюється «пастка», яка перевірить іншу частину умов, при цьому оригінальний байт-код циклу не видаляється. Так як в Python використовується динамічна типізація, такі умови можуть бути перевірені тільки безпосередньо перед запуском циклу:
  1. Об'єкт, по якому проходить цикл, повинен мати стандартний тип xrange або його аналог з цієї бібліотеки cpmoptimize.xrange. При цьому повільна функція range, яка повертає список, не підтримується.
  2. Значення всіх змінних, що використовуються в циклі, мають допустимий тип.
Якщо «пастка» уклала, що оптимізація прийнятна, будуть розраховані необхідні матриці, а потім значення використовуваних змінних змінюються на нові. Якщо оптимізацію виконати не можна, буде запущений оригінальний байт-код циклу.

Виразу і винос коду за цикл
Незважаючи на те, що описуваний метод не підтримує операції зведення в ступінь і «побітового І», наступний код буде оптимізовано:
@cpmoptimize()
def f(n, k):
res = 0
for i in xrange(n):
m = 3
res += ((k ** m) & 676) + i
return res

При аналізі байт-коду декоратор зробить висновок, що значення змінних k m у вираженні (k ** m) & 676 не залежать від того, на якій ітерації циклу вони використовуються, а значить не змінюється і значення всього виразу. Обчислювати його на кожній ітерації не потрібно, достатньо обчислити значення один раз. Тому відповідні інструкції байт-коду можна винести і виконувати їх безпосередньо перед запуском циклу, підставляючи в циклі вже готове значення. Код ніби перетворений до наступного:
@cpmoptimize()
def f(n, k):
res = 0
_const1 = (k ** m) & 676
for i in xrange(n):
m = 3
res += _const1 + i
return res

Така техніка відома винесення інваріантного коду за цикл (loop-invariant code motion). Зверніть увагу, що винесені значення обчислюються кожен раз при запуску функції, так як вони можуть залежати від мінливих глобальних змінних або параметрів функції (_const1 у прикладі залежить від параметру k). Отриманий код тепер легко оптимізувати за допомогою матриць.

Саме на цьому етапі виконується описана вище перевірка передбачуваності величин. Наприклад, якщо б один з операндів «побітового І» виявився непередбачуваним, цю операцію вже не можна було б винести за цикл і оптимізація не могла б бути застосована.

Декоратор також частково підтримує множинні присвоювання. Якщо в них мало елементів, Python створює підтримуваний декоратором байт-код без використання кортежів:
a, b = b, a + b

Поріг iters_limit
На графіках вище ви могли помітити, що при малій кількості ітерацій оптимізований цикл може працювати повільніше звичайного, так як в такому разі все одно потрібен певний час на конструювання матриць і перевірку типів. У випадках, коли необхідно, щоб функція працювала як можна швидше і при маленькій кількості ітерацій, можна явно задати поріг параметром iters_limit. Тоді «пастка» перед запуском оптимізації перевірить, скільки ітерацій належить виконати циклу, і скасує оптимізацію, якщо це число не перевищує заданий поріг.

Спочатку поріг встановлений в 5000 ітерацій. Його не можна встановити нижче, ніж в 2 ітерації.

Зрозуміло, що найбільш вигідним значенням порога є точка перетину на графіку ліній, відповідних часу роботи оптимізованого і вихідного варіантів функції. Якщо встановити поріг саме таким, функція зможе вибирати найбільш швидкий у даному випадку алгоритм (оптимізований або вихідний):


Прапор strict
У деяких випадках оптимізація повинна бути обов'язкова застосована. Так, якщо в циклі ітерацій, без оптимізації програма просто зависне. На цей випадок передбачений параметр strict. Спочатку його значення дорівнює False, але якщо його встановити в True, то у випадку, коли будь-який із стандартних циклів for не був оптимізований, буде порушено виняток.

Якщо те, що оптимізація незастосовна, було виявлено на етапі застосування декоратора, відразу буде порушено виняток cpmoptimize.recompiler.Recompilationerror. У прикладі в циклі множаться дві непередбачувані змінні:
>>> from cpmoptimize import cpmoptimize
>>>
>>> @cpmoptimize(strict=True)
... def f(n, k):
... res = 0
... for i in xrange(n):
... res += i * res
... return res
... 
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
File "cpmoptimize/__init__.py", line 100, in upgrade_func
index += analyze_loop(settings, code, index) + 1
File "cpmoptimize/__init__.py", line 59, in analyze_loop
raise err
cpmoptimize.recompiler.Recompileerror: Multiplication of two unpredictable values is unsupported

Якщо те, що оптимізація незастосовна, було виявлено перед виконанням циклу (тобто якщо виявилося, що типи значень ітератора або змінних не підтримуються), буде порушено виняток TypeError:
>>> from cpmoptimize import cpmoptimize
>>>
>>> @cpmoptimize(strict=True)
... def f(iterable):
... res = 0
... for elem in iterable:
... res += elem
... return res
... 
>>> f(xrange(30))
435
>>> f(range(30))
Traceback (most recent call last):
File "<stdin>", line 1, in < module>
File "<stdin>", line 4, in f
File "cpmoptimize/hook.py", line 170, in exec_loop
raise err
TypeError: Iterator in optimized loops must have type "xrange" instead of <type 'list'>

Опції додаткової оптимізації
Два прапора opt_min_rows opt_clear_stack відповідають за використання додаткових методів оптимізації при конструюванні матриць. Спочатку вони включені, можливість їх відключення присутній тільки в демонстраційних цілях (завдяки їй можна порівнювати ефективність цих методів).

При виконанні оптимізованого коду більшу частину часу займає множення довгих чисел в деяких клітинках генеруються матриць. Порівняно з цим трудомістким процесом час, що витрачається на перемножування всіх інших осередків, пренебрежимо мало.

В процесі перекомпіляції виразів декоратор створює проміжні, віртуальні змінні, що відповідають за позиції стека інтерпретатора. Після складних обчислень у них можуть залишатися довгі числа, які вже зберігаються в якихось інших, реальних змінних. Зберігати ці значення вдруге нам вже не потрібно, однак вони залишаються в клітинках матриці і суттєво гальмують роботу програми, так як при множенні матриць ми змушені зайвий раз множити ці довгі числа. Опція opt_clear_stack відповідає за очищення таких змінних: якщо по закінченні їх використання присвоювати їм нуль, довгі значення в них зникнуть.

Ця опція особливо ефективна, коли програма оперує дуже великими числами. Виключення зайвих перемножений таких чисел дозволяє прискорити програму більш, ніж в два рази.

Опція opt_min_rows включає мінімізацію розміру квадратних матриць, які ми перемножуємо. З матриць виключаються ряди, відповідні невживаним і передбачуваним змінним. Якщо не використовується сама змінна циклу, виключаються і ряди, що відповідають за підтримання її правильного значення. Щоб не порушити роботу програми, після циклу всім цим змінним будуть присвоєні правильні кінцеві значення. Крім того, в оригінальній статті вектор змінних доповнювався елементом, рівним одиниці. Якщо ряд, що відповідає цьому елементу, виявиться невживаним, він теж буде виключений.

Ця опція може дещо прискорити програму для не дуже великих n, коли числа ще не стали дуже довгими і розміри матриці вносять істотний вклад під час роботи програми.

Якщо застосовувати обидві опції одночасно, то віртуальні змінні починають мати передбачуване (нульове значення, і opt_min_rows працює ще ефективніше. Іншими словами, ефективність обох опцій разом більше, ніж ефективність кожної з них окремо.

Графік нижче демонструє час роботи програми для обчислення чисел Фібоначчі при відключенні тих чи інших опцій (тут "-m" — програма з відключеною opt_min_rows, "-c" — програма з відключеною opt_clear_stack, "-mc" — програма, де відключені обидві опції відразу):


Що ще можна реалізувати?

Зміна набору операцій

Будемо говорити, що наш метод підтримує кілька операцій , якщо:
  • Ми можемо виконувати операцію для двох змінних або змінної та константи;
  • Ми можемо виконувати операцію для змінної і константи.
Нам вже відомо, що метод підтримує кілька операцій . Дійсно:
  • Ми можемо складати дві змінних або змінної та константи;
  • Ми можемо множити змінну константу.
Саме ці операції на даний момент реалізовані в оптимизирующем декораторе. Однак, виявляється, що описуваний метод підтримує й інші пари операцій, у тому числі (пару з множення і операції зведення в ступінь).

Наприклад, наше завдання може полягати в тому, щоб знайти n-е число в послідовності, що задається рекуррентным співвідношенням:


Якби наш декоратор підтримував пару операцій , ми могли б множити змінну на іншу змінну (але вже не могли б складати змінні). У такому випадку таке тривіальне рішення цієї задачі могло б бути прискорене декоратором:
def f(n):
a = 1
b = 1
for i in xrange(n):
a, b = b, a * b
return a

Можна довести, що наш метод також підтримує пари операцій (тут and — побітове І, or — побітове АБО). У разі позитивних чисел можна працювати і з парами операцій .

Для реалізації підтримки операцій можна, наприклад, оперувати не значеннями змінних, а логарифмами цих значень. Тоді множення змінних заміниться складанням логарифмів, а зведення змінної в константну ступінь — множенням логарифма на константу. Таким чином ми зведемо задачу до вже реалізованому нагоди з операціями .

Пояснення того, як реалізувати підтримку решти зазначених пар операцій, містить деяку кількість математичеких викладок і гідно окремої статті. На даний момент лише варто згадати, що пари операції в певній мірі взаємозамінні.

Вкладені цикли

Доопрацювавши алгоритм аналізу циклів в байт-код, можна реалізувати підтримку вкладених циклів, щоб оптимізувати код, подібний до такого:
def f():
res = 0
for i in xrange(10 ** 50):
for j in xrange(10 ** 100):
res += i * 2 + j
return res

Передбачувані умови

В наступному коді умова в тілі циклу є передбачуваним. Можна ще перед запуском циклу з'ясувати, істинно воно, і прибрати невыполняющуюся гілку коду. Одержаний після цього код можна буде оптимізувати:
def f(mode):
res = 0
for i in xrange(10 ** 50):
if mode == 1:
res += 3
else:
res += 5
return res

Висновки
Інтерпретатор Python, взагалі кажучи, створює передбачуваний байт-код, який майже в точності відповідає тому вихідного коду, який ви написали. Стандартно він не виробляє ні вбудовування функцій, ні розгортання циклів, ні яких-небудь інших оптимізацій, що вимагають аналізу поведінки програми. Тільки з версії 2.6 CPython навчився згортати константные арифметичні вирази, але і ця можливість працює не завжди ефективно.

У цій ситуації є кілька причин. По-перше, аналіз коду в загальному випадку в Python скрутний, адже простежити за типами даних можна тільки під час виконання програми (що ми і робимо в нашому випадку). По-друге, оптимізації, як правило, все одно не дозволяють Python досягти швидкості чисто компилируемых мов, тому в разі, коли програмі потрібно працювати дуже швидко, пропонується просто писати її на більш низкоуровневом мовою.

Тим не менш, Python — гнучкий мову, що дозволяє при необхідності реалізувати багато методи оптимізації самостійно без втручання в інтерпретатор. Дана бібліотека, а також інші проекти, перераховані нижче, це добре ілюструють цю можливість.

Дивіться також
Нижче я наведу посилання на кілька інших цікавих проектів щодо прискорення виконання програм на Python:
  1. PyPy — альтернативний інтерпретатор Python з підтримкою JIT-компіляції, що дозволяє, як правило, виконувати програми на Python істотно швидше. Сам PyPy написаний на мові RPython, для якого спеціально розроблений транслятор в код на мові C.
  2. Pyston — новий альтернативний інтерпретатор Python, транслює код в проміжне представлення LLVM, з якого він може бути оптимізовано засобами LLVM і виконаний з використанням JIT-компіляції.
  3. Nuitka — інтерпретатор Python. На відміну від пакувальника py2exe, який створює *.exe-файл, що містить скрипт, інтерпретатор і необхідні бібліотеки, Nuitka дійсно компілює програми на Python у готові виконувані файли.
  4. WPython — модифікований інтерпретатор CPython 2.6.4 з більш ефективною моделлю байт-коду, розумною системою згортання констант та переробленої віртуальною машиною.
  5. astoptimizer — бібліотека, застосовує відомі методи оптимізації перед компіляцією в байт-код шляхом аналізу і зміни абстрактного синтаксичного дерева.
  6. promise — бібліотека, що оптимізує байт-код, покладаючись на так звані «обіцянки». Якщо програміст обіцяє не робити певного роду операцій в своєму коді, стає можливим застосувати ті оптимізації, які в загальному випадку застосувати не можна було.
  7. foldy.py — бібліотека, аналізує байт-код і виконує згортання констант (constant folding), тобто заміну константных виразів на їх значення, а також видалення непотрібних функцій.
  8. Декоратор, аналізує байт-код і виконує вбудовування констант (constant binding), тобто замінює пошук значення сталої глобальної змінної за її імені на безпосередню завантаження відповідної константи.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.