[mercury-users] Mercury programming by optimization

[Michael Hendricks]

On Wed, Mar 7, 2012 at 6:14 PM, Paul Bone <pbone at csse.unimelb.edu.au> wrote:
> How are the different alternatives generated.

The programmer provides the alternatives: multiple algorithms for
accomplishing the same goal.

> Optimization
> as a specialization occurs when, for instance it is common to use the type
> map(int, U) which is a sub-type of the type map(T, U).  Therefore, all the code
> that operates on map(T, U) can have an alternative implementation generated
> that works with map(int, U) - which is faster as comparisons on ints are faster
> than comparisons on some abstract type T.  Mercury already performs this
> optimization, and users may provide hints to the compiler about how to
> specialize code.

That's a neat trick.

> If the compiler generates these alternative versions of the same code what is
> the benefit of comparing implementations using QuickCheck?  I can see this
> being useful if the programmer provides different algorithms for solving the
> same problem, such as sorting.

Yup, since the programmer provides the alternative algorithms,
comparing his redundant implementations could offer some automated
testing.

> Eg, by providing both quicksort and mergesort.
> If the programmer also told the compiler when one sort is better than another
> the compiler (with enough data) could pick between the alternatives.

The hope is that the compiler can discern which sort is better, based
on the profiling data.  The article argues that compiler and hardware
variations make it difficult for the programmer to know which
algorithm performs best, so he provides multiple algorithms and defers
performance judgements to the compiler.

During the profiling phase, I assume the compiler would have to
randomly assign each predicate invocation to one of the alternative
algorithms so that it collects data about each one in different
conditions.  A subsequent recompile would consult the profiling data
to decide which alternative is best in each call site.  Or perhaps add
other conditional checks to choose among the alternatives.

> The latter can be more useful in a parallel environment.  For example, many
> fast sequential algorithms aren't easy to parallelize because they use
> accumulators.  However, if accumulators are removed we can have an algorithm
> that is easier to parallelize (and faster) but is worse if multiple processors
> aren't available.  Mercury can introduce accumulators when the programmer hasn't
> specified them himself.  There is no facility for removing them for parallel
> execution.

That's a good example where this "programming by optimization" might be helpful.

Do you think it would be feasible for the programmer to provide
multiple sort implementations in Mercury and have the compiler choose
among them?

--
Michael

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