bimbart@kulcs.uucp (Bart Demoen) (02/23/88)
I have been busy with the theorem prover of R. Overbeek, which was used
as a benchmarking program and a challenge to the prolog community. I want
to report here on my experiences with changing the program, introducing
destructive assignment and finding a reason why his prolog program is 20
times slower than his C program for this problem.
The unchanged version of the program took 77 sec in BIMprolog, on a SUN3/50
with the boys example (it is slow, I know, the main reason is that the bit
operations on integers are not yet in assembler, they are interpreted now;
and if you try to make time measurements, you will notice how much time the
program spends in get_next_literal and get_literals)
The first change I made to the program, was to replace the definition of
num_lits/3:
num_lits(_p,_n,_num) :- c(_p,0,_m) , c(_n,_m,_num) .
c(0,_i,_i) :- ! .
c(_n,_i,_j) :- _k is _n / 2 ,
_i1 is _i + _n - 2 * _k ,
c(_k,_i1,_j) .
This reduced the runtime to 70 seconds !
By giving another prolog definition to get_next_literal and get_literals, I
gained another 22 seconds ! (I am a bit ashamed about this prolog definition,
so I will not distribute it over the net, but you can obtain it from me
privatly)
Some small changes involved:
the test for tautology before the test for forward_subsumed
(that's how it is in C !)
form_resolvent/7 is symmetric in the first 2 argument pairs (at least
that's the way it is used) so there is no need to have 2 definitions
of form_resolvent/8; accordingly the definition of form_resolvent/7
becomes
form_resolvent(Par1Pos,Par1Neg,Par2Pos,Par2Neg,
ClashLit,ResPosWord,ResNegWord) :-
Mask is \(1 << (ClashLit - 1)),
ResPosWord is ((Par1Pos \/ Par2Pos) /\ Mask ),
ResNegWord is ((Par2Neg \/ Par1Neg) /\ Mask).
(it looks so in C !)
This gained only 1 second.
Then, I replaced all if-then-else constructions by their equivalent with
disjunction and cut: for instance:
delete_from_database_clauses([Id|Rest],L,Db,NewDb) :-
( member(Id,L) ->
delete_from_database_clauses(Rest,L,Db,NewDb)
; /* otherwise -> */
delete_from_database(Db,Id,Db1),
delete_from_database_clauses(Rest,[Id|L],Db1,NewDb)
).
became:
delete_from_database_clauses([Id|Rest],L,Db,NewDb) :-
( member(Id,L) , ! ,
delete_from_database_clauses(Rest,L,Db,NewDb)
; /* otherwise -> */
delete_from_database(Db,Id,Db1),
delete_from_database_clauses(Rest,[Id|L],Db1,NewDb)
).
Gain: 4 seconds.
The program took now about 44 seconds.
Then, I introduced destructive assignment into the program, as much as possible
without changing the algorithm. So, argrep/4 and delete/3 and
form_updated_index/4 were rewritten with destructive assignment and time
dropped from 44 to 22 seconds.
Actually, there was a small problem with destructive assignment, because at
one place in the program, the old database is used after the new one has been
constructed:
subsume_and_add(Db,ResPos,ResNeg,Parents,NewDb,DelList,NewEnd) :-
( (forward_subsumed(Db,ResPos,ResNeg) ; tautology(ResPos,ResNeg) ) ->
NewDb = Db,
NewEnd = DelList
; /* otherwise -> */
add_to_sos(Db,clause(Parents,ResPos,ResNeg),NewDb,NewId),
write_added_mesg(NewId,clause(Parents,ResPos,ResNeg)),
back_subsumption(Db,NewId,ResPos,ResNeg,DelList,NewEnd)
). ^^
||
In the call to back_subsumption, the first argument can be NewDb, but then in
the second definition of backsub/6, after the call to subsumes/4, an extra test
Id =\= SubId
must be added. (the C code also shows this test)
For destructive assignment, I implemented (in the BIMprolog kernel of course) a
predicate
replaca/3 arg1 : a compound term
arg2 : an integer between 1 and the arity of arg1
arg3 : anything
effect : in arg1, the arg2'th argument is replaced by arg3
and then changed the program accordingly; for instance: the new definiton of
argrep/4:
argrep(N,Old,Value,Old) :- replaca(Old,N,Value) .
For a destructive delete/2, I had to do something similar.
It is clear that destructive assignment improved the speed, but still the prolog
program is slower by a factor at least 10 than the C version.
With destructive assignment, the program needed 2.5 times less heap.
Not only the lack of destructive assignment is the performance killer in this
program: let's look at a typical sequence in the prolog program and compare it
with the C version:
backsub(...)
:-
( subsumes(SubsumerPos,SubsumerNeg,Pos,Neg) , Id =\= SubId , ! ,
write_subsumed_mesg(Id,SubId),
add_element(DelList,Id,EndList)
;
EndList = DelList
),
backsub(...).
for (pt = lst->next_avl - 1; pt >= lst->first; pt--)
{
if ((formula_id != (*pt)->id) && Subsumes(cl,(*pt)))
{
printf("clause %d subsumes %d \n", formula_id,(*pt)->id);
add_to_deleted_list((*pt)->id);
}
}
Most prologs recognise tailrecursion and can compile it to iteration, all right.
But, instead of C's if-then-else, prolog creates a choicepoint, makes the test
subsumes/4 (which is an out-of-line call while Subsumes in C is a macro) and
either calls a general procedure to fail, or continues and executes a cut: the
prolog overhead is at least a factor of 50 compared to C ! It is almost a
surprise that prolog is only 20 times slower !
Moreover, the datastructure used in the C and prolog program for sets, (a bit
string, i.e. an integer) is very much in favour of C: in a 'typed' prolog were
dereferencing would not be needed, arithmetic could approach the speed of
C arithmetic, but not in untyped prolog.
Since prolog compiler technology is still immature, the introduction of
destructive assignment improved the speed of the program with only a factor
of 2 (from 44 to 22 seconds) which is not much; but perhaps, in a couple of
years, when we will have implemented all beautiful ideas floating around right
now, the improvement will be from 24 to 2 seconds, making destructive assignment
well worth the effort !ed298-ak@violet.berkeley.edu (Edouard Lagache) (02/28/88)
In article <1150@kulcs.UUCP> bimbart@kulcs.UUCP (Bart Demoen) writes: >I have been busy with the theorem prover of R. Overbeek, which was used . . . >For destructive assignment, I implemented (in the BIMprolog kernel of course) a >predicate > > replaca/3 arg1 : a compound term > arg2 : an integer between 1 and the arity of arg1 > arg3 : anything ^^^^^^^^^ Here is an item that has interested me almost since I started using PROLOG. Why aren't destructive list predicates a part of PROLOG? I must say that I haven't missed them much in my programming but I have been avoiding lists with a passion. When lists and speed are needed, destructive list predicates would seem to be desirable. So what you do say folks? Shouldn't destructive manipulation be a part of PROLOG (or is it a part of most PROLOGs already?) Edouard Lagache
ok@quintus.UUCP (Richard A. O'Keefe) (02/29/88)
In article <7244@agate.BERKELEY.EDU>, ed298-ak@violet.berkeley.edu (Edouard Lagache) writes: > In article <1150@kulcs.UUCP> bimbart@kulcs.UUCP (Bart Demoen) writes: > >I have been busy with the theorem prover of R. Overbeek, which was used > . > >For destructive assignment, I implemented (in the BIMprolog kernel of > >course) a predicate > > replaca/3 > > Here is an item that has interested me almost since I started using > PROLOG. Why aren't destructive list predicates a part of PROLOG? Oh dear oh dear oh dear oh dear. Have you ever felt that everything you have done for the last N years has been futile? Have you ever been telling people about the milk and honey of the Promised Land, only to have them turn around and say "What about leeks? We had great leeks in Egypt." Let's clear up a misconception. Demoen's rplaca/3 is NOT an operation on lists as such, it's the equivalent of an array element update (see '$SET' in some versions of C Prolog, setarg/[3,4] in some other Prologs). But didn't you spot the punch-line in Bart Demoen's posting? He did all those things, including adding rplaca/3 , AND IT STILL DIDN'T HELP. The time went down from 77 seconds to 22 seconds (the last reduction was from 44 seconds to 22 seconds). However, (a) the original version of the program took 26 seconds in Quintus Prolog (b) Tim Lindholm was able to reduce that by a large factor (I haven't the figures to hand, but it was about a factor of 2, and did *not* involve the use of any sort of destructive operations). (c) the C version took 1.18 seconds (d) there is reason to believe that the C version could go twice as fast (e) these times are times on one specific problem. It's not enough to get close to C speed on this problem. The method used has to SCALE at least as well as the C version scales. The whole problem with Overbeek's Prolog program is that it faithfully mirrors the structure of his C program. The way to obtain a fast Prolog program is to go back to the specification, and write a Prolog program, instead of writing a C program in Prolog. > So what you do say folks? Shouldn't destructive manipulation be > a part of PROLOG (or is it a part of most PROLOGs already?) Look, if you want to use destructive operations, please use Lisp. Lisp is GOOD at that sort of thing, though I would warn you that in some Lisp systems rplacd is very bad for efficiency. The whole point of Prolog is that it is supposed to be based on logic. Destructive operations simply have no place in that model. Which is not to say that arrays with unit expected-time update do not! There were several papers about them, and one technique was posted to the Prolog Digest. Is anyone out there using a Prolog with logical arrays? What's it like? Why are so many people chasing the "destructive operations" pennies when there are "better data structure" POUNDS to be won?
steve@hubcap.UUCP ("Steve" Stevenson) (03/02/88)
in article <710@cresswell.quintus.UUCP>, ok@quintus.UUCP (Richard A. O'Keefe) says: > > Look,... Which is not to say that arrays with unit expected-time update do not! There were several papers about them.... I would appreciate a reposting of the papers and / or techiques. Of quite a bit of interest to me is how to deal with something like a vector Newton-Raphson or Jacobi method. -- Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu Department of Computer Science, (803)656-5880.mabell Clemson University, Clemson, SC 29634-1906
seif@sics.se (Seif Haridi) (03/10/88)
Regarding destructive assignment in Prolog, here is our experience at SICS with this feature. SICStus Prolog (version 0.6 will be announced soon for external use) has a backtrackable assignment called setarg/3: setarg(+ArgNo,+CompoundTerm,?NewArg) which replaces destructively argument ArgNo in CompoundTerm with NewArg and the assignment is undone on backtracking. There is also a lower level nonbacktrackable assignment not available for the users. We had this feature for a while to evaluate its need. My current view is that setarg/3 is not needed as is but it has been used to implement in SICStus Prolog other features that are important for efficiency. 1. setarg/3 has been used to implement a number of predicates for manipulating logical arrays with constant access time for the latest array reference. 2. Also it has been used for implementing logical hash tables (with the possibility of removing items from the hash table). These features are needed in a project on natural language processing at SICS where a grammar dictionary is created from reading an analysing a text in natural language. The features above can of course be used on other Prolog conventional applications. 3. Another primitive that is now existing in SICStus 0.6 is an : if(+P,+Q,+R) which is: if P then Q else R this is similar to (P -> Q ; R) construct except that it allows the generation of all possible solutions for P. This construct was needed on a work going on a complete theorem prover being built at SICS for intuitionistic first order logic. This control primitive was implemented efficiently first after using the lower primitive nonbacktrackable destructive assignment. Another area where we thought first that assignment is important is the area of object oriented programming as in SmallTalk (mutable objects) specially for the important class of discrete event simulation applications. The way out was to do object oriented programming in SICStus in a way that is similar to committed choice languages (CCLs). That is to introduce a data-driven control element in the language above the normal goal driven mechanism. This is done by introducing wait declarations in the language and device a reasonably efficient suspension mechanism. This leads to a language with the added expressive power of CCLs on sequential machines but it also allows backtracking over streams. A problem arose here is how to create multiple reference to a shared object. This is done as in CCLs by creating a tree of binary merge operators to the shared object. This can be done and isolated in a single predicate called merge/2 for doing the so called multiway merge. A problem here is that sending a message to a shared object would not take a constant time. The message has to pass through a number of merge operators. This is not acceptable in all known object oriented languages. 4. The multiway merge/2 is again implemented by setarg/3 reduces the message sending delay to constant time (see Shapiro). 5. Another object in the style CCLs that is useful in is an array object that can be implemented using setarg/3. The above two features had a considerable effect on the speed of a number of discrete event simulation programs that we wrote. In summary my current point of view is that the use of setarg/3 can be isolated and hidden in a number of predicates that still can be implemented in a Prolog system ( in case of object oriented feature you need a data driven control element). The use of setarg is then to increase efficiency without changing the semantics of your program Seif Haridi
alf@sics.se (Thomas Sj|land) (03/11/88)
The ending point of Seif's message "without changing the semantics of your program" should be read "without changing the semantics of your algorithm" to make sense, I guess. I (and also Seif, implicitly) mentioned the possibility to "implement" setarg/3 using var/1 and !/0. Perhaps it should be clarified that what is meant is that you can represent a variable that you wish to modify during the execution as a partially instantiated structure (an open list containing all values assigned to the variable). This is not exactly an "implementation" since you cannot unify two "variables" represented in this way if they do not share the same instantiation history, but it is a practical programming technique, that is appropriate in many situations, if you do not wish to use setarg/3. The efficiency problem mentioned by Seif should be obvious from this. The semantic problems seem to be similar to those introduced by viewing i.e. [1.2.3|X]-X as the same d-list regardless of what X is bound to. In both cases you READ your program in a particular way, and JUSTIFY your statement about equality of "the semantics" by some more or less well-specified METHODOLOGY for implementing a given algorithm.