Subject: Re: Inserting clauses

From: Robert van Engelen <[email-masked]>
Date: Wed, 5 Apr 2000 08:55:53 -0400 (EDT)

> >I use pattern matching to determine the position of the new clause in the
> >clauses. The pattern matching technique is comparable to the techniques
> >applied in functional programming languages to order function definitions.
> 
> This is clear.
> 
> Time to run profile/3 and see where the time is spend.  If updating is
> not (almost) linear with the number of clauses you might have hit some
> implementation error.  In that case, send the program with instructions.

Each update is almost linear. The time complexity of the algorithm
to retract and assert for each insertion is linear in the number of clauses.
It just seems very odd that the only way to insert a clause is to retract
the first clauses, store them in a list (or in my case store them in the local
variables of the recursive predicate instantiation that inserts a clause)
and put them back later. The algorithm may scale in time, because each clause
before the inserted one needs to be analysed anyway, but doesn't the algorithms
have overhead in the temporary storage of clauses? (Your suggestion below
alleviates this problem, but is not applicable in my case because clauses may
be permanently removed later leaving some other clauses that are never used.)

Here are some statistics for 300 clauses:

/home/faculty/engelen/Ctadel2/lib/simplify.pl compiled into simplify, 11.34 sec, 1,776 bytes.
2,815,095 inferences in 11.34 seconds (248245 Lips)
Predicate                   Box Entries =     Calls+Redos = Exits+Fails
Time
===============================================================================
$clause/3                        89,893 =       89,878+15 = 89,854+39     21.8%
asserta/1                        44,921 =        44,921+0 = 44,921+0       8.6%
numbervars/4                    179,362 =       179,362+0 = 179,362+0      7.1%
mp:mp_compare1/3                180,809 =   92,134+88,675 = 92,134+88,675  5.1%

Here are some statistics for 600 clauses:

/home/faculty/engelen/Ctadel2/lib/simplify.pl compiled into simplify, 36.27 sec, 1,816 bytes.
8,508,565 inferences in 36.27 seconds (234590 Lips)
Predicate                   Box Entries =     Calls+Redos = Exits+Fails
Time
===============================================================================
$clause/3                       276,964 =      276,949+15 = 276,925+39    23.3%
asserta/1                       138,381 =       138,381+0 = 138,381+0      8.7%
numbervars/4                    553,242 =       553,242+0 = 553,242+0      8.0%
mp:mp_compare1/3                557,967 = 284,434+273,533 = 284,434+273,533 5.5%

For this example the situation is not so bad and the fact that the algorithms
are not linear is due to the insertion problem, not the retract/assert time.
But I am afraid that insertion time may increase due to the copying involved
and keeping the clauses in temporary storage (e.g. how much of it is put on
the stack?). If you can assure me that this approach will scale when the
database grows, I am fine with this solution.

> If the slow speed is caused by very complicated bodies, you could split
> the head from the body using a unique identifier and only reshuffle the
> heads:
> 
> a(...) :- very-complicated-body.
> 
> a(...) :- b(UniqueId, ...).
> b(UniqueId, ...) :- very-complicated-body.
> 
> Now you can shuffle the clauses of a without touching those of b.  If
> the body is complicated performance will not be harmed significantly.

Robert

-- 
   Robert van Engelen: Assistant Professor, Computer Science Department
   Florida State University, 206 Love Bldg., Tallahassee, FL32306-4530
   Offices: 150C DSL/101B MCH, (850)645-0309/644-9661, Fax: (850)645-0300
   Email: [email-masked], URL: http://www.cs.fsu.edu/~engelen