[mercury-users] Loop optimisation and predicate specialisation and stuff.

[Tyson Dowd]

On 15-Dec-1997, Ralph Becket <rwab1 at cam.sri.com> wrote:
> A couple of queries regarding optimisation in Mercury 0.7.3:
> 
> 1 . Say I have a tail recursive predicate which calculates some
>     locally constant value in its body, e.g.
> 
> 	:- pred foo(int, int, list(int), int).
> 	:- mode foo(in,  in,  in,        out) is det.
> 
> 	foo(_, [], C, C).
> 
>     	foo(A, [B | Bs], C0, C) :-
> 		X = f(A),		% f/1 is a det function.
> 		C1 = g(X, B, C0),
> 		foo(A, Bs, C1, C).
> 
>     Will the compiler move the calculation of X outside the loop body?
>     If not, the programmer has to do this by hand, probably by
>     introducing a new predicate.

I rewrote this as something similar, but a valid mercury program, and
tried it out.

The code generated for this is (roughly):

entry:
	if (list is empty)
		goto code to handle empty case (i3)
	call f, return to i4
i4:
	create g/3 term
	shuffle arguments a bit
	if (list is empty)
		goto code to handle empty case (i3)
	call f, return to i4
i3:
	shuffle arguments to return list

So the answer is no, the Mercury compiler doesn't currently move the
call out of the body of the loop. 

It would probably be a good thing to do. 

> 
> 2 . Some algorithms do require one to pass around a fair amount of
>     state (e.g. a dozen variables).  If several predicates are
>     required to implement the algorithm then this can get rather
>     messy.  The answer is usually to box 'em up in a functor and use
>     various projection and updating functions:
> 
> 	:- func a(some_state) = type_a.
> 	:- mode a(in) is det.
> 	a(some_state(A,_,...)) = A.
> 
> 	[and so on]
> 
> 	:- pred set_a(some_state, type_a, some_state).
> 	:- mode set_a(di,         in,     uo) is det.
> 	set_a(some_state(_,B,...,Z), A, some_state(A,B,...,Z)).
> 
> 	[and so on, then...]
> 
> 	bar(..., State0, State) :-
> 		baz(a(State0)),
> 		set_b(State0, Something, State1),
> 		quux(..., State1, State).
> 
>     With suitable use of inlining this can be made quite efficient (or
>     it will be when di/ui/uo modes are fully implemented [what's the
>     status of this?]).

I can't answer that one, maybe someone else can.

> 
>     It seems to me that predicate calls *may* be cheaper this way
>     since all or most state is passed via a single argument.  On the
>     other hand, every access to some part of state is via indirection.
> 
>     Can the compiler/will the compiler be able to spot the common
>     structured argument type and specialise predicates so that the
>     some_state wrapper is done away with and the various state members
>     are passed directly as arguments?  And if so, will the compiler
>     reorder the order of arguments to try to minimise the number of
>     rearrangements of the stack frame for tail call optimisation?
>

No. We've been interested in working on optimizations such as these ones
in the past, but haven't get anyone to do them yet. There are various
optimizations that can be done with types (fold/unfold types, pass
only certain arguments, etc). I'm aware of at least two problems with
these optimizations:

	1. It's difficult to be able to predict when it will be a win.
	   Sometimes it will have little effect, it could even slow the
	   program down. Getting the right heuristic might be difficult.

	   Consider the optimization you're talking about: At some
	   point you remove the arguments from their wrapper, and pass
	   them around in separate registers, hoping that doing this
	   work now will save you more work later.

	   Extra arguments cost extra registers, and on some
	   architectures, registers are very scarce (x86 in
	   particular). Also, lots of registers means lots of saving
	   registers whenever you have to do a call, which means if
	   you want to get them back you just have to get them from
	   memory... which is where they were before the "optimization"
	   anyway the first place. (It gets worse, if you run out of
	   real registers, you'll pass the arguments in fake registers
	   (memory), save them across calls in stack frames (memory)
	   and then retrieve them when needed). 

	   So if you have a flat data structure, lots of registers,
	   and few calls, it might be worth passing a few more arguments
	   to save fetching the arguments indirectly.

	   If you have any benchmarks or results that indicate this
	   might be worthwhile, of course I'd be willing to become a lot
	   less skeptical ;-) Performance is difficult to estimate.

	2. We only have one calling convention. Inter-module effects
	   pretty quickly dampen most efforts to add more calling
	   conventions, because you need to be able to be sure all
	   callers can correctly call the predicate. This can be
	   done, it's just a lot of work and can sometimes remove
	   the benefits.

The last part of what you said talks about re-arranging argument
orders to minimize shuffling might be worthwhile, but it runs into
problems with calling conventions (and maybe complexity of the analysis).

> 3 . Beg beg beg, can we have nested unique modes soon?  Pretty please!

Again, I can't answer this one.

> 
> Normally I wouldn't be too worried about stuff this low level, but I'm
> in the middle of an efficiency argument with somebody.  It seems to me
> that if these optimisations aren't already there, it's only a matter
> of time before they appear.
> 
> For that matter, are there any plans to provide a stripped-down
> compiler back end to support experiments in source-to-source program
> transformation?  The expand_terms sample program doesn't really cut it
> since it doesn't provide access to the full program, just the parse of
> a single file.  This is important if you want to transform higher
> order code or need access to typing information (as in 2 above).
> 

There is another research group that is interested in using Mercury as a
backend, and have already started inserting certain hooks that will
enable them to have better control over the results of their
transformations. Perhaps their future work will be useful in this
area, but I don't know all of their plans.

> I'm sure the Mercury development team have more than enough on their
> plates as it is, so please take these as requests for information and
> not demands of any kind!

Of course.

-- 
       Tyson Dowd           # If I'm unusually agressive in this email, it's
                            # probably because USENET has been down here for
     trd at cs.mu.oz.au        # over a week, and I'm missing my usual dosage
http://www.cs.mu.oz.au/~trd # of flamewars. My apologies in advance.