Uneven tab performance in BProlog 8.1

Question

I did some experiments with the tab capabilities of b-prolog version 8.1 and was very surprised at the performance that I observed.

Here is the code I used. He counts the number of Collatz steps N needed to reduce some positive integer I 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 ). 

To determine the maximum number of recovery 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) ). 

When did I run multiple queries ?- time(i0_i_maxSteps0_maxSteps(1,1000000,0,MaxSteps)). without tabulation and with tabulation, I observed the following time intervals (in seconds):

• no tab: 6.784
• with tab: 2.323, 19.78 , 3.089, 3.084, 3.081

By adding :- table posInt_CollatzSteps/2. , requests received 2x faster. However, I am puzzled:

• The second run is more than 5 times slower than the first. Apparently, most of the time is spent in the GC. Starting from the 3rd launch, the tab option is fast again.
• Warm runs (3rd, 4th, ...) are noticeably slower than a cold (1st) move.

I did not expect this! Compare this to the runtime that I observed with xsb version 3.6.0:

• without tab: 14.287
• with tab: 1.829, 0.31 , 0.308 , 0.31 , 0.333

What can I do? Are there any directives or flags that will help me improve the efficiency of working with BProlog? I am using the 64 bit version of BProlog version 8.1 with Linux.

Answer 1

Checked against Jekejeke Prologue trailed notes. It was collected only at n = 100'000. For B-Prolog, the following command line worked fine on Windows:

 bp -s 40000000 

This is said to be 160 MB stack / heap space. I get both warm and not set tables than cold ones:

B-Prolog n = 100'000 in s:
without tab: 14.276, 12.229
with tabulation: 0.419, 0.143, 0.127, 0.152

The storage code for Jekejeke uses the acceptz / 2 predicate from the hypo module. Unlike B-Prolog tables, tracked entries will recount everything with every call. You need to manually add it to your code:

Projection Yekeke / Minlog n = 100'000 in s:
without memorization: 4,521, 3,893
with memorization: 0.724, 0.573, 0.585, 0.555

Thus, there is still room for improvement in speed at Jekejeke. Regarding your question, B-Prolog: When the memory is too tight, this may occasionally put extra pressure on the GC, which can lead to your observed behavior.

bye

PS: this is the code to remember in Jekejeke Prolog. You need to install Jekejeke Minlog to have a hypo- accessible module. It is best to install the latest version:

 :- 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