качество и надёжность с 2008 года

8 (800) 200-25-11

Техническая поддержка support@komtet.ru —

круглосуточно и без выходных дней

load-whois

Онлайн-касса

для интернет-магазина

Подключите ваш интернет-магазин

к онлайн-кассе в соответствии с 54-ФЗ

 
Главная Техническая библиотека Языки программирования Python Оптимизация хвостовой рекурсии Python с помощью модуля byteplay

Оптимизация хвостовой рекурсии Python с помощью модуля byteplay

Автор: timw

Я хотел бы обратить Ваше внимание на то, что эти данные не предназначены для рабочего использования, а только для ознакомления. Когда я посмотрел на структуру байткода Python (python’s bytecode), то подумал, что другим могло бы быть интересно это прочесть.

В прошлом занимало много сил, чтобы добавить оптимизацию хвостового вызова (tail-call optimisation) в python - обычно в кросс-интерпретаторе python (cross-interpreter python), но пока я "игрался" с модулем byteplay, то пришел к мысли попытаться написать функцию, которая перекомпилирует функцию и вставляет оптимизацию хвостового вызова (tail-call optimisation).

Мой метод является базовым, и конвертирует  хвостовые рекурсивные вызовы (tail-recursive calls) в (чистой) функции в команды перехода.

 

Вот, например, (очень простая) функция:

def f(x):
    """pointless sample function"""
    return f(x)

Начинается с байткода таким образом:

1 LOAD_GLOBAL          f
2 LOAD_FAST            x
3 CALL_FUNCTION        1
4 RETURN_VALUE

Код операции (opcode) CALL_FUNCTION  может быть заменен с помощью JUMP_ABSOLUTE на первый код операции:

2 LOAD_FAST            x
3 STORE_FAST           x
4 JUMP_ABSOLUTE        to 2
5 RETURN_VALUE

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

Причина, по которой Вы  захотели бы сделать такую замену, это:

1) Избавить интерпретатор от

a) Необходимости создания нового окружения (local scope) при каждом вызове новой функции

b) Необходимости выполнения многих операций RETURN_VALUE, возвращаемых из внутренних вызовов функции

2) Уменьшить размер стека

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

Я протестировал это на различных рекурсивных функциях, и вот - результаты:

********************
Testing: gcd - 'greatest common devisor - Euclid'
( 59.70% speed increase )
********************
Testing: gcd_dijkstra - 'greatest common devisor - Dijkstra'
( 147.89% speed increase )
********************
Testing: power - 'raise to the power - no square \
                                         optimisation (lisp-like)'
( 95.60% speed increase )
********************
Testing: quickpower - 'raise to the power - \
                                         with square optimisation'
( 2.79% speed increase )
********************
Testing: fact - 'Factorial (lisp-like)'
( 115.74% speed increase )
********************
Testing: binary_search - 'Simple binary search or ordered list'
( 25.95% speed increase )
********************
Testing: f - 'pointless sample function'
( 165.97% speed increase )
********************
Testing: ackermann - 'Ackermann-Peter function \
                                (doesn't get properly optimised)'
( 1.94% speed increase )
http://www.teamrubber.com/blog/author/timw/

Вот перечень функций, которые были протестированы:

протестированные функции

Хотя, я думаю, здесь можно было сделать намного больше - например, если переменные не изменяются, тогда их не надо снова сохранять.

Оригинал статьи на www.teamrubber.com

Перевод ООО «Комтет» komtet.ru

Клиентам — домены в подарок!
Бесплатный тест виртуального хостинга
Перенос сайта — бесплатно
Все акции
На сайте КОМТЕТ используются cookie-файлы, данные о IP-адресе и местоположении посетителей. Если, прочитав это сообщение, вы остаетесь на нашем сайте, это означает, что вы не возражаете против использования этих технологий.