paul@corto.laas.fr (Paul Freedman) (12/22/89)
Some months ago, I posted a request for information about
the consequences of using assert/1, retract/1, etc. on the
runtime speed of a Prolog program.
I have just completed some tests here at LAAS
(Laboratoire d'Automatique et d'Analyse des Systemes)
with C-Prolog (version 1.5), BIM (version 2.2 15-Jan-1988),
and Quintus (version 2.4.2 for Sun-3, SunOS 3.5),
and I thought that other people might be interested in
a short summary of the results.
A 12 page technical report with all the details is also available.
Please send me e-mail with your old technology address :)
and I'll mail you a copy.
---------------------------------------------------------------------------
Although the built-in database predicates assert/1 and retract
fall outside the strict definition
of logic programming, they provide a means to
naturally describe the evolution of a system
in terms of retracting the current `state', updating it in some way,
and then asserting the new `state'.
And when a data structure must be modified by multiple predicates,
it's often more convenient to maintain it in the form of
a ground predicate, rather than passing it from predicate
to predicate as an argument.
In addition, assert/1 and retract/1 can also be used in a general way
to obtain all possible assignments of arguments
which satisfy a given predicate.
For example, findall/3 defined in (Clocksin and Mellish 1981)
first asserts each possible assignment as an atom, then
forces Prolog to backtrack to find all the other
possibilities, and finally retracts them all to obtain a list
of all the assignments.
It was in this spirit that I first wrote some 2000 lines of code
in C-Prolog (for the sequencing analysis of robotic workcells).
But I soon discovered that examples of a practical size could not be analyzed,
and this was the motivation to consider re-coding for some other
Prolog available at LAAS.
---------------------------------------------------------------------------
Three variants on the same theme were used; in all cases,
the idea was to create a database of N atoms, collect them in
the form of a list, and then delete them.
Two database sizes were chosen: N = 1000, and N = 10,000.
The variants for each Prolog environment were the following:
1. via the basic built-in predicates assert/1, retract/1,
and a simple user-defined predicate append/3 taken from
(Clocksin and Mellish 1981):
append([[]],L,L):- !. /* 1st list is the empty list */
append([],L,L):- !. /* 1st list is the null list */
append([H|T],L1,[H|L2]):- append(T,L1,L2).
2. via the meta-level built-in predicates
setof/3 and retractall/1
3. via via the meta-level built-in predicates
bagof/3 and retractall/1
Since C-Prolog does not provide
retractall/1, an equivalent predicate was user-defined
in terms of retract/1:
retractall:- retract(predicate(_)), fail.
retractall.
Before presenting the test results, a few remarks about
the three Prolog environments are in order.
* Programs can be compiled under Quintus and BIM, but not C-Prolog.
* Only Quintus performs sophisticated memory
management by re-allocating memory in a dynamic way
among the various stacks.
The C-Prolog and BIM environments are static and require
careful initialization for large programs.
* C-Prolog and Quintus both use standard `DEC-10' or `Edinburgh'
style syntax; BIM does not (despite the so-called
`compatibility' switch).
For example, the standard syntax requires that variable names
begin with an upper case letter eg. `Temp'
(and predicates with a small letter);
under BIM, a variable must begin with an underscore and then
either a lower case or upper case letter eg. `_temp' or `_Temp'.
Such syntactical differences pose problems when porting programs
from one Prolog environment to another.
* Finally, both C-Prolog and BIM provide built-in predicates
for timing the execution of a predicate, in the form of
a `clock' which can be `read' before and after executing a predicate.
For Quintus, an external function was written based on the C function
``times''.
---------------------------------------------------------------------------
First, a summary of the test results for the two interpreted
environments: C-Prolog, and Quintus.
Prolog Database Program Create DB Collect/Delete DB
----------------------------------------------------------------------
----------------------------------------------------------------------
C-Prolog Sun-3 1000 1. 1.2 5.1
2. 19.0
3. 7.0
---------------------------------------------------
10000 1. 12.3 180
2. NA
3. 200
----------------------------------------------------------------------
Quintus Sun-3 1000 1. 2.2 3.6
2. 2.5
3. 2.0
---------------------------------------------------
10000 1. 29 225
2. 39
3. 19
----------------------------------------------------------------------
C-Prolog Sun-4 1000 1. 0.37 2.1
2. 6.8
3. 2.5
---------------------------------------------------
10000 1. 3.6 107
2. NA
3. 95
Now a summary of the test results for the two compiled
environments: BIM and Quintus.
Prolog Database Program Create DB Collect/Delete DB
----------------------------------------------------------------------
----------------------------------------------------------------------
BIM Sun-3 1000 1. 2.5 0.7
2. 82
3. 2.4
---------------------------------------------------
10000 1. 200 7.2
2. NA
3. 26
----------------------------------------------------------------------
Quintus Sun-3 1000 1. 1.4 2.3
2. 2.4
3. 1.7
---------------------------------------------------
10000 1. 15.7 165
2. 26
3. 18
---------------------------------------------------------------------------
Comparisons among the three different Prolog environments are
difficult to make, and the following comments are strictly my own.
C-Prolog is the most research-oriented Prolog, in that
it offers just an interpreter and essentially creates a single
executable environment from any number of consulted (or re-consulted)
input files.
No special checking is performed to catch conflicting predicate
definitions, or definitions spread over several input files.
The documentation is basic but for the most part, well written.
The results in the first table indicate that
the C-Prolog programs generally execute 3 times faster on the SPARCstation
for the database of 1000 items, and about 2 times faster
for the database of 10,000 items (for which the increased performance of
the CPU is limited by the size of the swap space).
In contrast, Quintus is the most production-oriented Prolog,
in that predicates may be interpreted or compiled (and mixed
within a single executable environment),
there are many kinds of predicate checking,
and there is a convenient interface to the EMACS editor;
the documentation is complete and well-written.
In addition, the meta-level predicates setof, bagof, retractall
have been specially optimized for speed.
Because it follows in the C-Prolog (and DEC-10 Prolog) tradition,
Quintus also offers a standard syntax.
But the extra checking (which is important for
developing a commercial product)
makes Quintus more constraining than
C-Prolog for research work.
Finally, BIM has an orientation somewhere between C-Prolog
and Quintus.
Unlike C-Prolog and Quintus Prolog,
BIM departs from the `standard' syntax, and this makes it difficult to port
programs written for other Prologs.
The documentation is incomplete, and sometimes difficult to follow.
Like Quintus, it offers a compiler (which runs more quickly
than the Quintus compiler), but the meta-level predicates
run more slowly.
However, the basic built-in predicates execute
more quickly under BIM than Quintus.
This advantage in raw speed was explained in a previous
posting to this newsgroup by Richard O'Keefe (18 october 1989).
The BIM compiler produces native code; the Quintus compiler does not.
This means that code compiled by BIM will execute faster,
but cannot be moved among machines with different base
architectures eg. among Sun-3, Sun-4, and VAX.
Native code also tends to be bigger, requiring more memory, which
might be important for programs which create large dynamic structures
running on memory-limited machines.
---------------------------------------------------------------------------
I finally opted to re-code those parts of my C-Prolog system
which made significant use of assert/1, retract/1, and
as a consequence, performed poorly (or not at all) on
examples, in Quintus.
In each case, the re-coding followed similar lines.
Use of assert/1, retract/1 to obtain all possible
assignments of arguments which satisfy a given predicate
were re-coded using the bagof/3
(and retractall/1 where required).
In addition, predicates which destructively manipulated
i.e. retracted, modified, re-asserted,
a common data structure (most often lists, or lists of
sublists), were re-coded so as to incorporate the data
structure as an additional argument which could be passed
between predicates.
In another posting to this newsgroup
(25 october 1989), Lee Naish suggested that programs which
make substantial use of assert/1, retract/1, etc. may run
more SLOWLY when compiled than when interpreted.
This was indeed the case with my code.
For example, one C-Prolog program which creates a directed graph
run under Quintus (after very minor syntactic changes)
was taking 4 or 5 times LONGER to execute when compiled
as compared to when interpreted.
But after all of the changes noted above,
the compiled code ran about 20 times faster than before.
This meant about 3 times faster than the original code
under C-Prolog.
And the new compiled Quintus version was also able to deal with
examples too large to be treated with the original code under C-Prolog.