[m-dev.] Trailing

[Peter Schachte]

On Tue, 12 Aug 1997, Bart Demoen wrote:

> you probably want to reset old_max_fr on backtracking as well ?

Yes.

> another point: if functions and "regular" trailings are pushed on the
> same stack, and executed/undone in reverse order of pushing, there is
> possibly a different behaviour from your schema or the 2 stacks schema
> in which this order is not respected; is that acceptable ?

I can't see why not.

> you have shifted some of the overhead of having tagged entries on one
> trail stack from untrailing to trailing - is it really better ?

That's the question I'm asking.  Alright, here's my analysis.  Corrections
welcome.

		1 tagged trail	2 sep. trails	New proposal

chpt. space	1 extra cell	2 extra cells	1 extra cell

pushing chpt	1 extra store	2 extra store	1 extra store

failure	fixed	1 load*,     	2 loads**,	1 load*,     
overhead	1 cond branch	2 cond branches	1 cond branch

untrailing	2 loads,	2 loads,	2 loads,     
cost/value	1 store, 	1 store, 	1 store,     
		2 cond branch,	1 cond branch	1 cond branch
		1 mask

untrailing	none		none		2 loads,     
overhead if                                     1 cond branch  
any values                                      1 call/return

untrailing	2 loads,	2 loads,	2 loads,     
cost/function	2 cond branch	1 cond branch	1 cond branch
		1 call/return	1 call/return	1 call/return
		1 mask

trail 1 value	2 stores*	2 stores*	2 stores*, 1 load*,
						1 cond branch

extra trailing	none		none		2 stores
cost once/chpt

trail function	2 stores*	2 stores*	2 stores*

* depending on register pressure, one (more) load may be necessary
** depending on register pressure, two more loads may be necessary

I've left out register increment/decrements, and probably a few other
things, but this should be about right.  I guess overall the single
tagged trail looks best.  The interface remains the same.

> >     2.  It would be nice if there was a mechanism to avoid multiple
> > 	untrailings in immediate succession.
> the mutables from SICStus 3.0 can be an inspiration for this

Can you tell me where to look for implementation details on mutables?

> as the functions on the trail stack can
> be used for whatever purpose, it cannot be known whether a garbage
> term is going to be restored by the function, or whether it is just
> going to do something stupid (like printing) with an otherwise
> unreachable term

In fact, you have no idea how to interpret the function argument.  It may be
a C pointer to some structure that has a bunch of pointers into the heap.
So it's quite important to handle it.  Even for the ardinary value trail
entries, you have no idea what the types of the entries are; this is a bit
of a problem during garbage collection.

> in its full generality, you would need the
> possibility to call the function with as calling_reason MR_gc ...
> or is the use of MR_trail_function restricted to what the
> implementation provides ?

I think calling the functions is probably the best way of handling this.  It
does mean that writing such functions is going to be a bit more tedious.

I'll send another message about this when I have a full proposal for
handling GC. 


-Peter Schachte      URL:  http://www.cs.mu.oz.au/~pets/
pets at cs.mu.OZ.AU     PGP:  finger pets at 128.250.37.150 for key
    Do insects spend hours demammaling their programs?