• 技术文章 >后端开发 >PHP7

    看看PHP 7中怎么优化递归的!

    青灯夜游青灯夜游2021-09-06 19:33:50转载159
    本篇文章带大家了解一下递归,介绍一下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 交互,需要借助虚拟机来虚拟化一套自身的堆、栈等概念。同时,还需要借助虚拟机来维护和管理这套虚拟化出来的堆栈。

      高级语言中的函数调用过程相较于低级语言已经很慢,而递归会让这种情况雪上加霜。以上例中的累加函数为例,每到一个 sumBelow,ZVM 都需要构造一个函数调用栈(具体调用栈的构造之前的文章已经讲过),随着 n 的增大,需要构造的调用栈会越来越多,最终导致内存溢出。相较于累加函数,斐波那契函数的递归会使得调用栈的数量呈现几何级数式的增加(因为每一个调用栈最终会新产生两个调用栈)。

    2.gif

    ⒊ 使用蹦床函数(trampoline)和尾调用(tail call)来优化递归

      ① 尾调用

      尾调用指的是一个函数最后只返回对自身的调用,再没有其他的任何操作。由于函数返回的是对自身的调用,因此编译器可以复用当前的调用栈而不需要新建调用栈。

    3.gif

      将前述的累加函数和斐波那契函数改为尾调用的实现方式,代码如下

    // 累加函数的尾调用方式实现
    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 中的累加函数 sum 发生尾调用时执行的 OPCode 为 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 字节

      在对象中尝试调用某个方法时,如果该方法在当前对象中不存在或访问受限(protectedprivate),则会调用对象的魔术方法 __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 Cclass Bclass A 中依次发生 __call 的调用),ZEND_VM_ENTERexecute_dataopline 进行变换,然后重新执行。

      递归之后还需要返回,返回的功能在 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_dataopline(注意:这里并没有将 opline 初始化为 execute_dataopline 的第一条 OPCode,而是接着之前执行到的位置继续执行下一条 OPCode)。

    推荐学习:《PHP视频教程

    以上就是看看PHP 7中怎么优化递归的!的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:掘金社区,如有侵犯,请联系admin@php.cn删除
    专题推荐:PHP 7 递归
    上一篇:带你了解PHP7里生成器的新特性 下一篇:怎么安装php7和php5共存
    线上培训班

    相关文章推荐

    • PHP 7.4的新增特性(功能,弃用,速度)• 详解PHP7新特性 What will be in PHP 7• 掌握PHP 7.x 各个版本的新特性• 你知道PHP 7.4的新增特性有哪些?• 简单对比一下PHP 7 和 PHP 5 中的对象

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网