XSB

XSB Prolog is a well-known deductive system with a long experience in efficiently implementing Prolog evaluation with tabling.

xsb 3.8 is built calling cd build && ./configure && ./makexsb.

For xsb we can measure the resource usage using /usr/bin/time.

tcff

We ran our tests loading the data with load_dync and enabled subsumtive tabling, and a trie index on the par relation.

% tcff.P
:- index(par/2, trie).
:- use_subsumptive_tabling tc/2.
tc(X,Y) :- par(X,Y).
tc(X,Y) :- par(X,Z), tc(Z,Y).
bench :- tc(_,_), fail.
bench.
test(FileName) :- load_dync(FileName), bench.

Launch : xsb -e "['tcff.P'], test({instance}), halt."

sgff

In general the same generation query for xsb looked like the following:

% tcff.P
/* Data load method: */
load_data(Filename) :- load_dync(Filename).

/* Index for the given database relation (edges of the graph): */
:- index(par/2, trie).

/* Tabling method: */
:- table sg/2 as subsumptive.

/*-----------------------------------------------------------------------------
 * Benchmark Program:
 *-----------------------------------------------------------------------------
 */

sg(X,X) :- par(_,X).
sg(X,Y) :- par(X,A), sg(A,B), par(Y,B).

/*-----------------------------------------------------------------------------
 * Benchmark Query:
 *-----------------------------------------------------------------------------
 */

bench :- sg(_,_), fail.
bench.

But we did try the following combinations of settings and chose the best one.

load_data(Filename) :- load_dyn(Filename).
:- index(par/2, [1,2]).
:- table sg/2 as variant.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, [1,2]).
:- table sg/2 as variant.
load_data(Filename) :- load_dyn(Filename).
:- index(par/2, [2]).
:- table sg/2 as variant.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, [2]).
:- table sg/2 as variant.
load_data(Filename) :- load_dyn(Filename).
:- index(par/2, [2,1]).
:- table sg/2 as variant.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, [2,1]).
:- table sg/2 as variant.
load_data(Filename) :- load_dyn(Filename).
:- index(par/2, trie).
:- table sg/2 as variant.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, trie).
:- table sg/2 as variant.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, [2,1]).
:- table sg/2 as subsumptive.
load_data(Filename) :- load_dync(Filename).
:- index(par/2, trie).
:- table sg/2 as subsumptive.