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