PHP 7 で再帰を最適化する方法をご覧ください。

この記事では再帰について説明し、PHP 7 での再帰の最適化について紹介します。

⒈ 再帰

再帰は、そのシンプルさと洗練さのため、プログラミングでよく使用されます。再帰的コードはより宣言的で自己記述的です。再帰では、反復のように値を取得する方法を説明する必要はありませんが、むしろ関数の最終結果を説明します。

累積数とフィボナッチ数の実装を例に挙げます。

• 反復実装

// 累加函数
// 给定参数 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];
}

• 再帰的実装

// 累加函数
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);
}

対照的に、再帰的実装はより簡潔かつ明確で、より読みやすく、理解しやすいです。

⒉ 再帰の問題

プログラム内の関数呼び出しは、通常、最下位レベルで特定の呼び出し規約に従う必要があります。通常のプロセスは次のとおりです。

• 最初に関数のパラメータと戻りアドレスをスタックにプッシュします
• 次に、CPU が関数本体のコードの実行を開始します
• 最後に、関数の実行が完了します。 その後、空間が破棄され、CPU は戻りアドレスが指す場所に戻ります。

この処理は、低級言語では非常に高速です (アセンブリなど）、低レベル言語は CPU と直接対話し、CPU は高速に動作するためです。 x86_64 アーキテクチャの Linux では、パラメータはレジスタを介して直接渡されることが多く、メモリ内のスタック スペースが CPU キャッシュにプリロードされるため、CPU は非常に迅速にスタック スペースにアクセスできます。

同じプロセスでも、PHP などの高級言語ではまったく異なります。高級言語は CPU と直接対話することができず、仮想マシンを使用してヒープやスタックなどの一連の概念を仮想化する必要があります。同時に、この仮想化スタックを維持および管理するために仮想マシンも必要になります。

高水準言語の関数呼び出しプロセスは、低水準言語に比べてすでに非常に遅いですが、再帰によってこの状況はさらに悪化します。上の例の累積関数を例にとると、ZVM は sumBelow ごとに関数呼び出しスタックを構築する必要があります (呼び出しスタックの具体的な構築については以前の記事で説明しています)。構築される呼び出しスタックがますます多くなり、最終的にはメモリ オーバーフローが発生します。累積関数と比較して、フィボナッチ関数の再帰では呼び出しスタックの数が幾何級数的に増加します (各呼び出しスタックは最終的に 2 つの新しい呼び出しスタックを生成するため)。

⒊ トランポリンとテール コールを使用して再帰を最適化する

# ① テール コール

テール コールとは、他の操作を行わず、最終的に自分自身への呼び出しのみを返す関数。関数はそれ自体への呼び出しを返すため、コンパイラは新しい呼び出しスタックを作成せずに現在の呼び出しスタックを再利用できます。

上記の累積関数とフィボナッチ関数をテールコール実装に変更すると、コードは次のとおりです

// 累加函数的尾调用方式实现
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);
}

② トランポリン関数

#累積関数は比較的単純であり、末尾呼び出しの実装に簡単に変換できます。フィボナッチ関数の末尾呼び出しの実装は比較的面倒です。しかし、実際のアプリケーションでは、多くの再帰が多くの複雑な条件判断と混合され、さまざまな条件下でさまざまな再帰方法が実行されます。このとき、再帰関数をそのまま末尾呼び出し形式に変換することはできず、トランポリン関数が必要となります。

いわゆるトランポリン関数の基本原理は、再帰関数を反復形式にラップすることです。累積関数を例にとると、まず累積関数の実装を書き換えます。

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

関数の最後では、再帰呼び出しは直接行われませんが、再帰呼び出しはクロージャにパッケージ化され、クロージャ関数はすぐには実行されません。このとき、トランポリン関数を使用する必要があります。トランポリン関数は、返されたものがクロージャであると判断した場合、返されたものが値であると判断するまで、返されたクロージャを実行し続けます。

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

echo trampoline('trampolineSumBelow', 100);

トランポリン関数は、再帰呼び出しの問題を解決するためのより一般的な方法です。トランポリン関数では、返されたクロージャが繰り返し実行され、関数の再帰によって引き起こされるメモリ オーバーフローが回避されます。

⒋ ZVM における再帰の最適化

PHP 7 では、末尾呼び出しによる再帰の最適化は主にオブジェクト メソッドで使用されます。引き続き累積関数を例に挙げます:

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

上記のコードに対応する OPCode は次のとおりです:

// 主函数
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

OPCode は、累積関数

sum が末尾で呼び出されるクラスは DO_FCALL で、対応する基礎となる実装は次のとおりです:

# 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视频教程》

以上がPHP 7 で再帰を最適化する方法をご覧ください。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。