See how to optimize recursion in PHP 7!

This article takes you through recursion and introduces the optimization of recursion in PHP 7.

⒈ Recursion

  Recursion is often used in programming because of its simplicity and elegance. Recursive code is more declarative and self-describing. Recursion does not need to explain how to obtain the value like iteration does, but rather describes the final result of the function.

Take the implementation of accumulation and Fibonacci numbers as an example:

• Iterative implementation

// 累加函数
// 给定参数 n，求小于等于 n 的正整数的和
function sumBelow(int $n)
{
    if ($n <= 0) {
        return 0;
    }
    $result = 0;
    for ($i = 1; $i <= $n; $i ++) {
        $result += $i;
    }
    return $result;
}

// 斐波那契数列
// 给定参数 n，取得斐波那契数列中第 n 项的值
// 这里用数组模拟斐波那契数列，斐波那契数列第一项为 1，第二项为 2，初始化数组 $arr = [1, 1]，则斐波那契数列第 n 项的值为 $arr[n] = $arr[n-1] + $arr[n-2]
function fib(int $n)
{
    if ($n <= 0) {
        return false;
    }
    if ($n == 1) {
        return 1;
    }
    $arr = [1, 1];
    for ($i = 2, $i <= $n; $i ++) {
        $arr[$i] = $arr[$i - 1] + $arr[$i - 2];
    }
    return $arr[$n];
}

• Recursive implementation

// 累加函数
function sumBelow(int $n) 
{
    if ($n <= 1) {
        return 1;
    }
    return $n + sumBelow($n - 1);
}

// 斐波那契数列
function fib(int $n) 
{
    if ($n < 2) {
        return 1;
    }
    return fib($n - 1) + fib($n - 2);
}

 In contrast, the recursive implementation is more concise and clear, more readable, and easier to understand.

⒉ Problems with recursion

 Function calls in programs usually need to follow a certain calling convention at the bottom level. The usual process is:

• First push the parameters and return address of the function onto the stack
• Then the CPU starts executing the code in the function body
• Finally, the function execution is completed After that, the space is destroyed, and the CPU returns to the location pointed to by the return address

This process is very fast in low-level languages ​​(such as assembly), because low-level languages ​​interact directly with the CPU, and the CPU's running high speed. In Linux with x86_64 architecture, parameters are often passed directly through registers, and the stack space in the memory will be preloaded into the CPU cache, so that the CPU can access the stack space very, very quickly.

The same process is completely different in high-level languages ​​such as PHP. High-level languages ​​cannot directly interact with the CPU and need to use a virtual machine to virtualize a set of concepts such as heap and stack. At the same time, virtual machines are also needed to maintain and manage this virtualized stack.

The function calling process in high-level languages ​​is already very slow compared to low-level languages, and recursion will make this situation even worse. Taking the accumulation function in the above example as an example, ZVM needs to construct a function call stack for each sumBelow (the specific construction of the call stack has been discussed in previous articles). As n increases, it needs to There will be more and more call stacks constructed, eventually leading to memory overflow. Compared with the cumulative function, the recursion of the Fibonacci function will increase the number of call stacks in a geometric progression (because each call stack will eventually generate two new call stacks).

⒊ Use trampoline and tail call to optimize recursion

① Tail call

 Tail call refers to a function that only returns a call to itself in the end, without any other operations. Because the function returns a call to itself, the compiler can reuse the current call stack without creating a new call stack.

  Change the aforementioned accumulation function and Fibonacci function to the tail call implementation, the code is as follows

// 累加函数的尾调用方式实现
function subBelow(int $n, int $sum = 1)
{
    if ($n <= 1) {
        return $sum;
    }
    
    return subBelow($n - 1, $sum + $n);
}

// 斐波那契函数的尾调用实现
function fib(int $n, int $acc1 = 1, int $acc2 = 2) 
{
    if ($n < 2) {
        return $acc1;
    }
    
    return fib($n - 1, $acc1 + $acc2, $acc1);
}

  ② Trampoline function

  The accumulation function is relatively simple and can be easily converted into a tail call implementation. The tail call implementation of the Fibonacci function is relatively troublesome. But in practical applications, many recursions are mixed with many complex conditional judgments, and different methods of recursion are performed under different conditions. At this time, the recursive function cannot be directly converted into a tail call form, and a trampoline function is required.

