Unexpected performance difference of two findall/3 methods (with some asserting/retracting)

General
1

Dear all,

I have some unexpected performance issues with SWI-Prolog. I have two approaches:

  • (A1) query
  • (A2) assert, query, and retract

Rather unexpectedly, A2 outperforms A1. I have included a toy example below. However, in this toy example, A1 is faster than A2. The example is only meant to illustrate the general problem.

pos_index(1,f(a)).
pos_index(2,f(b)).
pos_index(3,f(c)).

q(a,1).
q(b,1).
q(b,2).
q(b,3).
q(b,4).
q(c,3).
q(c,4).
r(1).
r(2).

test_ex(Atom):-
    call(Atom),!.

a1:-
    findall(ID, (pos_index(ID,f(A)), once((q(A,B), r(B)))), Xs),
    writeln(Xs).
a2:-
    assertz((f(A):- q(A,B), r(B))),
    findall(ID, (pos_index(ID,Atom),test_ex(Atom)), Xs),
    retractall(f(_)),
    writeln(Xs).

In my use case, I generate rules (such as f(A):- q(A,B), r(B)) and test them. In almost all cases, A2 is faster than A1, sometimes 0.01s faster. I am surprised as A2 has the extra work of asserting/retracting rules. A2

I have included timings from a larger problem:

time(findall(ID, (pos_index(ID,legal_checkermove(A,B,C,D,E,F)),once(( input_pawnmove(B,F,C,E,D),input_pawnmove(G,E,D,C,F),true_control(A,G)))), Xs)).
% 36,564 inferences, 0.022 CPU in 0.026 seconds (84% CPU, 1688089 Lips)

time((assertz((legal_checkermove(A,B,C,D,E,F):- input_pawnmove(B,F,C,E,D),input_pawnmove(G,E,D,C,F),true_control(A,G))),
|    findall(ID, (pos_index(ID,Atom),test_ex(Atom)), Xs),
|    retractall(legal_checkermove(_,_,_,_,_,_)))).
% 61,557 inferences, 0.009 CPU in 0.009 seconds (99% CPU, 6791372 Lips)

As you can see, although A2 has more inferences than A1, it is faster.

Q1. Why is A1 slower than A2? Is it because of the overhead of once/1?

Q2. Is there a faster approach?

In natural language, for a given rule (such as f(A):- q(A,B), r(B)) I want to find all the IDs covered by that rule. For instance, for the above case, I want to find [1,2].

Thanks!

2

SWI-Prolog’s meta calling works by compiling and than running if the goal is some control structure (as opposed to calling a simple predicate). So, in this case findall/3 compiles the conjunction. But, once/1 is another meta-call with a conjunction. So, for every solution of pos_index/2 it will go through the compile and run step again. The assert option avoids that (it is incorrect as it does not do once/1 or get the same effect using a !).

If you first load library(apply_macros) many meta calls are avoided and then a1 looks like below. Now findall/3 compiles the entire control structure, so this should be (a bit) faster.

?- listing(a1).
a1 :-
    findall(ID,
            ( pos_index(ID, f(A)),
              (   q(A, B),
                  r(B)
              ->  true
              )
            ),
            Xs),
    writeln(Xs).

Not sure I got everything right because the stuff to run the timing calls is lacking.

1 Like
3

@jan that works as expected now. Thank you for the explanation!