[mercury-users] mmc --structure-reuse

Michael Day mikeday at yeslogic.com
Sun Jan 4 21:22:31 AEDT 2009


> filter_neg([], []).
> filter_neg([X|Xs], Ys) :-
>     filter_neg(Xs, Ys0),
>     ( if X < 0 then
>         Ys = [0|Ys0]
>     else
>         Ys = [X|Ys0]
>     ).

I tried enabling --structure-reuse for this example and the results were 
pleasantly surprising, although not perfect. Here is the code:

void filter_neg(Word Xs, Word * Ys)
{
     if (Xs == 0)
     {
         *Ys = 0;
     }
     else
     {
         Integer X = (Integer) field(tag(1), Xs, 0);
         Word Xs0 = (Word) field(tag(1), Xs, 1);
         Word Ys0;

         filter_neg(Xs0, &Ys0);

         if (X < 0)
         {
             *Ys = Xs;
             field(tag(1), *Ys, 0) = 0;
             field(tag(1), *Ys, 1) = Ys0;
         }
         else
         {
             *Ys = Xs;
             field(tag(1), *Ys, 0) = X;
             field(tag(1), *Ys, 1) = Ys0;
         }
     }
}

It's not performing any allocations, which is great, but it's not 
tail-recursive, so it will blow the stack on large lists. Perhaps I can 
rewrite the predicate to avoid this, somehow?

Also, the else case seems to have an unnecessary copy: it is setting the 
first field of Ys to be X, but X is the first field of Xs and Ys has 
just been set to Xs, so this is unnecessary.

Overall this looks very promising, and raises the hope of writing 
ordinary list code and have it run efficiently without hackery.

How reliable is the --structure-reuse option? Any schedule on when it 
will be enabled by default? I am testing with rotd-2008-01-30, has it 
changed in more recent versions?

One final note: the ctgc version of the predicate does not appear to be 
called by the test program I made, even though the input is unique and I 
see no reason why it can't be reused. In fact, why does Mercury even 
bother to generate a non-ctgc version when the input has mode di?

Best regards,

Michael

-- 
Print XML with Prince!
http://www.princexml.com
--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the users mailing list