[mercury-users] mmc --structure-reuse

[Julien Fischer]

On Sun, 4 Jan 2009, Michael Day wrote:

>> 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 doubt it will ever be enabled by default.  Using CTGC on a non-trivial
program requires the use of --intermodule-analysis, and from what I recall
it requires _significant_ amount of analysis.  The resulting blowout in
compilation time would not be acceptable by default.

> I am testing with rotd-2008-01-30, has it changed in more 
> recent versions?

Assuming that the above date is correct, then yes, it has been worked on
quite a bit over the past year.

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

Because that is what Mercury generates by default for uniquely modeded
things at the moment.

Julien.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------