[m-rev.] for review: version array reimplementation

[Peter Wang]

On 2009-07-28, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> On 27-Jul-2009, Peter Wang <novalazy at gmail.com> wrote:
> > +static void
> > +ML_va_rewind_into(ML_va_ptr VA, const ML_va_ptr VA0)
> > +{
> > +    MR_Integer I;
> > +    MR_Word    X;
> > +
> > +    if (ML_va_latest_version(VA0)) {
> > +        return;
> > +    }
> > +
> > +    ML_va_rewind_into(VA, VA0->rest.next);
> > +
> > +    I  = VA0->index;
> > +    X  = VA0->value;
> > +    if (I < VA->rest.array->size) {
> > +        VA->rest.array->elements[I] = X;
> > +    }
> > +}
> 
> What is the average and maximum recursion depth here? If it is significant,
> you could cut the cost of recursion here (which will include setting up
> a stack frame of at least five words) by having your own array of <I, X>
> pairs, pushing them on the stack until you find the latest version and
> then applying the assignments. If you run out of array before then, you
> can always recurse then.
> 
> This is basically middle-recursion optimization applied to C code.

The recursion depth is however many versions VA0 is lagging behind the
latest version of the array.  If you take a version array VA0, apply k
updates to it, then update to VA0 (or copy it) then it will recurse k
times.

In mmc --make (before my patch today) the maximum depth would be limited
by the number of files that the compiler has to deal with, say,
low thousands.  The average I saw was in the low hundreds.

Peter
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------