Benchmarks

Selected programs have been tested in the HYPROLOG versions for different platforms and compared with other systems when relevant or possible. The programs tested are included in the collection of sample programs suppplied with the HYPROLOG system.

Software and hardware used

All tests have been made on a Macintosh Intel Core Duo, 2GHz, 2GB Ram running Mac OS X 10.4.11.

The following versions of Prolog and other systems have been used.

SWI-Prolog (Multi-threaded, Version 5.6.49); http://www.swi-prolog.org/
SICStus 3.12.8 (i386-darwin-8.9.1); http://www.sics.se/isl/sicstuswww/site/index.html
SICStus 4.0.4 (i386-darwin-8.11.1); http://www.sics.se/isl/sicstuswww/site/index.html
BinProlog, #11.20; http://www.binnetcorp.com/BinProlog/
SICStus4 metainterp refers to a straightforward metainterpreter for abductive logic programming;
see reference [2] below; executed under SICStus 4.0.1 (i386-darwin-8.9.1)
Asystem, Version Asystem 2.1 release: 20 november 2004; executed under SICStus 3.12.8 (i386-darwin-8.9.1); see reference [3] below.
CIFF, v4.0: 28/08/2006. See reference [4] below.
Smodels version 2.28; see reference [5] below.

Measured execution times

Test program Hyp. SWI.0.2 Hyp. SWI.0.2, non-opt. Hyp. SP3.0.2 Hyp. SP3.0.2, non-opt. Hyp. SP4.0.2 Hyp. SP4.0.2, non-opt. BinProlog SICStus4 metainterp Asystem CIFF Smodels
benchmarkDB 1.1 1.9 0.57 1.1 0.42 1.4 - 4.8 13 170 600
build15 6630 6760 3400 3430 3340 3360 - 195 - 2250
graph5 32 35 14 14 14 16 - - - 2880
superprinters 220 236 - 112 54 68 5 - - - -

Comments

For HYPROLOG, we have tested with (bold face) and without ("non-opt.") the optimization options described in the HYPROLOG User's Guide, which can be used to suppress generation of CHR rules known not to be used.

BinProlog contains a built-in version of assumptions, which is about 10 times as fast the fastest version of HYPROLOG. In previous publications, we mentioned an estimate of the slow-down factor of 3-5 based on tests performed on different hardware which was, thus, misleading.

Asystem and CIFF are systems for abductive logic programming based in metainterpretation. Asystem was developed under an earlier version of SICStus Prolog, which is the reason why programs build15 and graph5 could not be tested. Both Asystem and CIFF integrate the SICStus' clpfd solver, which is employed in the tests for the program graph5, whereas the tests in HYPROLOG use clpq.

Smodels is an answer set programming system, which as such is capable of executing abductive logic programs; however, its model construction strategy involves the unfolding of all possible ground instances of clauses in the program, which makes it prohibitively slow for any abductive problem of a certain size.

The reason which the metainterpreter the metainterpreter is faster that HYPROLOG for the build15 problem is discussed in reference [1] below; we expect that future improvements of CHR's use of indexing will change this.

References

  1. H. Christiansen. Executable specifications for hypothesis-based reasoning with Prolog and Constraint Handling Rules, Journal of Applied Logic, to appear 2008 or -09. Preliminary version available as pdf.
  2. A. C. Kakas, P. Mancarella, Database updates through abduction, in: D. McLeod, R. Sacks-Davis, H.-J. Schek (Eds.), 16th International Conference on Very Large Data Bases, VLDB, Morgan Kaufmann, 1990, pp. 650661.
  3. A. C. Kakas, B. V. Nuffelen, M. Denecker, A-system: Problem solving through abduction, in: B. Nebel (Ed.), IJCAI, Morgan Kaufmann, 2001, pp. 591596.
  4. P. Mancarella, F. Sadri, G. Terreni, F. Toni, Programming applications in CIFF, in: C. Baral, G. Brewka, J. S. Schlipf (Eds.), LPNMR, Vol. 4483 of Lecture Notes in Computer Science, Springer, 2007, pp. 284289.
  5. T. Syrjänen, I. Niemelä, The Smodels system, in: T. Eiter, W. Faber, M. Truszczynski (Eds.), Proc. of the Workshop Logic Programming and Non- Monotonic Logic, LPNMR, Vol. 2173 of Lecture Notes in Computer Science, Springer, 2001, pp. 434438