[Перевод] Трамплин вызова магических функций в PHP 7
В этой статье мы подробно рассмотрим оптимизацию в виртуальной машинe в PHP 7 (виртуальной машине Zend). Сначала коснёмся теории трамплинов вызовов функций, а затем узнаем, как они работают в PHP 7. Если вы хотите полностью во всём разобраться, то лучше иметь хорошее представление о работе виртуальной машины Zend. Для начала можете почитать, как устроена ВМ в PHP 5, а здесь мы поговорим о ВМ PHP 7. Хотя она и была переработана, но действует практически так же, как и в PHP 7. Поэтому если вы разберётесь в ВМ PHP 5, то разобраться с ВМ PHP 7 не составит никакого труда.
Если вы никогда не слышали о трамплинах, то наверняка и не прикасались к языкам вроде Haskell или Scala. Трамплины вызовов функций — это трюк, о котором обычно рассказывают на курсах углублённого обучения программированию. Задача трамплина — предотвратить рекурсивность вызовов функций. Это теоретическая основа. Если вы не знаете, что такое рекурсия, то сначала полюбопытствуйте. В ней нет ничего сложного.
Существует много способов внедрения механизма трамплинов в приложениях. Начнём с простого примера:
function factorial($n)
{
if ($n == 1) {
return $n;
}
return $n * factorial($n-1);
}
Проще всего понять рекурсию на всем известной функции factorial. У неё очень мало инструкций, и прежде всего — она вызывает саму себя.
Как вы знаете, при каждом вызове функции происходит много вещей. На нижнем уровне компилятор готовится к вызову, пользуясь соглашением о вызове функции. По сути, компилятор сначала передаёт в стек аргументы и адрес возврата, а затем генерирует опкод CALL, переводящий процессор на первую инструкцию тела функции. Когда она будет завершена, используется опкод RETURN (если его нет в теле функции, то он генерируется компилятором), говорящий процессору избавиться от стека аргументов (сбрасывается указатель стека) и вернуться к адресу возврата.
Проблема этой модели заключается в том, что стек — часть памяти, конечная и небольшая по размеру. В Linux под стек обычно выделяют 8 Кб (ulimit -a). Рекурсивные функции очень активно используют стек, потому что каждая запись на рекурсивном уровне создаёт в стеке новый фрейм. Если слишком увлечься, то можно заполнить весь стек. В этом случае ядро обычно выдаёт процессору сигнал SIGBUS и завершает стек, если до этого он сам не упадёт (например, если вы используете alloca()).
Хотя место в стеке заканчивается редко (если не считать багов в программе), помимо рекурсивных функций вам может навредить создание в стеке и последующее уничтожение (при возврате функции) фрейма вызова. Это отъедает часть циклов процессора (для ориентированных на стек инструкций вроде mov, pop, push и call) и всегда подразумевает обращения к основной памяти. И — это медленно. Если ваша программа может работать с одиночной функцией, без вызова дочерних, то она будет действовать быстрее: процессору не нужно бесконечно создавать и удалять стеки, перемещая блоки памяти, которые программа не использует напрямую, они просто являются частью архитектуры. Сегодня процессоры обычно применяют регистры для хранения аргументов стека или адреса возврата (например, LP64 в Linux), но всё равно избегайте рекурсии, хотя бы её самых глубоких уровней.
Предотвратить рекурсию при вызове функций можно несколькими способами. Для знакомства с простыми способами мы воспользуемся PHP. Более традиционный способ изучим с помощью функции-трамплина, а затем на примере исходного кода PHP рассмотрим работу этого механизма, добавленного в сердцевину PHP 7.
Функции хвостового вызова и циклы
Рекурсия — это разновидность цикла «пока ХХХ, вызываю самого себя». Следовательно, рекурсивную функцию можно переписать с помощью цикла (иногда даже нескольких) без какого-либо вызова самой себя. Однако имейте в виду, что это непростая задача, всё зависит от самой функции: сколько раз и как она себя вызывает.
К счастью, можно легко «дерекурсировать» факториальную функцию. Для этого мы воспользуемся способом, который называется преобразованием хвостового вызова (tail-call transformation). Можно раскрутить (unroll) факториальную функцию, превратив её в рекурсивную функцию хвостового вызова и применив некое правило. Давайте сначала выполним превращение:
function tail_factorial($n, $acc = 1)
{
if ($n == 1) {
return $acc;
}
return tail_factorial($n-1, $n * $acc);
}
Здесь мы использовали так называемый аккумулятор. В конце мы должны получить функцию хвостового вызова. Напомню: так называется функция, которая, когда дело доходит до возвращения себя, делает это без выполнения каких-либо других операций. То есть выражение возврата передаёт только рекурсивную функцию, без дополнительных операций. Например, повторный вход с одним потоком инструкций (single-instruction reentrant). Таким образом компилятор оптимизирует последний вызов: функция просто возвращает саму себя, следовательно, создание стека упрощается за счёт повторного использования текущего фрейма стека вместо создания нового. Также мы теперь можем преобразовать эту функцию хвостового вызова, тело которой представляет собой просто цикл. Вместо обратного вызова функции с изменёнными аргументами нужно прыгнуть снова к началу функции (как это сделал бы рекурсивный вызов), но при этом изменив аргументы, чтобы следующий цикл выполнялся с правильными значениями аргументов (как это делает рекурсивная функция). Получаем:
function unrolled_factorial($n)
{
$acc = 1;
while ($n > 1) {
$acc *= $n--;
}
return $acc;
}
Эта функция делает то же самое, что и оригинальная
factorial(), но больше не вызывает саму себя. В ходе runtime это получается гораздо производительнее рекурсивной альтернативы.Также мы могли бы использовать ветку goto:
function goto_factorial($n)
{
$acc = 1;
f:
if ($n == 1) {
return $acc;
}
$acc *= $n--;
goto f;
}
И снова никакой рекурсии.
Попробуйте запустить factorial() с огромным числом: у вас кончится стек, и вы упрётесь в ограничение памяти движка (поскольку фреймы стека в виртуальной машине размещены в куче (heap)). Если отключить ограничение (memory_limit), то PHP упадёт, потому что ни у него, ни у виртуальной машины Zend нет защиты от бесконечной рекурсии. Следовательно, процесс рухнет. Теперь попробуйте запустить с тем же аргументом unrolled_factorial() или даже goto_factorial(). Система не упадёт. Выполняться может не слишком быстро, но не упадёт, а место в стеке (размещённом в куче PHP) не закончится. Хотя скорость выполнения будет куда выше, чем в случае с рекурсивной функцией.
Управляющие трамплинные функции хвостового вызова
Иногда бывает так, что функцию непросто дерекурсировать. Факториальную — просто, но некоторые другие — куда сложнее. Например, функции, вызывающие себя в разных местах, в разных условиях и так далее (вроде простой реализации
bsearch()). В таких случаях, чтобы обуздать рекурсию, может понадобиться трамплин. Надо будет переписать базовую рекурсивную функцию (как при дерекурсировании), но в этот раз она может вызывать сама себя. Мы просто замаскируем эти вызовы, выполняя их с помощью трамплина, а не напрямую. Таким образом, рекурсия будет раскручиваться (unroll) при наличии потока управления (трамплина), обеспечивая контроль над каждым вызовом нашей функции. Больше не нужно ломать голову над тем, как дерекурсировать сложную функцию: просто оберните её и запускайте через управляющий код, называемый трамплином.
Давайте рассмотрим пример использования этой концепции в PHP. Идея заключается в преобразовании нашей функции, чтобы вызывающий её код (caller) мог определить, когда она входит в рекурсию, а когда выходит из неё. Если применить это к самому рекурсивному вызову, то трамплин будет вызываться им и станет управлять его стеком. Если он вернёт результат, то трамплин должен заметить это и остановить.
Вот так:
function trampo_factorial($n, $acc = 1)
{
if ($n == 1) {
return $acc;
}
return function() use ($n, $acc) { return trampo_factorial($n-1, $n * $acc); };
}
Здесь функция всё ещё вызывает себя. Однако не делает это напрямую, а оборачивает рекурсивный вызов в замыкание (closure). Ведь теперь мы хотим запускать рекурсивную функцию не напрямую, а через трамплин. Когда тот видит, что вернулось замыкание, он запускает функцию. Если не замыкание — возвращает функцию.
function trampoline(callable $c, ...$args)
{
while (is_callable($c)) { $c = $c(...$args); } return $c;
}
Готово. Используйте подобным образом:
echo trampoline('trampo_factorial', 42);
Трамплин — это нормальное решение проблемы рекурсии. Если вы не можете рефакторить функцию, чтобы исключить рекурсивные вызовы, то преобразуйте её в функцию хвостового вызова, которую можно запускать через трамплин. Конечно, трамплины работают только с функциями хвостового вызова, как же иначе.
При использовании трамплина вызываемые функции запускаются столько раз, сколько нужно, при этом им не дают вызывать себя рекурсивно. Трамплин выступает в роли вызываемого. Мы решили проблему рекурсии гораздо более универсальным способом, который может применяться к любой рекурсивной функции.
Здесь я использовал PHP только для того, чтобы объяснить вам суть идеи (полагаю, вы достаточно часто сталкиваетесь с PHP, раз читаете эти строки). Но я не рекомендую создавать трамплины в этом языке. PHP — высокоуровневый язык, и такие конструкции не требуются в повседневной работе. Вам не так часто могут быть нужны рекурсивные функции, и не таким легковесным получается цикл с вызовом is_callable() внутри.
Тем не менее давайте углубимся в движок PHP и посмотрим, как здесь реализованы трамплины для предотвращения рекурсии стека в главном цикле диспетчеризации (dispatch loop) виртуальной машины PHP.
Рекурсия в виртуальной машине ZendНадеюсь, вы не забыли, что такое цикл диспетчеризации?
Позвольте освежить это в вашей памяти. Все виртуальные машины строятся на нескольких общих идеях, среди которых есть и цикл диспетчеризации. Запускается бесконечный цикл, и в каждой его итерации выполняется (handler()) одна инструкция (opline) виртуальной машины. В рамках этой инструкции может происходить многое, но в конце всегда идёт команда циклу, обычно это команда перехода к следующей итерации (goto next). Также может быть команда возвращения из бесконечного цикла или команда перехода к этой операции.
По умолчанию цикл диспетчеризации виртуальной машины движка хранится в функции execute_ex(). Вот пример для PHP 7 с некоторыми оптимизациями для моего компьютера (использованы регистры IP и FP):
#define ZEND_VM_FP_GLOBAL_REG "%r14"
#define ZEND_VM_IP_GLOBAL_REG "%r15"
register zend_execute_data* volatile execute_data __asm__(ZEND_VM_FP_GLOBAL_REG);
register const zend_op* volatile opline __asm__(ZEND_VM_IP_GLOBAL_REG);
ZEND_API void execute_ex(zend_execute_data *ex)
{
const zend_op *orig_opline = opline;
zend_execute_data *orig_execute_data = execute_data;
execute_data = ex;
opline = execute_data->opline;
while (1) {
opline->handler();
if (UNEXPECTED(!opline)) {
execute_data = orig_execute_data;
opline = orig_opline;
return;
}
}
zend_error_noreturn(E_CORE_ERROR, "Arrived at end of main loop which shouldn't happen");
}
Обратите внимание на структуру
while(1). Что насчёт рекурсии? В чём тут дело? Всё просто. Вы запустили цикл while(1) как часть функции execute_ex(). Что случится, если одна инструкция (opline->handler()) запустит саму execute_ex()? Возникнет рекурсия. Это плохо. Как обычно: да, если она будет многоуровневой.
В каком случае execute_ex() вызывает execute_ex()? Здесь я не стану слишком углубляться в движок виртуальной машины, потому что вы можете упустить много важной информации. Для простоты будем считать, что это вызов PHP-функции вызывает execute_ex().
Каждый раз, когда вы вызываете PHP-функцию, она создаёт новый фрейм стека на уровне языка С и запускает новую версию цикла диспетчеризации, повторно входя в новый вызов execute_ex() с новыми инструкциями для выполнения. Когда появляется этот цикл, завершается вызов PHP-функции, что приводит к процедуре возврата в коде. Следовательно, завершается текущий цикл текущего фрейма в стеке с возвращением предыдущего. Только учитывайте, что это происходит только в случае с PHP-функциями в пользовательском пространстве. Причина в том, что определяемые пользователями PHP-функции представляют собой опкоды, которые после своего запуска работают в цикле. Но внутренним PHP-функциям (разработанным на С и находящимся в ядре или в расширениях) не нужно выполнять опкоды. Это инструкции на чистом С, следовательно, они не создают другой цикл диспетчеризации и другой фрейм.
Теперь я объясню, как можно использовать
__call(). Это PHP-функция из пользовательского пространства. Как и в случае с любой пользовательской функцией, её выполнение приводит к новому вызову execute_ex(). Но дело в том, что __call() может вызываться многократно, создавая много фреймов. Каждый раз, когда вызывается неизвестный метод в контексте объекта с помощью __call(), определённым в его классе.В PHP 7 движок был оптимизирован с помощью дополнительных трамплинных управляющих (mastering) вызовов __call(), а также с помощью предотвращения рекурсивных вызовов execute_ex() в случае с __call().
Стек __call() в PHP 5.6:
Здесь три вызова execute_ex(). Это взято из PHP-скрипта, который вызывает неизвестный метод в контексте объекта, который, в свою очередь, вызывает неизвестный метод в контексте другого объекта (в обоих случаях классы содержат __call()). Так что первый execute_ex() — это исполнение основного скрипта (позиция 6 в стеке вызовов), а в верху списка мы видим два остальных execute_ex().
Теперь запустим тот же скрипт в PHP 7:
Разница очевидна: фрейм стека куда тоньше, и у нас остался только один вызов execute_ex(), то есть один цикл диспетчеризации, управляющий всеми инструкциями, включая вызовы __call().
В PHP 5 мы вызывали
execute_ex() в контексте __call(). То есть мы приготовили новый цикл диспетчеризации для выполнения текущих запрошенных опкодов __call(). Пусть выполняется метод, вызванный, например, fooBarDontExist(). Нам нужно поместить в память ряд структур и выполнить классический вызов функции из пользовательского пространства. Примерно так (упрощённо):
ZEND_API void zend_std_call_user_call(INTERNAL_FUNCTION_PARAMETERS)
{
zend_internal_function *func = (zend_internal_function *)EG(current_execute_data)->function_state.function;
zval *method_name_ptr, *method_args_ptr;
zval *method_result_ptr = NULL;
zend_class_entry *ce = Z_OBJCE_P(this_ptr);
ALLOC_ZVAL(method_args_ptr);
INIT_PZVAL(method_args_ptr);
array_init_size(method_args_ptr, ZEND_NUM_ARGS());
/* ... ... */
ALLOC_ZVAL(method_name_ptr);
INIT_PZVAL(method_name_ptr);
ZVAL_STRING(method_name_ptr, func->function_name, 0); /* Копируем имя функции */
/* Делаем вызов нового цикла диспетчеризации: будет вызван execute_ex() */
zend_call_method_with_2_params(&this_ptr, ce, &ce->__call, ZEND_CALL_FUNC_NAME, &method_result_ptr, method_name_ptr, method_args_ptr);
if (method_result_ptr) {
RETVAL_ZVAL_FAST(method_result_ptr);
zval_ptr_dtor(&method_result_ptr);
}
zval_ptr_dtor(&method_args_ptr);
zval_ptr_dtor(&method_name_ptr);
efree(func);
}
Выполнение этого вызова требует большого объёма работы. Поэтому мы часто слышим «постарайтесь избегать
__call() ради повышения производительности» (и по ряду других причин). Это действительно так.Теперь про PHP 7. Помните теорию трамплина? Здесь всё примерно так же. Нам нужно избежать рекурсивных вызовов execute_ex(). Для этого дерекурсируем процедуру, оставаясь в том же контексте execute_ex(), а также перенаправив (rebranch) его в его начало, изменив необходимые аргументы. Давайте снова посмотрим на execute_ex():
ZEND_API void execute_ex(zend_execute_data *ex)
{
const zend_op *orig_opline = opline;
zend_execute_data *orig_execute_data = execute_data;
execute_data = ex;
opline = execute_data->opline;
while (1) {
opline->handler();
if (UNEXPECTED(!opline)) {
execute_data = orig_execute_data;
opline = orig_opline;
return;
}
}
zend_error_noreturn(E_CORE_ERROR, "Arrived at end of main loop which shouldn't happen");
}
Итак, для предотвращения рекурсивных вызовов нам нужно изменить как минимум переменные
opline и execute_data (содержит следующий опкод, а opline — это «текущий» опкод для выполнения). Когда мы встречаем __call(), то: - Изменяем
oplineиexecute_data. - Делаем возврат.
- Возвращаемся к текущему циклу диспетчеризации.
- Продолжаем его выполнение для наших свежеизменённых новых опкодов.
- И в результате заставляем его вернуться в исходную позицию (поэтому у нас есть
orig_oplineиorig_execute_data; диспетчер виртуальной машины должен всегда помнить, откуда пришёл, чтобы он мог перейти (branch) туда откуда угодно).
Именно это делает в PHP 7 новый опкод
ZEND_CALL_TRAMPOLINE. Он используется везде, где должны выполняться вызовы __call(). Давайте посмотрим на упрощённую версию: #define ZEND_VM_ENTER() execute_data = (executor_globals.current_execute_data); opline = ((execute_data)->opline); return
static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL ZEND_CALL_TRAMPOLINE_SPEC_HANDLER(ZEND_OPCODE_HANDLER_ARGS)
{
zend_array *args;
zend_function *fbc = EX(func);
zval *ret = EX(return_value);
uint32_t call_info = EX_CALL_INFO() & (ZEND_CALL_NESTED | ZEND_CALL_TOP | ZEND_CALL_RELEASE_THIS);
uint32_t num_args = EX_NUM_ARGS();
zend_execute_data *call;
/* ... */
SAVE_OPLINE();
call = execute_data;
execute_data = EG(current_execute_data) = EX(prev_execute_data);
/* ... */
if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) {
call->symbol_table = NULL;
i_init_func_execute_data(call, &fbc->op_array,
ret, (fbc->common.fn_flags & ZEND_ACC_STATIC) == 0);
if (EXPECTED(zend_execute_ex == execute_ex)) {
ZEND_VM_ENTER();
}
/* ... */
Можно заметить, что переменные
execute_data и opline эффективно изменены с помощью макроса ZEND_VM_ENTER(). Следующие execute_data подготовлены в переменной call, а их привязку (bind) осуществляет функция i_init_func_execute_data(). Далее с помощью ZEND_VM_ENTER() выполняется новая итерация цикла диспетчеризации, которая переключает переменные на следующий цикл, причём войти в него они должны с «возвратом» (текущего цикла).Круг замкнулся, всё закончилось.
Как теперь попасть обратно в главный цикл? Это делается в опкоде ZEND_RETURN, который завершает любую определённую пользователем функцию.
#define LOAD_NEXT_OPLINE() opline = ((execute_data)->opline) + 1
#define ZEND_VM_LEAVE() return
static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL zend_leave_helper_SPEC(ZEND_OPCODE_HANDLER_ARGS)
{
zend_execute_data *old_execute_data;
uint32_t call_info = EX_CALL_INFO();
if (EXPECTED(ZEND_CALL_KIND_EX(call_info) == ZEND_CALL_NESTED_FUNCTION)) {
zend_object *object;
i_free_compiled_variables(execute_data);
if (UNEXPECTED(EX(symbol_table) != NULL)) {
zend_clean_and_cache_symbol_table(EX(symbol_table));
}
zend_vm_stack_free_extra_args_ex(call_info, execute_data);
old_execute_data = execute_data;
execute_data = EG(current_execute_data) = EX(prev_execute_data);
/* ... */
LOAD_NEXT_OPLINE();
ZEND_VM_LEAVE();
}
/* ... */
Как видите, при возврате из вызова определённой пользователем функции мы задействуем
ZEND_RETURN, который заменяет следующие в очереди на выполнение инструкции предыдущими из предыдущего вызова prev_execute_data. Затем он подгружает opline и возвращается в главный цикл диспетчеризации.ЗаключениеМы рассмотрели теорию, лежащую в основе раскрутки (unroll) рекурсивных вызовов функций. Можно исправить любые рекурсивные вызовы, но это бывает очень трудно. Универсальное решение — разработка трамплина: системы, которая управляет запуском каждого этапа рекурсивной функции, не позволяя ей вызывать саму себя и, следовательно, мешая ей бесконтрольно плодить фреймы стека. «Трамплинный» код расположен в диспетчере и управляет им ради предотвращения рекурсии.
Также мы рассмотрели общую реализацию в PHP и изучили реализацию трамплинов в новом движке Zend 3, являющемся частью PHP 7. Больше не бойтесь вызывать __call(), они работают быстрее, чем в PHP 5. Они не создают при каждом вызове новые стеки фрейма (на С-уровне), это одно из улучшений в движке PHP 7.
