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

Tyson Dowd trd at cs.mu.oz.au
Wed Dec 17 17:27:24 AEDT 1997

```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)
i4:
create g/3 term
shuffle arguments a bit
if (list is empty)
goto code to handle empty case (i3)
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.

```