The basic principle of the so-called trampoline function is to wrap the recursive function into an iterative form. Taking the cumulative function as an example, first rewrite the implementation of the cumulative function:

function trampolineSumBelow(int $n, int $sum = 1)
{
    if ($n <= 1) {
        return $sum;
    }
    
    return function() use ($n, $sum) { return trampolineSumBelow($n - 1, $sum + $n); };
}

 At the end of the function, the recursive call is not directly made, but the recursive call is packaged into a closure, and the closure function does not Execute immediately. At this time, you need to use the trampoline function. If the trampoline function finds that what is returned is a closure, then the trampoline function will continue to execute the returned closure until the trampoline function finds that what is returned is a value.

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

echo trampoline('trampolineSumBelow', 100);

The trampoline function is a more general way to solve the problem of recursive calls. In the trampoline function, the returned closure is executed iteratively, avoiding memory overflow caused by function recursion.

⒋ Optimization of recursion in ZVM

In PHP 7, recursion optimization through tail calls is mainly used in object methods. Still taking the cumulative function as an example:

class Test
{
    public function __construct(int $n)
    {
        $this->sum($n);
    }

    public function sum(int $n, int $sum = 1)
    {
        if ($n <= 1) {
            return $sum;
        }

        return $this->sum($n - 1, $sum + $n);
    }
}

$t = new Test($argv[1]);
echo memory_get_peak_usage(true), PHP_EOL;

// 经测试，在 $n <= 10000 的条件下，内存消耗的峰值恒定为 2M

 The OPCode corresponding to the above code is:

// 主函数
L0:    V2 = NEW 1 string("Test")
L1:    CHECK_FUNC_ARG 1
L2:    V3 = FETCH_DIM_FUNC_ARG CV1($argv) int(1)
L3:    SEND_FUNC_ARG V3 1
L4:    DO_FCALL
L5:    ASSIGN CV0($t) V2
L6:    INIT_FCALL 1 96 string("memory_get_peak_usage")
L7:    SEND_VAL bool(true) 1
L8:    V6 = DO_ICALL
L9:    ECHO V6
L10:   ECHO string("
")
L11:   RETURN int(1)

// 构造函数
L0:     CV0($n) = RECV 1
L1:     INIT_METHOD_CALL 1 THIS string("sum")
L2:     SEND_VAR_EX CV0($n) 1
L3:     DO_FCALL
L4:     RETURN null

// 累加函数
L0:    CV0($n) = RECV 1
L1:    CV1($sum) = RECV_INIT 2 int(1)
L2:    T2 = IS_SMALLER_OR_EQUAL CV0($n) int(1)
L3:    JMPZ T2 L5
L4:    RETURN CV1($sum)
L5:    INIT_METHOD_CALL 2 THIS string("sum")
L6:    T3 = SUB CV0($n) int(1)
L7:    SEND_VAL_EX T3 1
L8:    T4 = ADD CV1($sum) CV0($n)
L9:    SEND_VAL_EX T4 2
L10:   V5 = DO_FCALL
L11:   RETURN V5
L12:   RETURN null

 The OPCode executed when the cumulative function sum in the class is tail-called is DO_FCALL, the corresponding underlying implementation is:

# define ZEND_VM_CONTINUE() return
# define LOAD_OPLINE() opline = EX(opline)
# define ZEND_VM_ENTER() execute_data = EG(current_execute_data); LOAD_OPLINE(); ZEND_VM_INTERRUPT_CHECK(); ZEND_VM_CONTINUE()

static ZEND_OPCODE_HANDLER_RET ZEND_FASTCALL ZEND_DO_FCALL_SPEC_RETVAL_USED_HANDLER(ZEND_OPCODE_HANDLER_ARGS)
{
	USE_OPLINE
	zend_execute_data *call = EX(call);
	zend_function *fbc = call->func;
	zend_object *object;
	zval *ret;

	SAVE_OPLINE();
	EX(call) = call->prev_execute_data;
	/* 判断所调用的方法是否为抽象方法或已废弃的函数 */
	/* ... ... */

	LOAD_OPLINE();

	if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) {
		/* 所调用的方法为开发者自定义的方法 */
		ret = NULL;
		if (1) {
			ret = EX_VAR(opline->result.var);
			ZVAL_NULL(ret);
		}

		call->prev_execute_data = execute_data;
		i_init_func_execute_data(call, &fbc->op_array, ret);

		if (EXPECTED(zend_execute_ex == execute_ex)) {
			/* zend_execute_ex == execute_ex 说明方法调用的是自身，发生递归*/
			ZEND_VM_ENTER();
		} else {
			ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP);
			zend_execute_ex(call);
		}
	} else if (EXPECTED(fbc->type < ZEND_USER_FUNCTION)) {
		/* 内部方法调用 */
		/* ... ... */
	} else { /* ZEND_OVERLOADED_FUNCTION */
		/* 重载的方法 */
		/* ... ... */
	}

