BProlog 8.1 中的制表性能不均匀

Question

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

这是我使用的代码。它计算将一些正整数 I 减少到 1:

所需的 Collatz 步数 N

%:- 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)). 没有和有制表时，我观察到以下运行次（以秒为单位）：

w/o 表：6.784
加表：2.323，19.78，3.089，3.084，3.081

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

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

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

w/o 制表：14.287
加表：1.829，0.31，0.308，0.31，0.333

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

Answer 1

正在检查 Jekejeke Prolog 尾随备忘录。只是去至 n=100'000。对于 B-Prolog，以下命令行运行良好在 windows:

bp -s 40000000

据说这相当于 stack/heap space 160MB。我得到两个有表和无表的热运行比冷运行更好：

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

Jekejeke 的备忘录 code 使用来自低模块。与 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，可能会导致您观察到的行为。

再见

P.S.: 这是 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

BProlog 8.1 中的制表性能不均匀

Uneven tabling performance in BProlog 8.1

performance

prolog

memoization

b-prolog

prolog-tabling