4

8.1 版的表格功能做了一些实验，对 我观察到的性能感到非常惊讶。

这是我使用的代码。它计算将某个正整数减少到所需的Collat​​z步数：NI1

%:- table posInt_CollatzSteps/2.               % remove comment to enable tabling
posInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  1 is I /\ 1 
   -> I0 is I*3+1, posInt_CollatzSteps(I0,N0), N is N0+1   % odd
   ;  I0 is I>>1,  posInt_CollatzSteps(I0,N0), N is N0+1   % even
   ).

I0要确定从到的所有整数所需的最大归约步骤数I：

i0_i_maxSteps0_maxSteps(I0,I,M0,M) :-
   (  I0 > I
   -> M0 = M
   ;  posInt_CollatzSteps(I0,N0),
      I1 is I0+1,
      M1 is max(M0,N0),
      i0_i_maxSteps0_maxSteps(I1,I,M1,M)
   ).

当我在没有和使用表格的情况下运行一些查询?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)).时，我观察到以下运行时（以秒为单位）：

  • 不带表格：6.784
  • 带表：2.323、19.78、3.089、3.084、3.081 _ _ _ _

通过添加:- table posInt_CollatzSteps/2.查询，速度提高了 2 倍。尽管如此，我还是很困惑：

  • 第二次运行比第一次慢 5 倍以上。显然大部分时间都花在了 GC 上。从第 3 次运行开始，制表变体再次变快。
  • 热运行（第 3 次、第 4 次、...）明显慢于冷运行（第 1 次）。

我没想到会这样！将此与我在版本 3.6.0 中观察到的运行时进行对比：

  • 不带表格：14.287
  • 带表：1.829、0.31、0.308、0.31、0.333 _ _ _ _

我能做些什么？是否有任何指令或标志可以帮助我使用 BProlog 获得更好的性能？我在 Linux 上使用 BProlog 版本 8.1 64 位版本。

4

1 回答 1

2

正在检查 Jekejeke Prolog 跟踪备忘录。只打算n = 100'000。对于 B-Prolog，以下命令行在 Windows 上运行良好：

bp -s 40000000

据说这相当于 160MB 的堆栈/堆空间。与冷跑相比，我得到了桌面和非桌面更好的热跑：

B-Prolog n=100'000 in s:
w/o table: 14.276, 12.229
with table: 0.419, 0.143, 0.127, 0.152

Jekejeke 的备忘录代码使用来自模块hypo 的谓词assumez/2。与 B-Prolog 表相比，尾随备忘录将在每次调用时重新计算所有内容。您需要手动将其添加到您的代码中：

Jekejeke Prolog/Minlog n=100'000 in s:
w/o memoing: 4.521, 3.893
with memoing: 0.724, 0.573, 0.585, 0.555

所以 Jekejeke 的速度仍有提升空间。关于您的 B-Prolog 问题：当内存太紧时，这可能会给 GC 带来不规则的额外压力，可能会导致您观察到的行为。

再见

PS：这是 Jekejeke Prolog 备忘录代码。您需要安装 Jekejeke Minlog 以使模块hypo可用。最好是安装最新版本：

:- thread_local posInt_CollatzStepsm/2.

mposInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  posInt_CollatzStepsm(I,N) %%% memo check
   -> true
   ;  1 is I /\ 1
   -> I0 is I*3+1, mposInt_CollatzSteps(I0,N0), N is N0+1,   % odd
      assumez(posInt_CollatzStepsm(I,N)) %%% memo add
   ;  I0 is I>>1,  mposInt_CollatzSteps(I0,N0), N is N0+1,   % even
      assumez(posInt_CollatzStepsm(I,N)) %%% memo add
   ).

?- time(mi0_i_maxSteps0_maxSteps(1, 100000, 0, R)).
% Up 724 ms, GC 71 ms, Thread Cpu 640 ms (Current 06/20/19 09:43:24)
R = 350

?- time(mi0_i_maxSteps0_maxSteps(1, 100000, 0, R)).
% Up 573 ms, GC 69 ms, Thread Cpu 500 ms (Current 06/20/19 09:43:27)
R = 350
于 2016-05-15T20:51:39.420 回答