Tabling: another core dump

Running this example from Stack overflow:


:- table posInt_CollatzSteps/2. 
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_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)
   ).

And this query:

2 ?- time(i0_i_maxSteps0_maxSteps(1,1 000 000,0,MaxSteps)).
[Thread 1 (main) at Wed Jun 19 22:46:21 2019] ../src/pl-trie.c:1234: find_var: Assertion
 failed: index == state->max_var_seen+1
C-stack trace labeled "assert_fail":
  [0] save_backtrace() at :? [0x7f09721abadf]
  [1] __assert_fail() at ??:? [0x7f09721e01c6]
  [2] unify_key() at :? [0x7f09721d9026]
  [3] trie_gen() at :? [0x7f09721db239]
  [4] pl_tbl_answer_update_dl2_va.lto_priv.0() at :? [0x7f09721db474]
  [5] PL_next_solution() at ??:? [0x7f09722685bc]
  [6] query_loop() at :? [0x7f097222d192]
  [7] prologToplevel() at :? [0x7f097222d26b]
  [8] PL_toplevel() at ??:? [0x7f0972279cae]
  [9] swipl(+0x1075) [0x55d3ede7b075]
  [10] __libc_start_main() at ??:? [0x7f0971f97ee3]
  [11] swipl(+0x10be) [0x55d3ede7b0be]
[1]    23511 abort (core dumped)  swipl

It works fine without tabling (albeit it takes a very long time).

I have updated my SO answer, to avoid some confusion. What the alternative solution does is not tabling, but rather trailed memoing. So I have renamed it from tabling to memoing. In trailed memoing when the query has finished, all results get lost.

The difference between trailed memoing is seen in the timing. There is no drastic difference between warm and cold runs in trailed memoing:

Jekejeke Prolog 1.3.8
with memoing: 0.724, 0.573, 0.585, 0.555

The above figures are little better than 3 years ago, since I have now inlining for disjunction and if-then-else. On the other hand tabling shows a much better amortisized effect, was just testing with SWI-Prolog tabling today:

SWI-Prolog 8.1.6
with tabling: 1.469, 0.172, 0.188, 0.187

So I was somehow comparing apples and oranges. That the tabling does not remove data after a query has been executed is seen here in the first run:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.6)

?- aggregate_all(count, current_table(_,_), N).
N = 0.

?- time(i0_i_maxSteps0_maxSteps(1, 100000, 0, R)).
% 10,203,889 inferences, 1.469 CPU in 1.494 seconds (98% CPU, 6947329 Lips)
R = 350.

?- aggregate_all(count, current_table(_,_), N).
N = 217212.

With latest git (8.1.8-25-g583b8636c):

103 ?- time(i0_i_maxSteps0_maxSteps(1, 1 000 000, 0, R)).
% 72,659,302 inferences, 12.005 CPU in 12.061 seconds (100% CPU, 6052541 Lips)
R = 524.

104 ?- time(i0_i_maxSteps0_maxSteps(1, 1 000 000, 0, R)).
% 5,000,001 inferences, 1.165 CPU in 1.169 seconds (100% CPU, 4290451 Lips)
R = 524.

These patches also fix Tabling: Core dump

Great! Tremendous response time. I think you surpassed Linus on this one :slight_smile: