Scryer-prolog: Where is the time spent?

[triska]

As one benchmark, please download edges.pl from https://www.metalevel.at/clpb/scryer/edges.pl, and then consult the program:

:- use_module(library(clpb)).
:- use_module(library(assoc)).

:- use_module(edges).

pairs_keys_values([], [], []).
pairs_keys_values([A-B|ABs], [A|As], [B|Bs]) :-
        pairs_keys_values(ABs, As, Bs).

independent_set(*(NBs)) :-
        findall(U-V, edge(U, V), Edges),
        setof(U, V^(member(U-V, Edges);member(V-U, Edges)), Nodes),
        pairs_keys_values(Pairs, Nodes, _),
        list_to_assoc(Pairs, Assoc),
        maplist(not_both(Assoc), Edges, NBs).

not_both(Assoc, U-V, ~BU + ~BV) :-
        get_assoc(U, Assoc, BU),
        get_assoc(V, Assoc, BV).

As a test case, post the query:

?- independent_set(Sat), sat_count(Sat, Count).

After some time, it correctly yields Count = 211954906, which is the number of independent sets of this graph.

I hope this benchmark gives some useful indication regarding which portions of the engine are promising candidates for performance improvements.

[mthom]

Thank you for the benchmark! I will see if Rust has any good profiling tools. Or if I should just use perf.

[mthom]

Wow, I made a few simple changes according to some feedback from perf, and the runtime of the benchmark on my home machine went down from 1 minute to 40 seconds on the release build. I wonder what else I might be doing that's so needlessly expensive.

[triska]

Thank you for looking at this! It is worth thinking about this. When all is done, I expect a considerably improved runtime for this particular case.

On the other hand, please do not get carried away with micro-optimizations: It is much more important to first get the semantics right, such as for example #95, and to implement the features that are necessary for elegant Prolog code (#192).

Scryer is currently in a very good position in this sense, and I hope that maybe a few simple changes like the one you now applied will improve performance considerably for important use cases.

[XVilka]

For optimizing I recommend these:

• Criterion crate for microbenchmarking
• For performance profiling there is no better alternative to perf yet, see example with png
• Optimizing the heap allocation - see this article

[mthom]

There is probably quite a lot I can do to improve the use of the AND and OR stacks in Unsafe Rust. It might be time to merge them, I don't know. Are there benefits to keeping them separate?