问题描述
我用表格功能做了一些实验b-prolog 版本 8.1对我观察到的表现感到非常惊讶.
I did a few experiments with the tabling capabilities ofb-prolog version 8.1 and was quite surprised by the performance I observed.
这是我使用的代码.它计算减少某些正整数所需的 Collatz 步骤 N 的数量I 到 1:
Here is the code that I used. It counts the number of Collatz steps N required for reducing some positive integer I down to 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 的所有整数所需的最大归约步骤数:
To determine the maximum number of reduction steps required for all integers from I0 to 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)). 没有和有表格时，我观察到以下运行时间(以秒为单位):
When I ran some queries ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)). without and with tabling, I observed the following runtimes (in seconds):
- 不带表格:6.784
- 带表:2.323、19.78、3.089、3.084、3.081
通过添加 :- table posInt_CollatzSteps/2.，查询速度提高了 2 倍.尽管如此，我还是很困惑:
By adding :- table posInt_CollatzSteps/2. the queries got 2x faster. Still, I'm puzzled:
- 第二次运行比第一次慢 5 倍以上.显然大部分时间都花在了 GC 上.从第 3 次运行开始，制表变体再次变快.
- 热运行(第 3 次、第 4 次、...)明显比冷运行(第 1 次)慢.
我没想到会这样！将此与我在 xsb 版本中观察到的运行时进行对比3.6.0:
I wasn't expecting this! Contrast this with the runtime that I observed with xsb version 3.6.0:
- 不带桌位:14.287
- 带表格:1.829、0.31、0.308、0.31、0.333
我能做什么?是否有任何指令或标志可以帮助我使用 BProlog 获得更好的性能?我在 Linux 上使用 BProlog 8.1 64 位版本.
What can I do? Are there any directives or flags to help me get better performance with BProlog? I use BProlog version 8.1 64-bit edition with Linux.
推荐答案
正在检查 Jekejeke Prolog 跟踪备忘录.只是去到 n = 100'000.对于 B-Prolog，以下命令行工作正常在窗户上:
Was checking against Jekejeke Prolog trailed memoing. Was only goingto n=100'000. For B-Prolog the following command line worked fineon windows:
bp -s 40000000
据说这相当于 160MB 的堆栈/堆空间.我得到了两个桌面和非桌面的热跑比冷跑更好:
This is said to amount to a stack/heap space of 160MB. I get bothtabled and non-tabled better warm runs than cold runs:
B-Prolog n=100'000 in s:
不带表格:14.276、12.229
带表:0.419、0.143、0.127、0.152
Jekejeke 的备忘录代码使用谓词assumez/2来自模块hypo.与 B-Prolog 表相比，尾随备忘录将在每次调用时重新计算所有内容.您需要手动将其添加到您的代码中:
The memoing code for Jekejeke uses the predicate assumez/2 from themodule hypo. In contrast to B-Prolog tabling, the trailed memoing will recalculate everything upon each call. You need to manually add it to your code:
Jekejeke Prolog/Minlog n=100'000 in s:
无备注:4.521、3.893
带备忘录:0.724、0.573、0.585、0.555
因此，Jekejeke 的速度仍有提升空间.关于你的 B-Prolog 问题:当记忆太多时紧，这可能会不规则地施加额外的压力GC，可能会导致您观察到的行为.
So there is still room for speed improvements in Jekejeke.Concerning your B-Prolog question: When the memory is tootight, this might irregularily put additional pressure ona GC, maybe resulting in your observed behaviour.
再见
P.S.:这是 Jekejeke Prolog 备忘录代码.你需要安装 Jekejeke Minlog 以获得模块 hypo 可用.最好的是安装最新版本:
P.S.: This is the Jekejeke Prolog memoing code. You need toinstall Jekejeke Minlog to have the module hypo available. Bestis to install the latest release:
:- 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 中的表格性能不均衡的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！