fcall_end:
	/* 异常判断以及相应的后续处理 */
	/* ... ... */

	zend_vm_stack_free_call_frame(call);
	/* 异常判断以及相应的后续处理 */
	/* ... ... */

	ZEND_VM_SET_OPCODE(opline + 1);
	ZEND_VM_CONTINUE();
}

  从 DO_FCALL 的底层实现可以看出，当发生方法递归调用时（zend_execute_ex == execute_ex），ZEND_VM_ENTER() 宏将 execute_data 转换为当前方法的 execute_data ，同时将 opline 又置为 execute_data 中的第一条指令，在检查完异常（ZEND_VM_INTERRUPT_CHECK()）之后，返回然后重新执行方法。

  通过蹦床函数的方式优化递归调用主要应用在对象的魔术方法 __call 、__callStatic 中。

class A
{
    private function test($n)
    {
        echo "test $n", PHP_EOL;
    }

    public function __call($method, $args)
    {
        $this->$method(...$args);
        var_export($this);
        echo PHP_EOL;
    }
}

class B extends A
{
    public function __call($method, $args)
    {
        (new parent)->$method(...$args);
        var_export($this);
        echo PHP_EOL;
    }
}

class C extends B
{
    public function __call($method, $args)
    {
        (new parent)->$method(...$args);
        var_export($this);
        echo PHP_EOL;
    }
}

$c = new C();
//$c->test(11);
echo memory_get_peak_usage(), PHP_EOL;

// 经测试，仅初始化 $c 对象消耗的内存峰值为 402416 字节，调用 test 方法所消耗的内存峰值为 431536 字节

  在对象中尝试调用某个方法时，如果该方法在当前对象中不存在或访问受限（protected、private），则会调用对象的魔术方法 __call（如果通过静态调用的方式，则会调用 __callStatic）。在 PHP 的底层实现中，该过程通过 zend_std_get_method 函数实现

static union _zend_function *zend_std_get_method(zend_object **obj_ptr, zend_string *method_name, const zval *key)
{
	zend_object *zobj = *obj_ptr;
	zval *func;
	zend_function *fbc;
	zend_string *lc_method_name;
	zend_class_entry *scope = NULL;
	ALLOCA_FLAG(use_heap);

	if (EXPECTED(key != NULL)) {
		lc_method_name = Z_STR_P(key);
#ifdef ZEND_ALLOCA_MAX_SIZE
		use_heap = 0;
#endif
	} else {
		ZSTR_ALLOCA_ALLOC(lc_method_name, ZSTR_LEN(method_name), use_heap);
		zend_str_tolower_copy(ZSTR_VAL(lc_method_name), ZSTR_VAL(method_name), ZSTR_LEN(method_name));
	}
	
