Linking from clause store to terms on the stack

Discussion
69

:slight_smile: no torture needed – you have a point – the comparison in practice needs to take into account the real additional feature of Prolog – that come along in the execution – so a simple C implementation doesn’t cut it.

And, I am looking for a high performance product-ready C/C++ graph library with all relevant such functions, to make a comparision with this.

But, again, I see alot of value understanding the mechanisms of Prolog under the hood and where one pays what price for its high-level capabilities.

My long term hope is that (SWI) Prolog will be executable as efficient as C – by either further improving the runtime, or adding novel new features – perhaps comparable to tabling – to enable the kind design control language like C/C++ provide without needing to go foreign and without giving up on Prologs high level language capabilities.

Dan

70

I think what would be needed to see what “actually” happens is a trace /debugger at the virtual machine level.

71

Well, depends what you are looking for. You can start by examining the compiled bytecode and reading the VM code that executes it. This is kinda necessary as a first step and probably enough for understanding things at the level at which you usually do your analyses of what Prolog does.

72

Well, you can look at the proof tree, but it will not tell you anything about the occurrence of implemented design choices that achieve performance and efficiency.

Jan had mentioned a few of them – related to how indexing works and that hashes are not always created and consulted (less than 17 predicates in a “hash set”,

The reuse of allocated choice point – so, they are not always created a fresh.

The manner the stack space of local variables are or are not reused during recursive calls.

Under what conditions choice points are or are not created

And, more like these …

Although as a first step I would be very happy to understand what VMIs are generated for what Prolog code

73

I offered to help to setup an experiment so that we can stop guessing and assuming and instead start seeing what actually happens. I don’t remember suggesting to look at a proof tree.

74

I must have misunderstood your earlier comment – thank you for clarifying.

76

SWI-Prolog’s JITI (Just-In-Time-Indexing) can generate hashes that include both fields, so there’s only a single lookup and potentially no backtrack points.
To see what it’s doing, run a sample query then look at the output from jiti_list/1.

If you want to find the adjacency list for node X, it’s just

adjacency(X, Adjacent) :-
    ( setof(Y, link(X,Y), Adjacent) -> true ; Adjacent = [] ).

(I used setof rather than findall to get the list in guaranteed order)

If it’s important for performance, you can use assertz/1 to cache the agency information; or you can use term-expansion when you read in the data.

77

Thank you Peter,

You know, it would be great to have a high performance Prolog guide – where all those insights are listed.

The code is great, but it gives no hint as to the performance optimizations – that is actually done.

What worries me a bit is the “can generate hashes” – is there a way to know by design that it will generate those hashes.

Markus has a great video tutorial where he shows how to design predicates so that choice points are eliminated – the same kind of guidance would be great for other aspects – including indexing and tabling.

Dan

78

In my experience, it does generate appropriate indexes. It’s easy to check – just do a query where the appropriate arguments are ground (it doesn’t matter whether the query succeeds or fails) and look at what jiti_list/1 tells you.

For example, here’s some set-up code I do on a 643,363 clauses, to create the indexes before starting the http server:

setup :-
        concurrent_maplist(index_pred,
            [kythe_node(sig,_,_,_,_,_,_),                       % kythe_node/7 1
             kythe_node(_,_,_,path,_,_,value),                  % kythe_node/7 4+7
             kythe_node(_,_,_,_,_,fact,value),                  % kythe_node/7 6+7
             kythe_edge(sig,corpus,root,path,lang,_,_,_,_,_,_), % kythe_edge/11 1
             kythe_edge(_,_,_,_,_,_,sig,corpus,root,path,lang), % kythe_edge/11 7
             kythe_edge(_,_,_,_,_,lang,sig,corpus,root,path,lang), % kythe_edge/11 6
             kythe_edge(vname(sig,corpus,root,path,lang),_,_),  % kythe_edge/3 1
             kythe_edge(_,_,vname(sig,corpus,root,path,lang)),  % kythe_edge/3 1
             kythe_edge(vname(sig,corpus,root,path,lang),edge,_),
             kythe_edge(_,edge,vname(sig,corpus,root,path,lang)),
             kythe_edge(_,edge,_),
             kythe_color_line(corpus,root,path,lang,_,_),       % kythe_color_line/6 3
             kythe_color_line(corpus,root,path,lang,0,_)        % kythe_color_line/6 3+5
            ])),
     ...

