In this article we will look at the optimization in a virtual machine in PHP 7 (Zend virtual machine) in detail. First, let's touch on the theory of springboards function calls, and then find out how they work in PHP 7. If you want to fully understand everything, then it is better to have a good understanding of the work of the Zend virtual machine. For starters, you can read how the VM is arranged in PHP 5, and here we will talk about the PHP 7 VM. Although it has been reworked, it works in much the same way as PHP 7. Therefore, if you figure it out in the PHP 5 VM, you will understand with VM PHP 7 will not be any difficulty.

It's all about recursion

If you have never heard of springboards, you probably didn’t touch languages ​​like Haskell or Scala. The function call trampoline is a trick that is usually talked about in depth programming training courses. The task of the springboard is to prevent the recursiveness of function calls. This is a theoretical basis. If you do not know what recursion is, then first ask. There is nothing difficult in it.

There are many ways to implement the springboard mechanism in applications. Let's start with a simple example:
')

function factorial($n) { if ($n == 1) { return $n; } return $n * factorial($n-1); } 

The easiest way to understand recursion is in the well-known factorial function. She has very few instructions, and above all - she calls herself.

As you know, with every function call a lot of things happen. At the bottom level, the compiler prepares for the call using the function calling convention . In fact, the compiler first passes the arguments and the return address to the stack, and then generates a CALL opcode that translates the processor to the first instruction of the function body. When it is completed, the RETURN opcode is used (if it is not in the function body, it is generated by the compiler), telling the processor to get rid of the stack of arguments (the stack pointer is reset) and return to the return address.

The problem with this model is that the stack is a part of memory, finite and small in size. In Linux, 8 MB ( ulimit -a ) is usually allocated for the stack. Recursive functions very actively use the stack, because each record at the recursive level creates a new frame in the stack. If you get too carried away, you can fill the entire stack. In this case, the kernel usually issues a SIGBUS signal to the processor and terminates the stack if it does not fall before this (for example, if you use alloca() ).

Although the place in the stack rarely ends (except for bugs in the program), in addition to recursive functions, you can harm the creation of the stack and the subsequent destruction (when the function returns) of the call frame. This eats away some processor cycles (for stack-oriented instructions like mov , pop , push and call ) and always implies accessing main memory. And - it is slow. If your program can work with a single function, without calling children, it will act faster: the processor does not need to infinitely create and delete stacks, moving blocks of memory that the program does not use directly, they are simply part of the architecture. Today, processors usually use registers to store stack arguments or return addresses (for example, LP64 on Linux), but still avoid recursion, at least its deepest levels.

Prevent recursion

There are several ways to prevent recursion when calling functions. We will use PHP to get familiar with simple ways. A more traditional way will be studied using the springboard function, and then, using the example of the PHP source code, we consider the operation of this mechanism added to the core of PHP 7.

Tail call functions and loops

Recursion is a type of the cycle “until XXX, I call myself”. Consequently, the recursive function can be rewritten using a loop (sometimes even a few) without any call to itself. However, keep in mind that this is not an easy task, it all depends on the function itself: how many times and how it calls itself.

Fortunately, one can easily “de-recurse” the factorial function. To do this, we will use a method called tail-call transformation. You can unleash the factorial function by turning it into a recursive tail call function and applying a certain rule. Let's do the transformation first:

 function tail_factorial($n, $acc = 1) { if ($n == 1) { return $acc; } return tail_factorial($n-1, $n * $acc); } 

Here we used the so-called battery. At the end we have to get the tail call function. Let me remind you: this is the name of the function, which, when it comes to returning itself, does so without performing any other operations. That is, the return expression passes only a recursive function, without additional operations. For example, re-entry with a single instruction stream (single-instruction reentrant). Thus, the compiler optimizes the last call: the function simply returns itself, therefore, the creation of the stack is simplified by reusing the current stack frame instead of creating a new one. We can now also convert this tail call function, the body of which is simply a loop. Instead of calling back a function with modified arguments, you need to jump again to the beginning of the function (as a recursive call would have done), but at the same time changing the arguments so that the next cycle is executed with the correct values ​​of the arguments (as the recursive function does). We get:

 function unrolled_factorial($n) { $acc = 1; while ($n > 1) { $acc *= $n--; } return $acc; } 

This function does the same thing as the original factorial() , but no longer calls itself. During runtime, this is much more productive than a recursive alternative.

