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

[Peter Schachte]

On Mon, 29 Sep 1997, Tyson Richard DOWD wrote:

> > Right.  In particular, for unsorted_solutions/2, the implementation in my diff
> > is O(N), whereas your suggestion would be O(N^2).

This is true as far as it goes, but it doesn't cover all costs.  The current
implementation is also O(MN) in the number and size of solutions, whereas
the new proposal is O(1).  Anyway, it's clear that this new proposal is
unacceptable for implementing solutions/2 and many similar things.

> > True.  On the other hand, I'm not willing to make solutions/2 O(N^N).

N^N?  It's not *that* bad :-).

> Well, you could do a runtime type check to see which version to call.
> If type of aggregate is a builtin type then use Peter's algorithm.

Maybe if it's coded carefully, inlining could turn it into a compile-time
type test in the common case?

Anyway, ultimately the best solution is to have the aggregator build the
result on the right stack in the first place.  This, it seems to me, is a
generalization of compile-time garbage collection.  We usually think of
compile-time gc as determinging that some term will be dead after a
particular use, and therefore we can feel free to reuse it.  But it would
also be sensible to determine at the time a term is created that it will not
survive the body that created it, and therefore allocate it on the call
stack like an auto variable in C.  We could also go the other way, and
determine at compile time that a term that is being built will ultimately be
copied into more permanent storage, and so we should build it build it there
in the first place.  It's just a matter of lifetime analysis.  SMOP.


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