我尝试了一些简单谓词的版本,该谓词将随机值从逻辑外的世界中提取出来并将其放入列表中。我假设带有累加器的版本为tail-call optimized,因为在递归调用之后什么也没有发生,因此存在优化路径,但是不存在(它使用“全局堆栈”)。另一方面,“天真的版本”显然已经优化成一个循环。这是SWI Prolog。
为什么累加器版本不能进行尾部调用优化?
这里是谓词版本。
在这里,我们只允许一个带有功能符号的头部来使事情明确。
% Slowest, and uses 4 inferences per call (+ 1 at the end of recursion).
% Uses "local stack" indicated in the "Stack limit (1.0Gb) exceeded"
% error at "Stack depth: 10,321,204":
% "Stack sizes: local: 1.0Gb, global: 7Kb, trail: 1Kb"
oracle_rands_explicit(Out,Size) :-
Size>0, !,
NewSize is Size-1,
oracle_rands_explicit(R,NewSize),
X is random_float,
Out = [X-Size|R].
oracle_rands_explicit([],0).
?- oracle_rands_explicit(X,4).
X = [0.7717053554954681-4, 0.9110187097066331-3, 0.9500246711335888-2, 0.25987829195170065-1].
?- X = 1000000, time(oracle_rands_explicit(_,X)).
% 4,000,001 inferences, 1.430 CPU in 1.459 seconds (98% CPU, 2797573 Lips)
?- X = 50000000, time(oracle_rands_explicit(_,X)).
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 1.0Gb, global: 7Kb, trail: 1Kb
ERROR: Stack depth: 10,321,204, last-call: 0%, Choice points: 6
ERROR: Possible non-terminating recursion: ...
同样,我们只允许一个不带功能符号的头使事情明确,但是将递归调用移到主体的末尾,这显然有所不同!
% Same number of inferences as Slowest, i.e. 4 inferences per call
% (+ 1 at the end of recursion), but at HALF the time.
% Does not run out of stack space! Conclusion: this is tail-call-optimized.
oracle_rands_explicit_last_call(Out,Size) :-
Size>0, !,
NewSize is Size-1,
X is random_float,
Out = [X-Size|R],
oracle_rands_explicit_last_call(R,NewSize).
oracle_rands_explicit_last_call([],0).
?- oracle_rands_explicit_last_call(X,4).
X = [0.6450176209046125-4, 0.5605468429780708-3, 0.597052872950385-2, 0.14440970112076815-1].
?- X = 1000000, time(oracle_rands_explicit_last_call(_,X)).
% 4,000,001 inferences, 0.697 CPU in 0.702 seconds (99% CPU, 5739758 Lips)
?- X = 50000000, time(oracle_rands_explicit_last_call(_,X)).
% 200,000,001 inferences, 32.259 CPU in 32.464 seconds (99% CPU, 6199905 Lips)
这里我们允许在头部使用功能符号,以便使用更紧凑的符号。仍然很幼稚的递归。
%每个调用仅3个推论(递归末尾+ 1),但大约%与“更快”相同的时间。%不会耗尽堆栈空间!结论:这是尾部呼叫优化的。
oracle_rands_compact([X-Size|R],Size) :-
Size>0, !,
NewSize is Size-1,
X is random_float,
oracle_rands_compact(R,NewSize).
oracle_rands_compact([],0).
?- oracle_rands_compact(X,4).
X = [0.815764980826608-4, 0.6516093608470418-3, 0.03206964297092248-2, 0.376168614426895-1].
?- X = 1000000, time(oracle_rands_compact(_,X)).
% 3,000,001 inferences, 0.641 CPU in 0.650 seconds (99% CPU, 4678064 Lips)
?- X = 50000000, time(oracle_rands_compact(_,X)).
% 150,000,001 inferences, 29.526 CPU in 29.709 seconds (99% CPU, 5080312 Lips)
% Accumulator-based, 3 inferences per call (+ 1 at the end of recursion + 1 at ignition),
% but it is often faster than the compact version.
% Uses "global stack" as indicated in the "Stack limit (1.0Gb) exceeded"
% error at "Stack depth: 12,779,585":
% "Stack sizes: local: 1Kb, global: 0.9Gb, trail: 40.6Mb"
oracle_rands_acc(Out,Size) :- oracle_rands_acc(Size,[],Out).
oracle_rands_acc(Size,ThreadIn,ThreadOut) :-
Size>0, !,
NewSize is Size-1,
X is random_float,
oracle_rands_acc(NewSize,[X-Size|ThreadIn],ThreadOut).
oracle_rands_acc(0,ThreadIn,ThreadOut) :- reverse(ThreadIn,ThreadOut).
?- oracle_rands_acc(X,4).
X = [0.7768407880604368-4, 0.03425412654687081-3, 0.6392634169514991-2, 0.8340458397587001-1].
?- X = 1000000, time(oracle_rands_acc(_,X)).
% 4,000,004 inferences, 0.798 CPU in 0.810 seconds (99% CPU, 5009599 Lips)
?- X = 50000000, time(oracle_rands_acc(_,X)).
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 1Kb, global: 0.9Gb, trail: 40.6Mb
ERROR: Stack depth: 12,779,585, last-call: 100%, Choice points: 6
ERROR: In:
ERROR: [12,779,585] user:oracle_rands_acc(37220431, [length:12,779,569], _876)
这全都取决于顶层shell和_
的实际解释。尝试
?- X = 50000000, time(oracle_rands_compact(L,X)),L=[].
相反,它将或多或少与必须首先产生整个列表仅将其移交给reverse/2
的累加器版本一样糟糕。查看此用法
?- set_prolog_flag(trace_gc, true).
如果需要的话,可以通过交换参数并删除剪切来加快您的_compact
版本。经典的第一个自变量索引能够处理这种情况,避免任何选择点。 (SWI具有WAM样式的第一个参数索引,以及我上次检查时针对多个参数的较小版本)