We could also use the goto branch:

 function goto_factorial($n) { $acc = 1; f: if ($n == 1) { return $acc; } $acc *= $n--; goto f; } 

Again, no recursion.

Try running factorial() with a huge number: you’re running out of a stack, and you’ll run into the engine’s memory limit (since the stack frames in the virtual machine are placed on the heap). If you disable the limit ( memory_limit ), then PHP will crash, because neither it nor the Zend virtual machine has protection against infinite recursion. Consequently, the process will collapse. Now try running with the same argument unrolled_factorial() or even goto_factorial() . The system will not fall. It may not run too fast, but it will not fall, and the place on the stack (located on the PHP heap) will not end. Although the speed of execution will be much higher than in the case of the recursive function.

Tailing Springboard Control Functions

Sometimes it happens that the function is not easy to de-cycle. Factorial is simple, but some others are much more complicated. For example, functions that call themselves in different places, in different conditions, and so on (like a simple implementation of bsearch() ).

In such cases, a springboard may be needed to curb the recursion. It will be necessary to rewrite the basic recursive function (as with de-recursion), but this time it can call itself. We simply disguise these challenges by fulfilling them with a springboard, and not directly. Thus, recursion will unwind if there is a flow of control (springboard), providing control over each call to our function. You no longer have to wrestle with how to de-recurse a complex function: just wrap it and run it through a control code called a springboard.

Let's look at an example of using this concept in PHP. The idea is to transform our function so that the code that calls it (caller) can determine when it enters recursion and when it exits. If you apply this to the most recursive call, then the springboard will be called by him and will manage his stack. If he returns the result, the springboard must notice it and stop.

Like this:

 function trampo_factorial($n, $acc = 1) { if ($n == 1) { return $acc; } return function() use ($n, $acc) { return trampo_factorial($n-1, $n * $acc); }; } 

Here the function still calls itself. However, it does not do this directly, but wraps the recursive call into a closure. After all, now we want to run the recursive function not directly, but through a springboard. When he sees that the closure has returned, he starts the function. If not closure, returns the function.

 function trampoline(callable $c, ...$args) { while (is_callable($c)) { $c = $c(...$args); } return $c; } 

Is done. Use in a similar way:

echo trampoline('trampo_factorial', 42);

A springboard is a normal solution to the recursion problem. If you cannot refactor a function to exclude recursive calls, then convert it to a tail call function that can be run through the springboard. Of course, springboards work only with tail call functions, otherwise.

When using the springboard, the functions called are run as many times as necessary, while they are not allowed to call themselves recursively. Springboard acts as a caller. We solved the problem of recursion in a much more versatile way that can be applied to any recursive function.

Here I used PHP only to explain the essence of the idea to you (I think you often come across PHP as you read these lines). But I do not recommend creating springboards in this language. PHP is a high-level language, and such constructs are not required in daily work. You may not often need recursive functions, and not so lightweight is a loop with the is_callable() call inside.

Nevertheless, let's delve into the PHP engine and see how springboards are implemented to prevent stack recursion in the main dispatch loop (dispatch loop) of the PHP virtual machine.

Recursion in Zend virtual machine

I hope you have not forgotten what a dispatch loop is ?

Let me refresh it in your memory. All virtual machines are built on several common ideas, among which there is a scheduling cycle. An infinite loop opline , and each iteration executes ( handler() ) one instruction ( opline ) of the virtual machine. A lot of things can happen within this instruction, but at the end there is always a command for the loop, usually a command for moving to the next iteration (goto next). There may also be a return command from an infinite loop or a transition command to this operation.

By default, the engine's virtual machine dispatch loop is stored in the execute_ex() function. Here is an example for PHP 7 with some optimizations for my computer (IP and FP registers are used):

 #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"); } 

Notice the while(1) structure. What about recursion? What's the matter?

It's simple. You have started a while(1) as part of the execute_ex() function. What happens if a single instruction ( opline->handler() ) starts execute_ex() ? Recursion will occur. This is bad. As usual: yes, if it is multi-level.

When does execute_ex() call execute_ex() ? Here I will not go too deep into the virtual machine engine, because you can miss a lot of important information. For simplicity, we assume that this PHP function call calls execute_ex() .

