Lihat cara untuk mengoptimumkan rekursi dalam PHP 7!

Artikel ini akan memperkenalkan anda kepada rekursi dan memperkenalkan pengoptimuman rekursi dalam PHP 7.

⒈ Rekursi

  Rekursi sering digunakan dalam pengaturcaraan kerana kesederhanaan dan keanggunannya. Kod rekursif lebih bersifat deklaratif dan menggambarkan diri. Rekursi tidak perlu menerangkan cara mendapatkan nilai seperti lelaran, sebaliknya menerangkan hasil akhir fungsi.

  Ambil pelaksanaan akumulasi dan jujukan Fibonacci sebagai contoh:

• Pelaksanaan berulang

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

• Pelaksanaan rekursif

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

 Sebagai perbandingan, pelaksanaan rekursif adalah lebih ringkas dan jelas, lebih mudah dibaca dan lebih mudah difahami.

⒉ Masalah dengan rekursi

Panggilan fungsi dalam program biasanya perlu mengikut konvensyen panggilan tertentu di peringkat bawah. Proses biasa ialah:

• Mula-mula tolak parameter fungsi dan alamat pemulangan ke dalam tindanan
• Kemudian CPU mula melaksanakan kod dalam badan fungsi
• Akhir sekali, pelaksanaan fungsi selesai Selepas itu, ruang dimusnahkan, dan CPU kembali ke lokasi yang ditunjukkan oleh alamat pemulangan

 Proses ini sangat pantas dalam bahasa peringkat rendah (seperti sebagai pemasangan), kerana bahasa peringkat rendah berinteraksi secara langsung dengan CPU, dan operasi CPU Sangat pantas. Dalam Linux dengan seni bina x86_64, parameter sering dihantar terus melalui daftar, dan ruang tindanan dalam memori akan dimuatkan ke dalam cache CPU, supaya CPU boleh mengakses ruang tindanan dengan sangat cepat.

  Proses yang sama adalah berbeza sama sekali dalam bahasa peringkat tinggi seperti PHP. Bahasa peringkat tinggi tidak boleh berinteraksi secara langsung dengan CPU dan perlu menggunakan mesin maya untuk memayakan set konsep seperti timbunan dan timbunan. Pada masa yang sama, mesin maya juga diperlukan untuk mengekalkan dan mengurus timbunan maya ini.

  Proses panggilan fungsi dalam bahasa peringkat tinggi sudah sangat perlahan berbanding bahasa peringkat rendah, dan pengulangan akan memburukkan keadaan ini. Mengambil fungsi pengumpulan dalam contoh di atas sebagai contoh, ZVM perlu membina timbunan panggilan fungsi untuk setiap sumBelow (pembinaan khusus timbunan panggilan telah dibincangkan dalam artikel sebelumnya Apabila n meningkat, timbunan panggilan perlu akan dibina Akan semakin banyak, akhirnya membawa kepada limpahan ingatan. Berbanding dengan fungsi terkumpul, pengulangan fungsi Fibonacci akan meningkatkan bilangan tindanan panggilan dalam janjang geometri (kerana setiap tindanan panggilan akhirnya akan menghasilkan dua tindanan panggilan baharu).

⒊ Gunakan trampolin dan panggilan ekor untuk mengoptimumkan rekursi

① Panggilan ekor

Panggilan ekor merujuk kepada a fungsi yang hanya mengembalikan panggilan kepada dirinya sendiri pada akhirnya, tanpa sebarang operasi lain. Kerana fungsi mengembalikan panggilan kepada dirinya sendiri, pengkompil boleh menggunakan semula tindanan panggilan semasa tanpa membuat tindanan panggilan baharu.

   Tukar fungsi pengumpulan dan fungsi Fibonacci yang dinyatakan di atas kepada pelaksanaan panggilan ekor, kodnya adalah seperti berikut

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

  ② Fungsi Trampolin

 Fungsi pengumpulan agak mudah dan boleh ditukar dengan mudah menjadi pelaksanaan panggilan ekor. Pelaksanaan panggilan ekor bagi fungsi Fibonacci agak menyusahkan. Tetapi dalam aplikasi praktikal, banyak rekursi bercampur dengan banyak pertimbangan bersyarat yang kompleks, dan kaedah rekursi yang berbeza dilakukan dalam keadaan yang berbeza. Pada masa ini, fungsi rekursif tidak boleh ditukar terus kepada bentuk panggilan ekor, dan fungsi trampolin diperlukan.

   Fungsi trampolin yang dipanggil, prinsip asasnya ialah membungkus fungsi rekursif ke dalam bentuk berulang. Mengambil fungsi terkumpul sebagai contoh, mula-mula tulis semula pelaksanaan fungsi terkumpul:

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

  Pada penghujung fungsi, panggilan rekursif tidak dibuat secara langsung, tetapi panggilan rekursif dibungkus ke dalam penutupan , dan fungsi penutupan Ia tidak akan dilaksanakan serta-merta. Pada masa ini, anda perlu menggunakan fungsi trampolin Jika fungsi trampolin mendapati bahawa apa yang dikembalikan adalah penutupan, maka fungsi trampolin akan terus melaksanakan penutupan yang dikembalikan sehingga fungsi trampolin mendapati bahawa apa yang dikembalikan adalah nilai.

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

echo trampoline('trampolineSumBelow', 100);

  fungsi trampolin ialah cara yang lebih umum untuk menyelesaikan masalah panggilan rekursif. Dalam fungsi trampolin, penutupan yang dikembalikan dilaksanakan secara berulang, mengelakkan limpahan memori yang disebabkan oleh pengulangan fungsi.

⒋ Pengoptimuman rekursi dalam ZVM

  Dalam PHP 7, pengoptimuman rekursi melalui panggilan ekor digunakan terutamanya dalam kaedah objek. Masih mengambil fungsi terkumpul sebagai contoh:

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

  OPCod yang sepadan dengan kod di atas ialah:

// 主函数
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 dilaksanakan apabila fungsi terkumpul

dalam kelas adalah tail-called ialah sum , pelaksanaan asas yang sepadan ialah: 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视频教程》

Atas ialah kandungan terperinci Lihat cara untuk mengoptimumkan rekursi dalam PHP 7!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!