[m-dev.] Trailing

[Peter Schachte]

On Sat, 9 Aug 1997, Fergus Henderson wrote:

> I think the common case will be backtracking to a choice point
> after there have been _no_ trail entries added.  For this common
> case, it is faster if you only have to check one trail.

Ok, I've got another idea.  The interface remains as I proposed, but the
implementation changes.

There will be only one trail:  the function trail.  MR_trail_value() can be
implemented as:

	struct value_trail_entry {
	    Word *address;
	    Word value;
	};

	static struct value_trail_entry *cur_val_tr_ptr;

	void MR_trail_value(Word *address, Word value)
	{
	    static Word *old_max_fr = NULL;

	    if (MR_current_choicepoint() != old_max_fr) {
		MR_trail_function(untrail_values, (Word)cur_val_tr_ptr);
		old_max_fr = MR_current_choicepoint();
	    }
	    cur_val_tr_ptr->address = address;
	    cur_val_tr_ptr->value = value;
	    ++cur_val_tr_ptr;
	}


	static void untrail_values(Word datum, MR_untrail_reason reason)
	{
	    struct value_trail_entry *bottom;

	    if (reason == MR_undo || reason == MR_exception) {
		while (bottom <= --cur_val_tr_ptr) {
		    *(cur_val_tr_ptr->address) = cur_val_tr_ptr->value;
		}
	    }
	    cur_val_tr_ptr = bottom;
	}

I haven't checked this very carefully, but I hope you get the idea.

So the cost tradeoff is that trailing a value becomes more expensive (a
conditional branch which will probably usually be taken, and when it's not ,
and extra function call and an assignment), and untrailing becomes more
expensive (one extra function call per choicepoint with some values
trailed).  On the plus side, choicepoints only need to store one trail
pointer, and failing when nothing is trailed is cheaper. 

I still have these loose ends, though:

    1.	Trailing in semidet code, as mentioned in my last mail
	message.

    2.  It would be nice if there was a mechanism to avoid multiple
	untrailings in immediate succession.  Eg, suppose we've been
	making one copy of a whole array for each choicepoint.  If a
	failure takes us back a few choicepoints, it would be nice if
	we could just put back the right copy of the array, rather
	than copying back the array once for each choicepoint.  I hope
	this is clear.  I wish I could draw a picture and wave my
	hands around to explain this.

    3.  Accurate garbage collection.  Firstly, the garbage collector
	needs to trace through the trail entries (both the function
	and value trails).  Also, it would be nice if after garbage
	collection, trail entries that specify how to restore garbage
	terms could be removed from the trails.  This seems fairly
	important, as doing this will sometimes mean that on the next
	garbage collection, some stuff that was only accessible from
	the trail can now be reclaimed.

Comments/suggestions?


-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?