[m-dev.] diff: better unsorted_aggregate/4

Peter Schachte pets at students.cs.mu.oz.au
Mon Sep 29 11:23:35 AEST 1997


On Mon, 29 Sep 1997, Fergus Henderson wrote:

> library/std_util.m:
> 	Implement unsorted_aggregate so that it interleaves the
> 	generator and the accumulator, rather than generating all

This looks fine.

Since coding this, and in thinking about comments made on comp.lang.prolog
by Karen Morrissey, it occurred to me there may be a better way to do this.
In some cases, the aggregate itself will be very small, sometimes just an
io__state, while the solutions themselves will be very large.  In such
cases, it would be better never to copy parts of the solutions that aren't a
part of the aggregation.

So here's a proposed algorithm:

	1.  Call the generator closure, building a solution on the heap.
	2.  Swap (the runtime systems conception of) the heap and solutions
	    heap.
	3.  Call the collector closure, passing the "collection so far" and
	    the new solution, storing it as the new "collection so far."
	4.  Deep copy the "collection so far" to the solutions heap (which
	    is now thought of as the heap).  Since it was built on the
	    solutions heap, only the parts of the new solution which have
	    become part of the collection so far actually need to be copied.
	5.  Swap the heap and solutions heap back.
	6.  Force a failure, and return to 2 for each new success.
	7.  Return the collection so far as the aggregate.

The trouble with this is that (as I understand it) deep_copy needs to
traverse the whole aggregate just to see that there isn't much it needs to
copy.  So if the aggregate being built is large, the implementation you just
checked in will be much better.  But if it's just an io__state, this
proposal looks pretty good.

Well, as long as we're using the conservative GC, it doesn't matter anyway.


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




More information about the developers mailing list