Turbo s(CASP)

Announce
1

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.

ProgramSWICiao
bec_light.pl0.251.83
birds.pl0.030.09
classic_negation_inconstistent.pl0.020.06
family.pl0.030.08
forall_arity.pl0.040.07
hamcycle.pl0.050.30
hamcycle_two.pl0.091.06
hanoi.pl0.131.06
pq.pl0.030.07
queens.pl2.1423.53
rat.pl0.030.06
vars.pl0.030.07
8 Likes