“This project utilizes the logic language Prolog to define rules that represent particular patterns and criteria within a graph, and then compares a variety of implementations, both logic and conventional. The logic implementations more than hold their own.”
“As can be seen from the figure, the different processors and different implementations vary wildly until about 1 million edges, where they all converge at about 200 cycles per inference before exploding upwards at about 4 million edges. The cause of this increase is unclear. As seen from Table 1, there is a wide range in both last level cache and memory bandwidth, thus excluding memory access resources as a likely candidate. We speculate that this jump is caused by something in the SWI-PROLOG implementation.”
“Using a multiplicity of metrics, we compare those implementations with multiple non-Prolog implementations that use a variety of different programming models. The Prolog source codes are simpler and vastly smaller than the more conventional forms, but are performance comparable, especially considering they are not parallelized like the others. Future work includes investigating the performance spike at 2 to 4 million edges, and using the builtin predicate asserta, which allows the addition of new clauses to the beginning of a database [3]. This would reduce the number of repeated queries and decrease the number of inferences made, improving efficiency. In addition, parallel versions of Prolog may further enhance performance.”
Any ideas about the “jump”? I wonder whether tabling would be useful? Maybe their suggested use of asserta is a way of simulating tabling.
I saw this paper a while ago and found it interesting but a little hard to see what was really going on. I, too, wondered if tabling might help. I (of course) thought it might but realized it would take more effort than I could afford at the time to download everything and try to understand and reproduce it. And then add tabling. SWI Prolog now has tabling so they might just try it with the code they have. But it may be the case that their SWI program(s) might need to be changed. They started with a somewhat naive implementation and then optimized it. The optimized form is likely to be less improved (if at all) by tabling.
I have no idea what they meant by saying they’d try to use asserta to speed it up.
I scanned it. It is a bit hard to see what is going on. The fact that there is a lot of different hardware involved does not make it any easier. The task is much like a SPARQL graph pattern. We compile that to a complex Prolog body, after which we do query optimization by reordering conjunctions based on graph statistics. That would be the first thing to try if I was to study this in details. I did not see a download link for the code and data. Did I miss something?
Using carefully crafted helper predicates and tabling could help.
The sudden loss of inferences per second hints at either less well functioning indexing or slowdown due to exhausting memory caching in the hardware. AFAIK there indexing should not deteriorate if the number of clauses grows. In another context we have used up to 60M clauses without a problem.
I didn’t know that SWI did query reordering. Is that part of your SPARQL interface, or is it more general?
Echoing Jan’s point, the XSB side, I’ve always fround working RAM to be the problem rather than indexing, at least up to about 200 million facts or table entries.
I did find a link to download the code. It is indeed as Jan suggests. There are two implementations, as mentioned in the paper: 1. One predicate to recognize each subgraph with one to put them together, and 2. One predicate, essentially the previous one unfolded, and slightly reordered, I think. Their measurements showed the second one somewhat faster, almost assuredly because of the reordering. The data in the download only went up to about 60K facts, so I didn’t try larger. (I believe there is a way to use python to create larger datasets, but I didn’t look into that.) XSB does solves the 60K fact problem in about 0.05 secs. Note that since the “optimized” form defines only one (non-recursive) predicate, so tabling can’t even be applied. It’s possible that tabling would help the “un-optimized” form, but I haven’t looked at it.
As another interesting (to me at least) paper on comparison of Prolog (XSB) with other declarative technologies for computing full transitive closure of a variety of graphs, Annie and a student wrote:
It compares XSB, Clingo, and Souffle on transitive closure and shows XSB to be almost always the fastest, often significantly faster. The one case XSB is slower turned out to be a problem in the default indexing in XSB that showed up in that particular case. When better indexing is used XSB is always fastest, I believe.
That is just part of the SPARQL implementation. It compiles the query to a Prolog goal, then reorders it and finally it executes. I wrote some ICLP paper about it long ago
