prolog - 天真地假设被认为是有害的 : Prolog predicate with accumulator blows (global) stack, 但天真的版本没有

Question

我尝试了几个版本的简单谓词，该谓词从超逻辑宇宙中提取随机值并将它们放入列表中。我假设带有累加器的版本是 tail-call optimized ，因为在递归调用之后什么也没有发生，所以存在优化的路径，但它不是(它使用“全局堆栈”)。另一方面，“天真版本”显然已被优化为一个循环。这是 SWI 序言。

为什么累加器版本不受尾调用优化的影响？

这是谓词版本。

最慢，用完本地堆栈空间(预期)

在这里，我们只允许一个带有函数符号的头部来使事情变得明确。

% 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: ...

更快，并且不会耗尽堆栈空间

同样，我们只允许没有函数符号的 head 使事情变得明确，但是我们将递归调用移动到 body 的末尾，这显然有所不同!

% 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)

附录:“紧凑”版本的另一个版本。

我们在这里移动 Size参数放在第一个位置，不要使用 ! .但是 indexing is a complex matter .差异可能只会在更多条款中引起注意。

oracle_rands_compact2(Size,[X-Size|R]) :- 
   Size>0, 
   NewSize is Size-1,    
   X is random_float, 
   oracle_rands_compact2(NewSize,R).
oracle_rands_compact2(0,[]).

正在尝试，与 L而不是匿名变量，和 L调用后使用。

X = 10000000, time(oracle_rands_compact2(X,L)),L=[].
% 30,000,002 inferences, 6.129 CPU in 6.159 seconds (100% CPU, 4894674 Lips)

X = 10000000, time(oracle_rands_compact(L,X)),L=[].
% 30,000,001 inferences, 5.865 CPU in 5.892 seconds (100% CPU, 5115153 Lips)

也许稍微快一点。上述数字略有不同，实际上必须生成超过一百次运行的完整统计数据。

重新引入切割是否使它更快(它似乎并没有使它变慢)？

oracle_rands_compact3(Size,[X-Size|R]) :- 
   Size>0, !,
   NewSize is Size-1,    
   X is random_float, 
   oracle_rands_compact3(NewSize,R).
oracle_rands_compact3(0,[]).

?- X = 10000000, time(oracle_rands_compact3(X,L)),L=[].
% 30,000,001 inferences, 5.026 CPU in 5.061 seconds (99% CPU, 5969441 Lips)

不能说，真的。

Answer 1

这一切都取决于顶级shell和_的实际解释。 .尝试

 ?- X = 50000000, time(oracle_rands_compact(L,X)),L=[].

相反，它或多或少与必须首先生成整个列表的累加器版本一样糟糕，然后才将其交给 reverse/2 .看这个用法

?- set_prolog_flag(trace_gc, true).
true.

?- X = 50000000, time(oracle_rands_compact(_,X)).
% GC: gained 0+0 in 0.001 sec; used 440+8; free 126,520+129,008
% GC: gained 0+0 in 0.000 sec; used 464+16; free 126,496+129,000
% GC: gained 0+0 in 0.000 sec; used 464+16; free 126,496+129,000
...

?- X = 50000000, time(oracle_rands_compact(L,X)),L=[].
% SHIFT: l:g:t = 0:1:0 ...l+g+t = 131072+262144+131072 (0.000 sec)
% GC: gained 0+0 in 0.002 sec; used 123,024+16; free 135,008+129,000
% SHIFT: l:g:t = 0:1:0 ...l+g+t = 131072+524288+131072 (0.000 sec)
% GC: gained 0+0 in 0.003 sec; used 257,976+24; free 262,200+128,992
% SHIFT: l:g:t = 0:0:1 ...l+g+t = 131072+524288+262144 (0.000 sec)
% SHIFT: l:g:t = 0:1:0 ...l+g+t = 131072+1048576+262144 (0.000 sec)
% GC: gained 0+0 in 0.007 sec; used 520,104+16; free 524,360+260,072
...

如果我们在，您的 _compact版本可以通过交换参数和删除剪切来加速。经典的第一个参数索引能够处理这种情况，避免任何选择点。 (SWI 具有 WAM 样式的第一个参数索引以及多个参数的较小版本，我上次检查过)