BProlog 8.1中的制表性能不均匀 [英] Uneven tabling performance in BProlog 8.1

问题描述

我使用的制表功能进行了一些实验 b-prolog 版本8.1的问题我对观察到的性能感到非常惊讶.

I did a few experiments with the tabling capabilities of b-prolog version 8.1 and was quite surprised by the performance I observed.

这是我使用的代码.它计算了将一些正整数I减少到所需的 Collat​​z 步骤N的数量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

• w/o tabling: 6.784
• with tabling: 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，第4，...)比寒冷的跑步(第1)慢得多.

• The 2nd run is more than 5x slower than the 1st. Apparently most time is spend in GC. From the 3rd run onwards, the tabling variant is fast again.
• Warm runs (3rd, 4th,...) are noticeably slower than the cold (1st) run.

我没想到这一点！将其与我在

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

• w/o tabling: 14.287
• with tabling: 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，以下命令行可以正常工作 在Windows上:

Was checking against Jekejeke Prolog trailed memoing. Was only going to n=100'000. For B-Prolog the following command line worked fine on windows:

bp -s 40000000

据说这相当于160MB的堆栈/堆空间.我都得到 上桌和不上桌的热跑比冷跑更好:

This is said to amount to a stack/heap space of 160MB. I get both tabled 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

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的备忘录代码使用谓词假定z/2来自 模块假设.与B-Prolog制表相反，尾随的备忘录将在每次呼叫时重新计算所有内容.您需要手动将其添加到您的代码中:

The memoing code for Jekejeke uses the predicate assumez/2 from the module 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 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，可能会导致您观察到的行为.

So there is still room for speed improvements in Jekejeke. Concerning your B-Prolog question: When the memory is too tight, this might irregularily put additional pressure on a 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 to install Jekejeke Minlog to have the module hypo available. Best is 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中的制表性能不均匀的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！