Turbo s(CASP)

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

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
7 Likes