Add benchmarking suite to CI

[infogulch]

I think it would be helpful to run a collection of benchmarks as part of CI so we can immediately see how changes impact performance. As humans our immediate decision making is better guided by comparing our individual performance to our past selves rather than others (though occasional reality checks can be good too); adding benchmarks to CI is a good analogue for programs.

This breaks down into a few questions:

1. Where/how are the benchmarks performed?
2. Which metrics are measured?
3. Which benchmarks are run?

Some considerations:

• It should be easy to maintain, sustainable, and consistent. Benchmarks are most valuable with frequent measurements over long periods of time. This strongly suggests using public github actions runners.
• We should aim for the CI benchmark suite to take ~30m at most to make the most efficient use of public resources and minimize workflow completion latency.
• Consistently measuring wall clock time is notoriously difficult, and since GH action runners are run on shared infrastructure this excludes "wall clock time" as a primary metric due to variance. (Though we can measure it anyways.)
• Some metrics that may be more consistent (and therefore more easily comparable) could be: 1. WAM instructions / inferences (like those reported by swi's time/1), 2. instruction counts, 3. peak memory (?).

As far as which benchmarks would be appropriate I have no basis for an opinion. Instead I'll reference some past discussions that mention performance, many of which contain minimized reproductions that may be good candidates for benchmarks:

• Benchmarks #10
• Where is the time spent? #207
• Where is the time spent? (Exhibit 3) #315
• Where is the time spent? (Exhibit 4) #317
• Advice on Performance Tuning #974
• Modularity performance hit #979
• Where is the time spent? (Exhibit 5: Salsa20 core) #1094
• Slow numlist #1138
• Querying a predicate based on phrase_from_file is slow #1403
• Performance #1513
• My DCG is very slow to parse #1517
• Performance for LUBM benchmark #1521
• CLP(ℤ): (#\=)/2 is unexpectedly slow #1730

Thoughts?

[triska]

A very good idea!

A few further existing issues related to performance with contained benchmarks:

#315
#317
#1094

[UWN]

Would such a suite be also the place for space leaks?

[infogulch]

I guess the the requirement is that the metric is collectible and reliable enough to indicate incremental improvement.

Maybe you could indicate one or two candidates?

[infogulch]

Here's a rough implementation proposal.

The most straightforward way to run the benchmarks may be to do it at the process level.

As a sample benchmark for discussion, we can use edges.pl from #207:

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

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Contiguous United States and DC as they appear in SGB:
   http://www-cs-faculty.stanford.edu/~uno/sgb.html
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

edge(al, fl).
edge(al, ga).
edge(al, ms).
edge(al, tn).
edge(ar, la).
edge(ar, mo).
edge(ar, ms).
edge(ar, ok).
edge(ar, tn).
edge(ar, tx).
edge(az, ca).
edge(az, nm).
edge(az, nv).
edge(az, ut).
edge(ca, nv).
edge(ca, or).
edge(co, ks).
edge(co, ne).
edge(co, nm).
edge(co, ok).
edge(co, ut).
edge(co, wy).
edge(ct, ma).
edge(ct, ny).
edge(ct, ri).
edge(dc, md).
edge(dc, va).
edge(de, md).
edge(de, nj).
edge(de, pa).
edge(fl, ga).
edge(ga, nc).
edge(ga, sc).
edge(ga, tn).
edge(ia, il).
edge(ia, mn).
edge(ia, mo).
edge(ia, ne).
edge(ia, sd).
edge(ia, wi).
edge(id, mt).
edge(id, nv).
edge(id, or).
edge(id, ut).
edge(id, wa).
edge(id, wy).
edge(il, in).
edge(il, ky).
edge(il, mo).
edge(il, wi).
edge(in, ky).
edge(in, mi).
edge(in, oh).
edge(ks, mo).
edge(ks, ne).
edge(ks, ok).
edge(ky, mo).
edge(ky, oh).
edge(ky, tn).
edge(ky, va).
edge(ky, wv).
edge(la, ms).
edge(la, tx).
edge(ma, nh).
edge(ma, ny).
edge(ma, ri).
edge(ma, vt).
edge(md, pa).
edge(md, va).
edge(md, wv).
edge(me, nh).
edge(mi, oh).
edge(mi, wi).
edge(mn, nd).
edge(mn, sd).
edge(mn, wi).
edge(mo, ne).
edge(mo, ok).
edge(mo, tn).
edge(ms, tn).
edge(mt, nd).
edge(mt, sd).
edge(mt, wy).
edge(nc, sc).
edge(nc, tn).
edge(nc, va).
edge(nd, sd).
edge(ne, sd).
edge(ne, wy).
edge(nh, vt).
edge(nj, ny).
edge(nj, pa).
edge(nm, ok).
edge(nm, tx).
edge(nv, or).
edge(nv, ut).
edge(ny, pa).
edge(ny, vt).
edge(oh, pa).
edge(oh, wv).
edge(ok, tx).
edge(or, wa).
edge(pa, wv).
edge(sd, wy).
edge(tn, va).
edge(ut, wy).
edge(va, wv).

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).

run :- independent_set(Sat), sat_count(Sat, Count), write(Count), nl.

Memory

To get memory use we could use /usr/bin/time with the %M "Max memory" format, see: https://man7.org/linux/man-pages/man1/time.1.html

$ /usr/bin/time -f '%M' scryer-prolog edges.pl -g run,halt 1>/dev/null
217968

Instructions

For other metrics we could use perf. See: https://perf.wiki.kernel.org/index.php/Tutorial#Benchmarking_with_perf_bench We can use -x, to output csv for easier parsing. I bet the instructions:u field would be mostly stable, but we might as well capture most of these until we know what we want for sure. On WSL2 some metrics aren't supported but it looks something like the following:

$ perf stat -ddd scryer-prolog edges.pl -g run,halt >/dev/null

 Performance counter stats for 'scryer-prolog edges.pl -g run,halt':

           3167.74 msec task-clock:u              #    1.000 CPUs utilized          
                 0      context-switches:u        #    0.000 /sec                   
                 0      cpu-migrations:u          #    0.000 /sec                   
              6438      page-faults:u             #    2.032 K/sec                  
       12215306462      cycles:u                  #    3.856 GHz                      (44.39%)
       27669673831      instructions:u            #    2.27  insn per cycle           (54.57%)
        5529774631      branches:u                #    1.746 G/sec                    (54.90%)
          46609315      branch-misses:u           #    0.84% of all branches          (55.22%)
        7817404134      L1-dcache-loads:u         #    2.468 G/sec                    (55.54%)
         140631202      L1-dcache-load-misses:u   #    1.80% of all L1-dcache accesses  (55.82%)
   <not supported>      LLC-loads:u                                                 
   <not supported>      LLC-load-misses:u                                           
   <not supported>      L1-icache-loads:u                                           
         323206414      L1-icache-load-misses:u                                       (36.30%)
        7978264554      dTLB-loads:u              #    2.519 G/sec                    (36.02%)
            325966      dTLB-load-misses:u        #    0.00% of all dTLB cache accesses  (35.70%)
           8847152      iTLB-loads:u              #    2.793 M/sec                    (35.42%)
            563309      iTLB-load-misses:u        #    6.37% of all iTLB cache accesses  (35.41%)
   <not supported>      L1-dcache-prefetches:u                                      
   <not supported>      L1-dcache-prefetch-misses:u                                   

       3.167883362 seconds time elapsed

       3.108992000 seconds user
       0.060368000 seconds sys

Inferences?

As far as I know, time/1 doesn't output a ~deterministic counter like 'instructions'/'inferences', so it's not super useful here. Is there some way to get that metric?

---

As a start for CI, I'm imagining a simple script that runs these commands for each .pl file in some directory, collects the output metrics into some machine readable format, and publishes it as a github artifact for later consumption

Perhaps with something like https://github.com/benchmark-action/github-action-benchmark / https://github.com/marketplace/actions/continuous-benchmark

Thoughts?

[infogulch]

iai ¹ runs cargo bench benchmarks by directly measuring the number of executed instructions with cachegrind. This should be stable enough to run in CI.

Edit: it looks like iai is not being maintained, maybe iai-callgrind ²? Or calliper ³?

Footnotes

1. https://bheisler.github.io/criterion.rs/book/iai/iai.html ↩

2. https://github.com/iai-callgrind/iai-callgrind ↩

3. https://github.com/osiewicz/calliper ↩