BEAM 字节码指令的尾调用递归行为 call_last
Tail-call recursive behavior of the BEAM bytecode instruction call_last
我们最近在阅读 BEAM Book 作为阅读小组的一部分。
在附录 B.3.3 中指出 call_last
指令具有以下行为
Deallocate Deallocate
words of stack, then do a tail recursive
call to the function of arity Arity in the same module at label
Label
根据我们目前的理解,尾递归意味着堆栈上分配的内存可以从当前调用中重用。
因此,我们想知道从堆栈中释放了什么。
另外,我们也想知道为什么尾递归调用之前需要先从栈中释放,而不是直接进行尾递归调用。
(免责声明:这是一个猜测)
Tail-recursion 调用并不意味着它不能执行之前的任何其他调用或同时使用堆栈。在那种情况下,必须在执行 tail-recursion 之前释放为这些调用分配的堆栈。 call_last
在表现得像 call_only
.
之前释放多余的堆栈
如果你erlc -S
下面的代码,你可以看到一个例子:
-module(test).
-compile(export_all).
fun1([]) ->
ok;
fun1([1|R]) ->
fun1(R).
funN() ->
A = list(),
B = list(),
fun1([A, B]).
list() ->
[1,2,3,4].
我已经对相关部分进行了注释:
{function, fun1, 1, 2}.
{label,1}.
{line,[{location,"test.erl",4}]}.
{func_info,{atom,test},{atom,fun1},1}.
{label,2}.
{test,is_nonempty_list,{f,3},[{x,0}]}.
{get_list,{x,0},{x,1},{x,2}}.
{test,is_eq_exact,{f,1},[{x,1},{integer,1}]}.
{move,{x,2},{x,0}}.
{call_only,1,{f,2}}. % No stack allocated, no need to deallocate it
{label,3}.
{test,is_nil,{f,1},[{x,0}]}.
{move,{atom,ok},{x,0}}.
return.
{function, funN, 0, 5}.
{label,4}.
{line,[{location,"test.erl",10}]}.
{func_info,{atom,test},{atom,funN},0}.
{label,5}.
{allocate_zero,1,0}. % Allocate 1 slot in the stack
{call,0,{f,7}}. % Leaves the result in {x,0} (the 0 register)
{move,{x,0},{y,0}}.% Moves the previous result from {x,0} to the stack because next function needs {x,0} free
{call,0,{f,7}}. % Leaves the result in {x,0} (the 0 register)
{test_heap,4,1}.
{put_list,{x,0},nil,{x,0}}. % Create a list with only the last value, [B]
{put_list,{y,0},{x,0},{x,0}}. % Prepend A (from the stack) to the previous list, creating [A, B] ([A | [B]]) in {x,0}
{call_last,1,{f,2},1}. % Tail recursion call deallocating the stack
{function, list, 0, 7}.
{label,6}.
{line,[{location,"test.erl",15}]}.
{func_info,{atom,test},{atom,list},0}.
{label,7}.
{move,{literal,[1,2,3,4]},{x,0}}.
return.
编辑:
实际回答您的问题:
线程的内存同时用于栈和堆,它们在相对的两侧使用相同的内存块,相互增长(线程的GC在它们相遇时触发)。
在这种情况下,“分配”意味着增加用于堆栈的 space,如果不再使用 space,则必须将其释放(返回到内存块)以便以后可以再次使用它(作为堆或堆栈)。
在 CPU 的 asm 中,优化的尾调用只是跳转到函数入口点。 IE。 运行整个函数在tail-recursion的情况下作为一个循环体。 (没有推送 return 地址,所以当你到达 base-case 它只是一个 return 回到最终父级。)
我大胆猜测 Erlang / BEAM 字节码在很大程度上是相似的,尽管我对此一无所知。
当执行到达一个函数的顶部时,它不知道它是通过递归还是从另一个函数调用到达那里,因此如果需要的话必须分配更多的space。
如果你想重用 already-allocated 堆栈 space,你必须进一步优化 tail-recursion 到函数体内的实际循环,而不是递归。
或者换句话说,要尾调用任何东西,您需要调用堆栈处于与函数入口时相同的状态。跳转而不是调用失去了在被调用函数return之后进行任何清理的机会return,因为它return是给你的调用者,而不是你。
但是我们不能将 stack-cleanup 放在实际上执行 return 的递归 base-case 中而不是尾调用吗?是的,但这只有在分配新的 space 已经完成后“tailcall”指向此函数中的某个点时才有效,而不是外部调用者将调用的入口点。这 2 个更改与将 tail-recursion 变成循环完全相同。
我们最近在阅读 BEAM Book 作为阅读小组的一部分。
在附录 B.3.3 中指出 call_last
指令具有以下行为
Deallocate
Deallocate
words of stack, then do a tail recursive call to the function of arity Arity in the same module at label Label
根据我们目前的理解,尾递归意味着堆栈上分配的内存可以从当前调用中重用。
因此,我们想知道从堆栈中释放了什么。
另外,我们也想知道为什么尾递归调用之前需要先从栈中释放,而不是直接进行尾递归调用。
(免责声明:这是一个猜测)
Tail-recursion 调用并不意味着它不能执行之前的任何其他调用或同时使用堆栈。在那种情况下,必须在执行 tail-recursion 之前释放为这些调用分配的堆栈。 call_last
在表现得像 call_only
.
如果你erlc -S
下面的代码,你可以看到一个例子:
-module(test).
-compile(export_all).
fun1([]) ->
ok;
fun1([1|R]) ->
fun1(R).
funN() ->
A = list(),
B = list(),
fun1([A, B]).
list() ->
[1,2,3,4].
我已经对相关部分进行了注释:
{function, fun1, 1, 2}.
{label,1}.
{line,[{location,"test.erl",4}]}.
{func_info,{atom,test},{atom,fun1},1}.
{label,2}.
{test,is_nonempty_list,{f,3},[{x,0}]}.
{get_list,{x,0},{x,1},{x,2}}.
{test,is_eq_exact,{f,1},[{x,1},{integer,1}]}.
{move,{x,2},{x,0}}.
{call_only,1,{f,2}}. % No stack allocated, no need to deallocate it
{label,3}.
{test,is_nil,{f,1},[{x,0}]}.
{move,{atom,ok},{x,0}}.
return.
{function, funN, 0, 5}.
{label,4}.
{line,[{location,"test.erl",10}]}.
{func_info,{atom,test},{atom,funN},0}.
{label,5}.
{allocate_zero,1,0}. % Allocate 1 slot in the stack
{call,0,{f,7}}. % Leaves the result in {x,0} (the 0 register)
{move,{x,0},{y,0}}.% Moves the previous result from {x,0} to the stack because next function needs {x,0} free
{call,0,{f,7}}. % Leaves the result in {x,0} (the 0 register)
{test_heap,4,1}.
{put_list,{x,0},nil,{x,0}}. % Create a list with only the last value, [B]
{put_list,{y,0},{x,0},{x,0}}. % Prepend A (from the stack) to the previous list, creating [A, B] ([A | [B]]) in {x,0}
{call_last,1,{f,2},1}. % Tail recursion call deallocating the stack
{function, list, 0, 7}.
{label,6}.
{line,[{location,"test.erl",15}]}.
{func_info,{atom,test},{atom,list},0}.
{label,7}.
{move,{literal,[1,2,3,4]},{x,0}}.
return.
编辑:
实际回答您的问题:
线程的内存同时用于栈和堆,它们在相对的两侧使用相同的内存块,相互增长(线程的GC在它们相遇时触发)。
在这种情况下,“分配”意味着增加用于堆栈的 space,如果不再使用 space,则必须将其释放(返回到内存块)以便以后可以再次使用它(作为堆或堆栈)。
在 CPU 的 asm 中,优化的尾调用只是跳转到函数入口点。 IE。 运行整个函数在tail-recursion的情况下作为一个循环体。 (没有推送 return 地址,所以当你到达 base-case 它只是一个 return 回到最终父级。)
我大胆猜测 Erlang / BEAM 字节码在很大程度上是相似的,尽管我对此一无所知。
当执行到达一个函数的顶部时,它不知道它是通过递归还是从另一个函数调用到达那里,因此如果需要的话必须分配更多的space。
如果你想重用 already-allocated 堆栈 space,你必须进一步优化 tail-recursion 到函数体内的实际循环,而不是递归。
或者换句话说,要尾调用任何东西,您需要调用堆栈处于与函数入口时相同的状态。跳转而不是调用失去了在被调用函数return之后进行任何清理的机会return,因为它return是给你的调用者,而不是你。
但是我们不能将 stack-cleanup 放在实际上执行 return 的递归 base-case 中而不是尾调用吗?是的,但这只有在分配新的 space 已经完成后“tailcall”指向此函数中的某个点时才有效,而不是外部调用者将调用的入口点。这 2 个更改与将 tail-recursion 变成循环完全相同。