retina: Integrated RDF Surfaces inspired by Pat Hayes, Patrick Hochstenbach and EYE

[josd]

In phy we implement RDF Surfaces inspired by Pat Hayes, Patrick Hochstenbach and EYE using Scryer.

It is still premature but the examples already run fine :-)

Thanks a lot for Scryer!

[josd]

For the moment phy is on hold due to performance issues with https://github.com/josd/phy/tree/master/rdfsurfaces/lubm and https://github.com/josd/phy/tree/master/rdfsurfaces/edt
Running the latter gives

$ time scryer-prolog -g run ../../phy.pl edt.pl | tee edt-answer.pl
% phy v2.12.0 (2023-05-11)
'<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>'('<http://eulersharp.sourceforge.net/2009/12dtb/test#i100000>','<http://eulersharp.sourceforge.net/2009/12dtb/test#N100000>').

real    95m6.657s
user    95m3.068s
sys     0m3.531s

Running it with Trealla gives

$ time tpl -g run ../../phy.pl edt.pl | tee edt-answer.pl
% phy v2.12.0 (2023-05-11)
'<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>'('<http://eulersharp.sourceforge.net/2009/12dtb/test#i100000>','<http://eulersharp.sourceforge.net/2009/12dtb/test#N100000>').

real    0m3.152s
user    0m2.969s
sys     0m0.192s

[mthom]

I wonder if meta-predicates that instantiate goal arguments in clause heads should inline those arguments. phy follows a pattern whereby it binds a structure to a predicate argument variable and then calls the variable. As such, it doesn't benefit from Scryer's call inlining at all, and so goal expansion is invoked millions of times, many times for the same goals (not an exaggeration, I did some profiling of phy earlier today).

However, if those predicates were declared as meta-predicates with appropriate goal arguments, and we were to inline their expansions, it would benefit. ISO Prolog semantics would be completely preserved, of course.

The only developer burden would be extra meta-predicate declarations. Thoughts?

[triska]

With the latest git version, the situation looks much better in the sense that the meta-call now incurs only about 35% overhead (instead of yielding a more than 10-fold slowdown):

?- time((exp(18),true,false)).
   % CPU time: 0.654s
   false.

?- time((exp(18),a(true),false)).
   % CPU time: 0.883s
   false.

?- time((exp(18),b(true),false)).
   % CPU time: 1.071s
   false.

Calling true/0 directly (as in the first query) seems to have slowed down slightly though?

[josd]

With the latest git version, the situation looks much better in the sense that the meta-call now incurs only about 35% overhead (instead of yielding a more than 10-fold slowdown):

?- time((exp(18),true,false)).
% CPU time: 0.654s
false.

?- time((exp(18),a(true),false)).
% CPU time: 0.883s
false.

?- time((exp(18),b(true),false)).
% CPU time: 1.071s
false.
Calling true/0 directly (as in the first query) seems to have slowed down slightly though?

It is indeed twice as fast for https://github.com/eyereasoner/retina/tree/master/rdfsurfaces/edt

$ time scryer-prolog -g run ../../retina.pl edt.pl
% retina v4.0.1 (2023-06-06)
'<http://www.w3.org/1999/02/22-rdf-syntax-ns#type>'('<http://eulersharp.sourceforge.net/2009/12dtb/test#i100000>','<http://eulersharp.sourceforge.net/2009/12dtb/test#N100000>').

real    47m41.851s
user    47m38.141s
sys     0m3.680s

versus 95 minutes before, but that is still much longer than the 3 seconds with Trealla and SWI.

[triska]

I haven't yet looked at this specific example, but such extreme performance differences are often due to differences in the indexing mechanisms of different Prolog systems.

Scryer currently only indexes on the leftmost instantiated argument in clause definitions, the other arguments are not taken into account when using indexing to determine which clauses match. This can incur substantial overhead, because it means that an O(1) hash-based lookup can turn into an O(n) linear scan for matching clauses, which quickly leads to quadratic (or worse) overhead when conjunctions of goals are handled.

We previously had such an example, discussed in #1681, with a workaround based on term expansion to automatically generate clauses in different ways so that they best profit from indexing, combined with dynamic (manual) dispatch that invokes different versions based on instantiated arguments.

Scryer also currently does not perform deep indexing, and cannot quickly determine that only a single clause matches in examples such as:

p("a").
p("b").

?- C = a, p([C|_]).
   C = a
;  false. % redundant choice-point

[mthom]

Does Trealla use multi-argument and deep indexing, though? I know SWI does.

[triska]

Yes, Trealla does perform deep indexing, which can be very important for lookup in such large databases. For example, with:

f(g(a)).
f(g(b)).
f(g(c)).
f(g(c)).

I get:

?- f(g(c)).
   true
;  true.
?- f(g(b)).
   true.  % deep indexing, no alternative remaining

The indexing is so efficient that it even omits solutions:

?- f(g(X)).
   X = a, unexpected, incomplete.

I filed this as trealla-prolog/trealla#204.

For comparison, with Scryer Prolog, we get:

?- f(g(b)).
   true
;  false. % redundant choice-point

[josd]

Not sure if I understand it, but we need a solution that works in general, that is with any kind of RDF Surfaces just-in-time data. Can those meta-predicates be derived in general?

[pmoura]

It should be noted that, in most Prolog systems (and also in Logtalk), term- and goal-expansion are only performed at compile-time (SICStus Prolog is a known exception). For the rare cases where runtime expansion is required, there's always expand_term/2 and expand_goal/2.