Clause lookup with Reference vs term lookup w/ first argument

Help!
1

Hi,

Suppose have alot of dynamically asserted facts such as:

fact(id1, val1).
fact(id2, val2).

Suppose I look up a fact via:

lookup(ID, Val) :- fact(ID, Val).

Now, instead I lookup fact as so:

lookup(RefID, Val) :-
clause(fact(ID, Val), true, RefID).

which of the two lookups would be faster – is the second lookup more “direct” like a pointer – or does it also go through a hash index as the first one.

thanks,

Dan

2

This is interesting. It seems you could just use fact/2?

This is even more surprising. What is your use case?

If you could share the code that you use to benchmark those, it might be easier to understand what you are after?

3

I want to create a graph like structure and link one node to the next via something as close as pointers – to avoid going through hashtable lookup of the prolog KB.

Also, i want to avoid externalizing this to c code.

4

If RefID is a clause reference as produced by asserta/2 and friends, there is no hash lookup for finding the associated clause. But, clause/3 is probably slower than normal calling. You’d have to do the timing, but my guess is that the normal Prolog thing probably wins (and is in general a lot easier to deal with).

I think the four options for a graph are:

  • Use Prolog terms, linking the parents and/or children as arguments. You have direct pointers and a backtracking graph. If the graph is big this will probably slow down, notably due to GC cost. SWI-Prolog still doesn’t have generational GC (trying to avoid looking at old data).
  • Use the Prolog database as t(parent, child) with as many additional info you want to add (relation name, other relation properties).
  • Use the RDF store. This has some advantages compared to Prolog, but with the improved indexing of todays Prolog, these advantages start to disappear. At the moment it is probably slower, but does use less memory.
  • Something external.
1 Like
5

Hi Jan,

Thank you.

We had this line of discussions many times – and i keep getting back to it as I review my code.

I very much want to stay within Prolog but want the efficiency of C++ pointers for structures that are best represented as directly linked.

I am wondering if its possible to create a new kind of primitive data structure that is optimized for creating truly linked structures (and support for backtracking).

The most primitive could be perhaps be directed_linked(A,B). which is implemented as a true pointer lookup from A to B – but not from B to A. Or bi_directed_linked(A,B), which has pointers in each direction.

If both A and B are unbound, it may not be supported – or this reverts back, somehow, to term lookup.

Does this make sense?

Dan

p.s. an extension could be linked(A,B, W), with W an arbitrary primitive or compound term – to associate some value to link.

6

I think it makes little sense. Whatever you want to do is ultimately based on the 4 options is outlined. The rest is syntactic sugar anyone can add. The only thing worth considering would to be add undo/1 which would allow you to push arbitrary goals onto the trail stack that get called during backtracking. That would allow creating backtracking data structures that are not hosted on the Prolog stacks. Such a thing is available in several Prolog systems. So far I ignored it as most scenarios have reasonable alternatives and the implementation of undo/1 is rather involved.