Uneven tabling performance in BProlog 8.1

Question

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

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
   ).

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)
   ).

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

• w/o tabling: 6.784
• with tabling: 2.323, 19.78, 3.089, 3.084, 3.081

By adding :- table posInt_CollatzSteps/2. the queries got 2x faster. Still, I'm puzzled:

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

• w/o tabling: 14.287
• with tabling: 1.829, 0.31, 0.308, 0.31, 0.333

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.

Answer 1

Was checking against Jekejeke Prolog tabling. But could only go to n=100'000. For B-Prolog the following command line worked fine on windows:

bp -s 40000000

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:
w/o tabling: 14.276, 12.229
with tabling: 0.419, 0.143, 0.127, 0.152

The tabling code for Jekejeke uses the operator (<=)/2 from the module hypo. You need to manually add it to your code:

Jekejeke Prolog/Minlog n=100'000 in s:
w/o tabling: 20.271, 18.920
with tabling: 3.352, 2.879, 2.300, 2.719

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.

Bye

P.S.: This is the Jekejeke Prolog tabling code. You need to install Jekejeke Minlog to have the module hypo available. Best is to install the latest release:

/* with memoization */
:- thread_local posInt_CollatzStepsm/2.

mposInt_CollatzSteps(I,N) :-
   (  I == 1
   -> N = 0                                                % base case
   ;  posInt_CollatzStepsm(I,N)
   -> true
   ;  1 is I /\ 1
   -> I0 is I*3+1, mposInt_CollatzSteps(I0,N0), N is N0+1,   % odd
      <= posInt_CollatzStepsm(I,N)
   ;  I0 is I>>1,  mposInt_CollatzSteps(I0,N0), N is N0+1,   % even
      <= posInt_CollatzStepsm(I,N)
   ).