[mercury-users] Destructive list operations

[Julien Fischer]

On Sun, 4 Jan 2009, Michael Day wrote:

> Hi,
>
> We use a lot of lists, and list operations are starting to take up a 
> significant portion of our total run time, so I have a few questions about 
> list operations that perform destructive update for speed.
>
> To begin with, there is the following mode for append:
>
> :- mode list.append(di, di, uo) is det.
>
> How is this implemented by the compiler? One might assume that it performs a 
> traversal of the first list and destructively updates the final cons tail to 
> be the second list, taking linear time and constant stack space. But is this 
> actually the case?

The compiler currently does not automatically take advantage of unique
modes to do CTGC, so in the absence of the --ctgc flag, the code
generated for the above is the same as that generated for the
(in, in, out) mode of append.

When CTGC is enabled, then a specialized version of the procedure 
is generated; whether it is used however is a matter of whether the
compiler can identify any call sites where it would be applicable.

> Also, we generally use the ++ function everywhere, and only call append 
> explicitly if we are using it in a reverse mode. Would it make sense to add a 
> di/di/uo mode for the ++ function?

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