There’s also a high cognitive overhead in figuring out how to use these in C++ (plus proper use of unique_ptr, references, move semantics, and friends); also adding/deleting items can be tricky because of the need to also modify back-links. (I once had to deal with an object databases, and it turned out to be a nightmare when dealing with deletions; on the other hand, OQL was rather nice, compared to SQL.)
I think you want to distinguish here between a first look up and a rest lookup – and that’s is, i think, a key difference between Prolog and C
Consider a graph with adjacent nodes.
- Given a node ‘a’, the first lookup is a map lookup to get from the symbol name to the memory holding that node.
I.e. a C solution will have to manage a map like Prolog does to get from a symbol to the memory reference holding its data structure.
- once a reference to the memory cell is held, the next lookup step in C now relates to the data structure holding the adjacency list for that node – this is an iteration over a linked list or, even an array – which is where the speed comes in.
However, in Prolog, every adjacency hop is another hash lookup.
link(a, b).
link(a, c).
link(a, d)
Note: to retrieve link(a,c) requires in Prolog:
i) create choice point prior to retrieving via hash link(a,b)
ii) fail link(a,b),
ii) backtrack
iii) new hash lookup for link(a,c)
iv) create new choice point for link(a,c)
vs.
Ref1 → [a | Ref2 ]
Ref2 → [b | Ref 3]
Ref3 → [c | nil]
Requires in C:
i) hash lookup ‘a’ to get Ref1
ii) next memory structure read of Ref2 – in memory structure read
iii) read of b - pointer lookup
Clearly, Prolog does more housekeeping to get to the next adjacent node of ‘a’ and requires multiple hash lookups
Now, if you can store meta data in the adjacency list as well, that selects only those adjacent nodes to look up further that are relevant – the saving can be further increased – whereas in prolog you have to hash lookup the next adcent to know if its relevant or not.
Dan
Could you give a couple of pointers how one can discover this on their own? Like, the Prolog code you used to test this, how exactly to find what it compiles to, and what the VM than does with the byte code? To be honest this would be a tremendously useful walkthrough for an advanced beginner who would like to acquire deeper knowledge of the SWI-Prolog implementation.
This is based on my mental model of how Prolog operates – and I envisioned that
findall(X, link(a, B), Xs) would compile to.
Can someone decipher this, to see if my mental model aligns:
link(a,b).
link(a,c).
link(a,d).
?- vm_list(findall(X, link(a, X), Xs)).
========================================================================
findall/3
========================================================================
0 s_lmqual(1)
2 s_trustme(clause(97566464))
----------------------------------------
clause 1 (<clause>(0000000005D0BF00)):
----------------------------------------
0 i_enter
1 l_nolco('L1')
3 l_nil(3)
5 i_lcall('$bags':findall/4)
L1: 7 b_var0
8 b_var1
9 b_var2
10 b_nil
11 i_depart('$bags':findall/4)
13 i_exit
and
?- vm_list(link(a, X)).
========================================================================
link/2
========================================================================
0 s_virgin
1 i_exit
----------------------------------------
clause 1 (<clause>(000000000C12B760)):
----------------------------------------
0 h_atom(a)
2 h_atom(b)
4 i_exitfact
----------------------------------------
clause 2 (<clause>(000000000C12C090)):
----------------------------------------
0 h_atom(a)
2 h_atom(c)
4 i_exitfact
----------------------------------------
clause 3 (<clause>(000000000C12C330)):
----------------------------------------
0 h_atom(a)
2 h_atom(d)
4 i_exitfact
true.
Why does vm_list(link(a,X)) pre-generates three clauses – i.e. is this how its done internally – all potential matches are generated upfront as VMI ?
Edit:
get_a(X) :-
link(a, X).
?- vm_list(get_a).
========================================================================
get_a/1
========================================================================
0 s_virgin
1 i_exit
----------------------------------------
clause 1 (<clause>(00000000082AEE00)):
----------------------------------------
0 i_enter
1 b_atom(a)
3 b_var0
4 i_depart(user:link/2)
6 i_exit
true.
Looks like clause 1 above is simply a call to link/2with the first argument the atom a, and a second argument and unbound variable. b_var0.
I wish there was a guide for VM instructions — that would be super helpful
Dan
This is a great start. I am not sure what exactly we are looking for. I would think that if we want to know “how does prolog find the edge a → c” we might set it up like this:
% maybe some edges above
edge(a, b).
edge(a, c).
edge(a, d).
% and more edges below
edge_a_c :-
edge(a, X),
X == c.
I am not sure if the edge_a_c needs to be written like this. I am imagining that this will defeat the JIT indexing on the second argument but this would have to be confirmed first. And obviously if you want to check that the edge a → c exists, then this would be a different question.
But in principle, do you think that this is what we should be looking at?
I think the code you wrote – and any such trace, gives a first hint …
I think, if you really want to understand what is going on under the hood, you have to look at this through the lense of the virtual machine instructions - – those that are generated – and how they are then processed by the executive / supervisor function – you can’t simply do a Prolog trace, since you then skip most of the interesting stuff.
? No. ?- link(a,c). does a hash lookup. If the result is an empty bucket it fails. If the result is a bucket with one clause it runs the clause without creating any choicepoints. If the result is a bucket with more clauses it creates a choice point pointing at the next clause and runs the first.
The indexing is JIT. That as been discussed often enough. In this case it will look at the first argument, conclude indexing makes no sense (all the same), try the second argument to conclude a good index can be created (well, hashing currently only happens with >16 clauses)
So, the structure (shape) of the graph plays a key role here:
If there are millions of nodes many with “fanout” of less than 16 adjacency nodes, the the second lookup is often going to be a linear search. The first lookup (to get at the first clauses with ‘a’ as first argument, would be a hash in any case).
So the amended step by step process is as follows:
i) create choice point prior to retrieving via hash link(a,b) – if there are many links(X, Y) and X is/was unbound at call time
ii) fail link(a,b),
ii) backtrack
iii) new hash lookup for link(a,c) – if fanout is > 16, otherwise identify link(a,c) through linear search in the fact base – (I guess, facts with common first argument are somehow linearly related – an array perhaps.
iv) create new choice point for link(a,c)
So, a key overhead in Prolog (relative to a C implementation) is the backtrack mechanism (backtrack, create choice point to next next, access linearly next)
So, the same choice point is reused – which is a saving in new allocation, but some data is different – it has to point to a different next clause – and backtracking has to occur. Is this correct?
Before we start looking at compiled byte code and so on we would have to figure out what it the particular use case that we want to really look at, and what would be the Prolog code that we implement it with. Because apparently we can make any number of assumptions about everything, but our goal now (I thought) is to figure out what is actually happening, without having to guess what others think, or what the code does.
True.
So, the specification is a directed graph with adjacent nodes, fully normalized – as you often have suggested – and an algorithm that searches from node X across all adjacent nodes, say depth or breadth first or by use of adjacent selection criteria, a target node – say, a node having a certain symbolic name.
The question is when the algorithm is implemented in C where the graph is stored as pointers – would Prolog perform equivalently – disregarding for now garbage collection.
Dan
This is already a task almost too big to be useful for a walk-through, at least if neither of us has done this before. Do you want to check if a path exists between two known nodes? Does it have to be shortest path?
I thought as a first small exercise we might take it easy, maybe, what steps does Prolog take if you want to find if two nodes are adjacent (where “adjacent” means that if adjacent(a, b), then adjacent(b, a) does not follow automatically; is that right? or do you want an undirected graph?)
And as you know, even something as simple as “graph stored as pointers in C” is non-trivial. What are your data structures? If a node is a data structure that maintains a value at that node and a “list of pointers to adjacent nodes”, what is that list, really? Is it a singly-linked list? Is it an array? If it is an array, do you have to re-allocate it if it happens to grow? And if the topology of the graph does not change, why use pointers at all?
Sorry for being unclear, I wanted to write “graph stored as pointers in C”, not in Prolog.
Yes, to me it would seem that the “Guido Van Rossum” approach should be “equivalent” to the idiomatic way of doing it in Prolog.
Good idea.
Here is a simple graph implementation. I tried it out using an online IDE (Compile and run the code with online compiler and IDE | CodeChef) and it works.
If i read this correctly, the graph is essentially designed as follows:
- a vertex is represented / identified by an integer
- graph is an array of adjacency lists – a head of an adjacency list is simply a pointer to a first node in the list
- an index into the graph array represents a vertex and its adjacency list
- an adjacency list a linked list of node,
- each node holds a data item – an integer representing a vertex and a pointer to a next adjacent node
I guess, instead of having an integer represent a node, and could use pointers, and an node in an adjacency list would hold a pointer to a vertex – or be the vertex itself – which holds its adjacency (linked) list as well.
And instead of having an array to hold all vertices as index, one could use a hash table to map between a vertex name to a vertex – which in turn holds its adjacency list of vertices. Note, that hash would only be used once to identify the first vertex given an atom or string name of the node-- after that its always following the pointers.
But, lets analyze access performance of the current code:
Given a vertex V=4:
- a first lookup would be an array lookup (essentially pointer add arithmetic)
- then each adjacent would be a linked list item lookup of a node
- then each node is accessed to retrieve the next vertex - an integer in this case
- then this is used to lookup in the array again to get at the next adjacency list of that vertex
Lookups are always pointer lookups essentially
Did, i read this correctly
Lets now compare it with Prolog and a fully normalized adjacency list.
Edit:
There is btw some little overhead in the search algorithm which needs to track where in the adjacency list one is during, say, depth first search – that’s, i think, is the “cursor” @j4n_bur53 had mentioned earlier – I guess these are local variables used during the search – which would end up on a stack, if this is recursively searched.
Dan
Say, a depth first search
I will have to read more carefully through this code. Some of it looks a bit fishy. At the very least, it seems that finding a particular node requires traversing the singly linked “adjacency list”. So if you are trying to find a path, you need to do a linear search through the adjacency list at every step. So this is basically O(n), and not O(1).
I also see new winking at me at line 57 but no delete 
so I guess this rudimentary implementation is a bit rudimentary.
We anyway got very distracted. I really would have liked to try and see what actually happens when we traverse the adjacent nodes. Quoting myself:
I will anyway do this as an exercise, when I find the time. I was just hoping that @grossdan will help me do it, I am not too self-driven.
This code is simply an illustration to help visualize how adjacent nodes could be accessed via pointers and an array lookup.
I think this should suffice to compare it with a similar lookup in Prolog, where some of it will be hash lookups, and others a linear search if there are less than 17 adjacency predicates while hash lookups when more.
Also, the algorithm in prolog will have backtracking to access a next node, while the algorithm in C will have a next pointer lookup.
Below is how the algorithm in C for depth first search might look like. I will try to write it up later today …
I am assuming no cycles, otherwise you would, for example, maintain a visited list you pass along, and test it, an addition quite like in prolog might do.
// given a graph, a starting vertex:src, do a dfs until you identify the destination vertex dest
// 1. if src has no adjacency then end, report not (yet) found
// 2. retrieve the adjacency head of src
// 3. if head = dest, done, end, report found
// 4. otherwise, search dfs for that node
// 5. if failed, and unless last node, – otherwise report end and success
// 5.1 go to next node n
// 5.2 do dfs for n
// 6. if failed, report failure, else, report success
I think an algorithm above simply makes use of repeated pointer lockups to advance in the graph, first to identify a vertex adjacency list, and then each node in the adjacency list
True no proof.
If i seek proof, i would indeed implement it fully and test it with a 1M node and link graph – which I will likely do in the end-- but, I think one can discuss the architecture / design of two systems to compare them as well – qualitatively.
The difference in approach (hash, linear search, backtracking, VMIs, vs. array, pointers arithmetic and access, recursive calls in C), should be indicative if the implementations in each system is very different.
Also, a comparision side by side is very instructive to better understand both designs