	/* 所调用的方法在当前对象中不存在 */
	if (UNEXPECTED((func = zend_hash_find(&zobj->ce->function_table, lc_method_name)) == NULL)) {
		if (UNEXPECTED(!key)) {
			ZSTR_ALLOCA_FREE(lc_method_name, use_heap);
		}
		if (zobj->ce->__call) {
			/* 当前对象存在魔术方法 __call */
			return zend_get_user_call_function(zobj->ce, method_name);
		} else {
			return NULL;
		}
	}
	/* 所调用的方法为 protected 或 private 类型时的处理逻辑 */
	/* ... ... */
}


static zend_always_inline zend_function *zend_get_user_call_function(zend_class_entry *ce, zend_string *method_name)
{
	return zend_get_call_trampoline_func(ce, method_name, 0);
}


ZEND_API zend_function *zend_get_call_trampoline_func(zend_class_entry *ce, zend_string *method_name, int is_static)
{
	size_t mname_len;
	zend_op_array *func;
	zend_function *fbc = is_static ? ce->__callstatic : ce->__call;

	ZEND_ASSERT(fbc);

	if (EXPECTED(EG(trampoline).common.function_name == NULL)) {
		func = &EG(trampoline).op_array;
	} else {
		func = ecalloc(1, sizeof(zend_op_array));
	}

	func->type = ZEND_USER_FUNCTION;
	func->arg_flags[0] = 0;
	func->arg_flags[1] = 0;
	func->arg_flags[2] = 0;
	func->fn_flags = ZEND_ACC_CALL_VIA_TRAMPOLINE | ZEND_ACC_PUBLIC;
	if (is_static) {
		func->fn_flags |= ZEND_ACC_STATIC;
	}
	func->opcodes = &EG(call_trampoline_op);

	func->prototype = fbc;
	func->scope = fbc->common.scope;
	/* reserve space for arguments, local and temorary variables */
	func->T = (fbc->type == ZEND_USER_FUNCTION)? MAX(fbc->op_array.last_var + fbc->op_array.T, 2) : 2;
	func->filename = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.filename : ZSTR_EMPTY_ALLOC();
	func->line_start = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_start : 0;
	func->line_end = (fbc->type == ZEND_USER_FUNCTION)? fbc->op_array.line_end : 0;

	//??? keep compatibility for "\0" characters
	//??? see: Zend/tests/bug46238.phpt
	if (UNEXPECTED((mname_len = strlen(ZSTR_VAL(method_name))) != ZSTR_LEN(method_name))) {
		func->function_name = zend_string_init(ZSTR_VAL(method_name), mname_len, 0);
	} else {
		func->function_name = zend_string_copy(method_name);
	}

	return (zend_function*)func;
}


