BProlog 8.1 中的表格性能不均匀

Question

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

这是我使用的代码。它计算将某些正整数 N 减少到

I

所需的

Collatz

步骤

1

的数量：

%:- 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 上。从第三次运行开始，表格变体再次变得很快。
• 热跑（第三次、第四次……）比冷跑（第一次）明显慢。

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

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

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

Answer 1

正在检查 Jekejeke Prolog 跟踪备忘录。本来只是去 至 n=100'000。对于 B-Prolog，以下命令行运行良好 在窗户上：

bp -s 40000000

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

B-Prolog n=100'000 in s:
不带桌子：14.276、12.229
带表格：0.419、0.143、0.127、0.152

Jekejeke 的备忘录

code 使用来自 模块低。与 B-Prolog 表格相反，跟踪备忘录将在每次调用时重新计算所有内容。您需要手动将其添加到您的代码中：

Jekejeke Prolog/Minlog n=100'000 in s:

不带备忘录：4.521、3.893
带记忆：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