[m-dev.] for review: tuples [1]

[Peter Schachte]

On Thu, Aug 03, 2000 at 09:34:46AM +1000, Simon Taylor wrote:
> Peter Schachte wrote:
> > Hang on.  If you're going to do that, wouldn't you be a lot better off using
> > the defn:
> > 
> > 	:- type (T1,T2) ---> (T1,T2)
>  
> > I can only see one disadvantage:  for triples and above, the representation is
> > inefficient (and for pairs, the standard pair type is probably fine).  This
> > could be fixed by implementing structure inlining of single-constructor types.
> > Of course, this would have benefits in many other situations, as well.  Is
> > there some reason that this is a more difficult optimization than it would
> > seem?
> 
> It doesn't work well with polymorphic predicates because
> the structures would need to be un-inlined before passing
> them to a predicate such as io__write or std_util__deconstruct.

I don't think un-inlining is a problem:  you just take a pointer to the
middle of the structure.  Standard C implementation stuff.  For example, if
you have the type:

	type foo ---> something(int, (int, int, int), int).

the usual Mercury implementation (given my defn of the ,/2 type above) would
be equivalent to the C type:


struct something {
    int		first;
    inttriple	*second;
    int		third;
}

struct inttriple {
    int		first;
    intpair	*second;
}

struct intpair {
    int		first;
    int		second;
}

If a variable V is bound to a term of type foo/0, then accessing its second
element is done as if by `V.second', and accessing the last element of the
triple would be done as if by V.second->second->second.

Instead I'm suggesting implementing it as if by:

struct something {
    int		first;
    inttriple	second;
    int		third;
}

struct inttriple {
    int		first;
    intpair	second;
}

struct intpair {
    int		first;
    int		second;
}

To access the second member of the same V, just do &V.second.  No problem.
And the third element of the triple would be accessed as if by
V.second.second.second.

The only problem comes when you want to set the second element of V.  The
first method allow a single pointer assignment, whereas the second requires
three integer assignments.  Fortunately Mercury does not support destructive
assignment, so the only time you do this is when you create a new something.

> This optimization is in the same category as the type unfolding
> discussed earlier in this thread -- it's difficult to work out
> when it will improve performance.

Consider the actual costs:
				current cost		cost with unfolding
create new something from
    existing triple		1 alloc, 3 assigns	1 alloc, 5 assigns,
							4 reads
create new something with
    new triple			3 allocs, 7 assigns	1 alloc, 5 assigns

access first of triple		2 reads			1 read
access second of triple		3 reads			1 read
access third of triple		3 reads			1 read
access whole triple		1 read			1 address calculation


So if we assume we create the structure once from an existing triple, and
access each member once, the total costs the current way is 1 alloc, 3
assigns, and 8 reads.  With unfolding, there are 2 more assigns, and 1 fewer
read.  If each member is accessed twice, the unfolding approach saves 6
reads at the cost of 2 extra writes.  When the triple is created at the same
time as the something, with a single read of each member, the unfolding
approach saves 2 allocs, 2 assigns, and 5 reads.  I guess it's obviously a
win when you're creating both at the same time, my point is it's not much of
a lose when you're not.  Also, the unfolded version has better locality of
reference.

It is possible to get a slowdown in some cases from this optimization, but I
expect it would be a win overall, at least for inlining two argument
single-constructor terms (one argument single-constructor terms are already
optimized).  For larger structures, the tradeoff is less clear.  It would be
interesting to have a compilation parameter that would specify the largest
single-constructor type that to automatically inline, and play with it to
see when it wins and when it loses.  But I suspect 2 would almost always win
in real code.

-- 
Peter Schachte <schachte at cs.mu.OZ.AU>  Reason deceives us often; conscience
http://www.cs.mu.oz.au/~schachte/      never.
Phone:  +61 3 8344 9166                    -- Rousseau 
Fax:    +61 3 9348 1184                
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------