I’ve done some serious performance optimization for the SWI-Prolog
port of s(CASP). It boils down to these steps:
-
In addition to the current stack representation that both
captures the parents of the current goal and everything that
has been proved before we keep two new structures:-
The list of direct parents. We use this for the coinductive
derivations. This reduces the overhead of these derivations
about 30 times, from 30% of the total execution to 1%. -
Represent the proven goals in a Prolog assoc that maps from
Name/Arity to the relevant goals, e.g. p/1 may be associated
to [p(1), not(p(4)), …]. Use this for “proved” as well as
combining the new result with existing results as done in
check_CSH_. This provides an about 3 times speedup. -
Big speedup of translating the stack to a proper justification
tree.
-
The dominant performance bottleneck is now the term copying that happens
as part of the “forall” implementation which is responsible for over 50%
on many programs.
Enjoy --- Jan
Available from
- Source: GitHub - JanWielemaker/sCASP: top-down interpreter for ASP programs with constraints
- Online: SWISH -- SWI-Prolog for SHaring (Jason Morris)
- Service: s(CASP) web server
Timing
Below we compare the current versions on some of the bundled test
programs. Tests have been executed as scasp -n0 file.pl and for the
fast ones it mostly shows the program startup and closedown overhead.
* SWI-Prolog % s(CASP): version swi.0.21.11.26
* Ciao s(CASP) version 0.21.10.09
Note that this mostly compares the performance of the s(CASP) code and does not claim anything about the performance of SWI-Prolog vs Ciao.
| Program | SWI | Ciao |
|---|---|---|
| bec_light.pl | 0.25 | 1.83 |
| birds.pl | 0.03 | 0.09 |
| classic_negation_inconstistent.pl | 0.02 | 0.06 |
| family.pl | 0.03 | 0.08 |
| forall_arity.pl | 0.04 | 0.07 |
| hamcycle.pl | 0.05 | 0.30 |
| hamcycle_two.pl | 0.09 | 1.06 |
| hanoi.pl | 0.13 | 1.06 |
| pq.pl | 0.03 | 0.07 |
| queens.pl | 2.14 | 23.53 |
| rat.pl | 0.03 | 0.06 |
| vars.pl | 0.03 | 0.07 |