本篇文章带大家了解一下递归,介绍一下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); } ??相比之下,递归的实现方式更简洁明了,可读性更强,更容易理解。 ⒉ 递归存在的问题??程序中的函数调用,在底层通常需要遵循一定的调用约定(calling convention)。通常的过程是:
??这个过程在低级语言(例如汇编)中非常快,因为低级语言直接与 CPU 交互,而 CPU 的运行速度非常快。在 x86_64 架构的 Linux 中,参数往往直接通过寄存器传递,内存中的栈空间会被预加载到 CPU 的缓存中,这样 CPU 反问栈空间会非常非常快。 ??同样的过程在高级语言(例如 PHP)中却截然不同。高级语言无法直接与 CPU 交互,需要借助虚拟机来虚拟化一套自身的堆、栈等概念。同时,还需要借助虚拟机来维护和管理这套虚拟化出来的堆栈。 ??高级语言中的函数调用过程相较于低级语言已经很慢,而递归会让这种情况雪上加霜。以上例中的累加函数为例,每到一个 ⒊ 使用蹦床函数(trampoline)和尾调用(tail call)来优化递归??① 尾调用??尾调用指的是一个函数最后只返回对自身的调用,再没有其他的任何操作。由于函数返回的是对自身的调用,因此编译器可以复用当前的调用栈而不需要新建调用栈。 ??将前述的累加函数和斐波那契函数改为尾调用的实现方式,代码如下 // 累加函数的尾调用方式实现 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 ??当 class 中的累加函数 # 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(); } ??从 ??通过蹦床函数的方式优化递归调用主要应用在对象的魔术方法 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 字节 ??在对象中尝试调用某个方法时,如果该方法在当前对象中不存在或访问受限( 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)); } ?? 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 { /* ... ... */ } /* ... ... */ } ?? 从 ??递归之后还需要返回,返回的功能在 # 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 { /* ... ... */ } } ??在 推荐学习:《PHP视频教程》 以上就是看看PHP 7中怎么优化递归的!的详细内容,更多请关注模板之家(www.mb5.com.cn)其它相关文章! |