static void zend_init_call_trampoline_op(void)
{
	memset(&EG(call_trampoline_op), 0, sizeof(EG(call_trampoline_op)));
	EG(call_trampoline_op).opcode = ZEND_CALL_TRAMPOLINE;
	EG(call_trampoline_op).op1_type = IS_UNUSED;
	EG(call_trampoline_op).op2_type = IS_UNUSED;
	EG(call_trampoline_op).result_type = IS_UNUSED;
	ZEND_VM_SET_OPCODE_HANDLER(&EG(call_trampoline_op));
}

  ZEND_CALL_TRAMPOLINE 的底层实现逻辑：

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;
	USE_OPLINE

	args = emalloc(sizeof(zend_array));
	zend_hash_init(args, num_args, NULL, ZVAL_PTR_DTOR, 0);
	if (num_args) {
		zval *p = ZEND_CALL_ARG(execute_data, 1);
		zval *end = p + num_args;

		zend_hash_real_init(args, 1);
		ZEND_HASH_FILL_PACKED(args) {
			do {
				ZEND_HASH_FILL_ADD(p);
				p++;
			} while (p != end);
		} ZEND_HASH_FILL_END();
	}

	SAVE_OPLINE();
	call = execute_data;
	execute_data = EG(current_execute_data) = EX(prev_execute_data);

	ZEND_ASSERT(zend_vm_calc_used_stack(2, fbc->common.prototype) <= (size_t)(((char*)EG(vm_stack_end)) - (char*)call));

	call->func = fbc->common.prototype;
	ZEND_CALL_NUM_ARGS(call) = 2;

	ZVAL_STR(ZEND_CALL_ARG(call, 1), fbc->common.function_name);
	ZVAL_ARR(ZEND_CALL_ARG(call, 2), args);
	zend_free_trampoline(fbc);
	fbc = call->func;

	if (EXPECTED(fbc->type == ZEND_USER_FUNCTION)) {
		if (UNEXPECTED(!fbc->op_array.run_time_cache)) {
			init_func_run_time_cache(&fbc->op_array);
		}
		i_init_func_execute_data(call, &fbc->op_array, ret);
		if (EXPECTED(zend_execute_ex == execute_ex)) {
			ZEND_VM_ENTER();
		} else {
			ZEND_ADD_CALL_FLAG(call, ZEND_CALL_TOP);
			zend_execute_ex(call);
		}
	} else {
		/* ... ... */	
	}

	/* ... ... */
}

   从 ZEND_CALL_TRAMPOLINE 的底层实现可以看出，当发生 __call 的递归调用时（上例中 class C、class B、class A 中依次发生 __call 的调用），ZEND_VM_ENTER 将 execute_data 和 opline 进行变换，然后重新执行。

  递归之后还需要返回，返回的功能在 RETURN 中实现。所有的 PHP 代码在编译成 OPCode 之后，最后一条 OPCode 指令一定是 RETURN（即使代码中没有 return，编译时也会自动添加）。而在 ZEND_RETURN 中，最后一步要执行的操作为 zend_leave_helper ，递归的返回即时在这一步完成。

# define LOAD_NEXT_OPLINE() opline = EX(opline) + 1
# define ZEND_VM_CONTINUE() return
# define ZEND_VM_LEAVE() ZEND_VM_CONTINUE()

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((call_info & (ZEND_CALL_CODE|ZEND_CALL_TOP|ZEND_CALL_HAS_SYMBOL_TABLE|ZEND_CALL_FREE_EXTRA_ARGS|ZEND_CALL_ALLOCATED)) == 0)) {
		/* ... ... */

		LOAD_NEXT_OPLINE();
		ZEND_VM_LEAVE();
	} else if (EXPECTED((call_info & (ZEND_CALL_CODE|ZEND_CALL_TOP)) == 0)) {
		i_free_compiled_variables(execute_data);

		if (UNEXPECTED(call_info & ZEND_CALL_HAS_SYMBOL_TABLE)) {
			zend_clean_and_cache_symbol_table(EX(symbol_table));
		}
		EG(current_execute_data) = EX(prev_execute_data);
		/* ... ... */

		zend_vm_stack_free_extra_args_ex(call_info, execute_data);
		old_execute_data = execute_data;
		execute_data = EX(prev_execute_data);
		zend_vm_stack_free_call_frame_ex(call_info, old_execute_data);

		if (UNEXPECTED(EG(exception) != NULL)) {
			const zend_op *old_opline = EX(opline);
			zend_throw_exception_internal(NULL);
			if (RETURN_VALUE_USED(old_opline)) {
				zval_ptr_dtor(EX_VAR(old_opline->result.var));
			}
			HANDLE_EXCEPTION_LEAVE();
		}

		LOAD_NEXT_OPLINE();
		ZEND_VM_LEAVE();
	} else if (EXPECTED((call_info & ZEND_CALL_TOP) == 0)) {
		/* ... ... */

		LOAD_NEXT_OPLINE();
		ZEND_VM_LEAVE();
	} else {
		/* ... ... */
	}
}

  在 zend_leave_helper 中，execute_data 又被换成了 prev_execute_data ，然后继续执行新的 execute_data 的 opline（注意：这里并没有将 opline 初始化为 execute_data 中 opline 的第一条 OPCode，而是接着之前执行到的位置继续执行下一条 OPCode）。

推荐学习：《PHP视频教程》

The above is the detailed content of See how to optimize recursion in PHP 7!. For more information, please follow other related articles on the PHP Chinese website!