Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!snorkelwacker!ira.uka.de!fauern!lan!tumuc!guug!ecrc!joachim
From: joachim@ecrc.de (Joachim Schimpf)
Newsgroups: comp.lang.prolog
Subject: Re: Arrays in Prolog
Keywords: value trailing, coroutining
Message-ID: <1238@ecrc.de>
Date: 17 Sep 90 16:29:38 GMT
References: <90239.175243SCHMIED@DB0TUI11.BITNET> <3899@bingvaxu.cc.binghamton.edu> <1990Aug28.065353.13951@sics.se> <3904@bingvaxu.cc.binghamton.edu> <1990Aug29.095308.18522@sics.se> <3907@bingvaxu.cc.binghamton.edu> <1032@ecrc.de> <1990Sep11.150245.26833@sics.se>
Sender: news@ecrc.de
Reply-To: joachim@ecrc.de (Joachim Schimpf)
Organization: European Computer-Industry Research Centre, Munich
Lines: 48

In article <1990Sep11.150245.26833@sics.se> matsc@sics.se (Mats Carlsson) writes:
>In article <1032@ecrc.de> micha@ecrc.de (Micha Meier) writes:
>   Value trailing is necessary to implement
>   efficiently coroutining systems (yes, I know that it is possible
>   without, but not fast enough). It was already present in MU-Prolog.
>
>This is an interesting claim.  Could you provide some arguments for
>why it is that coroutining systems become so much slower without value
>trailing?
 
The main advantage - compared to a scheme as presented in Mats
Carlsson's ICLP 87 paper - is a more efficient handling of updates
to the list of delayed goals associated to every suspending variable.
 
In a typical delay-tests-and-generate application it is quite common
to have hundreds of goals delayed on only a few variables, so these
lists can become rather long.
 
Using destructive and value-trailed updates, all operations can be
performed in O(1) time. Without, the only choice seems to be using
open-ended lists, which means all operations are O(length).
 
The reason why these lists can be destructively changed is that they
are an internal data structure, and we are sure we don't need multiple
versions at the same time.

>Value trailing seems to have a rather high price: the trail
>becomes twice as large, and there is extra work for each (normal)
>variable to reset.

It is not necessary to use value trailing even for normal variables.
Having two trails, one for normal, one for value trails, is probably
too expensive (you also might get into trouble since you couldn't
untrail in exactly the reverse order than trailing had been done).
In a paper of Bowen et al (ICLP 86) there was a suggestion to
interleave the two trails by linking all the value trail entries,
assuming they occur infrequently.
In the SEPIA system we use a sort of tagged trail entries, which
has turned out to be reasonably efficient.

A point to mention, however, is that garbage collection becomes
somewhat more difficult in the presence of value trailing.


--
Joachim Schimpf
ECRC, Arabellastrasse 17, D-8000 Munich 81, West-Germany
joachim@ecrc.de  (from USA: joachim%ecrc.de@pyramid.com)