Each time you call a PHP function, it creates a new stack frame at the C language level and starts a new version of the dispatch loop, reentering the new execute_ex() call with new instructions for execution. When this loop appears, the PHP function call is completed, which leads to the return procedure in the code. Consequently, the current loop of the current frame on the stack ends with the return of the previous one. Just keep in mind that this happens only in the case of PHP functions in user space. The reason is that user-defined PHP functions are opcodes that, after starting, run in a loop. But internal PHP functions (developed in C and located in the kernel or in extensions) do not need to execute opcodes. These are instructions on pure C, therefore, they do not create another dispatch cycle and another frame.

Usage __call ()

Now I will explain how to use __call() . This is a PHP function from user space. As with any user-defined function, its execution leads to a new execute_ex() call. But the fact is that __call() can be called multiple times, creating many frames. Every time an unknown method is called in the context of an object using __call() defined in its class.

In PHP 7, the engine was optimized using additional springboard control (mastering) calls to __call() , as well as using prevention of recursive calls to execute_ex() in the case of __call() .

__call() in PHP 5.6:



Here are three calls to execute_ex() . This is taken from a PHP script that calls an unknown method in the context of an object, which in turn calls an unknown method in the context of another object (in both cases, the classes contain __call() ). So the first execute_ex() is the execution of the main script (position 6 in the call stack), and at the top of the list we see the other two execute_ex() .

Now run the same script in PHP 7:



The difference is obvious: the stack frame is much thinner, and we have only one call to execute_ex() , that is, one dispatch cycle that controls all the instructions, including __call() calls.

Turning __ call () calls to springboard calls

In PHP 5, we called execute_ex() in the context of __call() . That is, we have prepared a new dispatch loop to execute the currently requested __call() opcodes.

Let the method called, for example, fooBarDontExist() be executed. We need to put in memory a number of structures and perform a classic function call from user space. Something like this (simplified):

 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); } 

Making this call requires a lot of work. Therefore, we often hear “try to avoid __call() for the sake of better performance” (and for a number of other reasons). It really is.

Now about PHP 7. Remember the theory of springboard? Here everything is about the same. We need to avoid recursive calls to execute_ex() . To do this, we derecurs the procedure, remaining in the same context as execute_ex() , and also redirecting (rebranch) it to its beginning, changing the necessary arguments. Let's look again at 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"); } 

So, to prevent recursive calls, we need to change at least the opline and execute_data variables (contains the following opcode, and opline is the “current” opcode to execute). When we meet __call() , then:

1. opline and execute_data .
2. Making a return.
3. Go back to the current dispatch cycle.
4. We continue its implementation for our newly modified new opcodes.
5. And as a result, we force him to return to the original position (therefore, we have orig_opline and orig_execute_data ; the virtual machine manager must always remember where it came from so that it can go (the branch) to wherever it goes).

This is what PHP 7 does a new opcode ZEND_CALL_TRAMPOLINE . It is used wherever __call() calls should be made. Let's look at the simplified version:

 #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(); } /* ... */ 

You can see that the variables execute_data and opline effectively modified using the macro ZEND_VM_ENTER() . The following execute_data prepared in the call variable, and their binding (bind) is performed by the i_init_func_execute_data() function. Next, using ZEND_VM_ENTER() , a new iteration of the dispatching cycle is performed, which switches the variables to the next cycle, and they must go into it with a “return” (the current cycle).

The circle is closed, it's all over.

How to get back to the main loop now? This is done in the opcode ZEND_RETURN , which completes any user-defined function.

 #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(); } /* ... */ 

As you can see, when returning from a call to a user-defined function, we use ZEND_RETURN , which replaces the next ones in the queue to execute the instructions from the previous ones from the previous call, prev_execute_data . Then it loads the opline and returns to the main dispatch loop.

Conclusion

We considered the theory underlying the unroll of recursive function calls. You can fix any recursive calls, but this can be very difficult. A universal solution is the development of a springboard: a system that controls the launch of each stage of a recursive function, not allowing it to call itself and, therefore, preventing it from generating stack frames uncontrollably. The “springboard” code is located in the dispatcher and controls it in order to prevent recursion.

We also looked at the general implementation in PHP and studied the implementation of springboards in the new Zend 3 engine, which is part of PHP 7. No longer be afraid to call __call() call __call() , they work faster than in PHP 5. They do not create new frame stacks (for C-level), this is one of the improvements in the PHP 7 engine.