%! index_pred(:Goal) is nondet.
% Call a single Goal and ignore its result - this forces a building the index.
index_pred(Goal) :-
    statistics(process_cputime, T0),
    ( Goal -> true ; true ),
    statistics(process_cputime, T1),
    T is T1 - T0,
    debug(log, 'Indexed ~q in ~3f sec', [Goal, T]).

%! show_jiti is det.
show_jiti :-
    strip_module(kythe_node(_,_,_), Module, _),
    jiti_list(Module:_),
    findall(S, kythe_node(S,_,_,_,_,_,_), Sigs),
    length(Sigs, LenSigs),
    sort(Sigs, SigsSorted),
    length(SigsSorted, LenSigsSorted),
    debug(log, 'kythe_node(Signature) in ~q: ~d entries, ~d unique.', [Module, LenSigs, LenSigsSorted]).

which wrote this to the log:

% [Thread  6 10:43:02]  Indexed kythe_color_line(corpus,root,path,lang,_48,_50) in 0.694 sec
% [Thread  9 10:43:02]  Indexed kythe_edge(_40,edge,_44) in 0.972 sec
% [Thread 15 10:43:02]  Indexed kythe_color_line(corpus,root,path,lang,0,_50) in 1.026 sec
% [Thread  3 10:43:02]  Indexed kythe_node(sig,_42,_44,_46,_48,_50,_52) in 1.276 sec
% [Thread 13 10:43:02]  Indexed kythe_edge(vname(sig,corpus,root,path,lang),_42,_44) in 2.039 sec
% [Thread  5 10:43:02]  Indexed kythe_edge(sig,corpus,root,path,lang,_50,_52,_54,_56,_58,_60) in 2.050 sec
% [Thread 10 10:43:02]  Indexed kythe_edge(vname(sig,corpus,root,path,lang),edge,_44) in 2.320 sec
% [Thread  8 10:43:02]  Indexed kythe_edge(_40,_42,vname(sig,corpus,root,path,lang)) in 2.430 sec
% [Thread  7 10:43:02]  Indexed kythe_edge(_40,_42,_44,_46,_48,_50,sig,corpus,root,path,lang) in 2.433 sec
% [Thread 12 10:43:02]  Indexed kythe_edge(_40,edge,vname(sig,corpus,root,path,lang)) in 2.524 sec
% [Thread 14 10:43:02]  Indexed kythe_node(_40,_42,_44,_46,_48,fact,value) in 2.553 sec
% [Thread 11 10:43:02]  Indexed kythe_edge(_40,_42,_44,_46,_48,lang,sig,corpus,root,path,lang) in 2.562 sec
% [Thread  4 10:43:02]  Indexed kythe_node(_40,_42,_44,path,_48,_50,value) in 2.575 sec
Predicate                                     Indexed  Buckets Speedup Flags
============================================================================
src_browser:kythe_edge/11                       1        131,072 11794.7   
                                                7        131,072 11794.7   
                                                6           16     5.2   
src_browser:kythe_color_line/6                  3+5      65,536 40332.0   
                                                3          256    45.7   
src_browser:kythe_node/7                        1        262,144 60698.5   
                                                4+7      262,144  4507.3   
                                                7        131,072  1090.0   
% [Thread 1 10:43:03]  kythe_node(Signature) in src_browser: 348365 entries, 136252 unique.
% [Thread 1 10:43:03]  JIT index done.