В прошлом занимало много сил, чтобы добавить оптимизацию хвостового вызова (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