[mercury-users] Mercury programming by optimization

[Paul Bone]

On Mon, Mar 05, 2012 at 08:36:37AM -0700, Michael Hendricks wrote:
> I just finished reading "Programming by Optimization" by Holger Hoos
> in the February 2012 edition of Communications of the ACM.  Is
> something like this feasible/sensible for Mercury?  It reminds me of
> Paul Bone's recent work on automatic parallelization.  It also seems
> similar to Mercury's ability to compile different procedures for each
> mode and to supply different clauses for different modes.
> 
> For those who haven't heard of the idea before, here's a rough idea
> couched in terms of Mercury.  A developer is allowed to specify
> multiple implementations for a single predicate (and/or mode).  Each
> implementation performs the same computation, but perhaps has
> different performance characteristics.  The compiler and optimization
> tools, based on profiling data, choose among these redundant
> implementations to make a highly optimized binary.  The author
> describes 2-500x speedups in their research benchmarks.  It allows the
> developer to solve a problem in multiple creative ways and have the
> compiler make the hard performance computations/decisions on his
> behalf.
> 
> Incidentally, the idea also allows a QuickCheck-like testing regime in
> which random input is fed to each of the redundant implementations
> with the results compared against each other.  Any deviation in the
> results suggests a bug in one of the implementations.

How are the different alternatives generated.  Does the compiler generate the
alternatives when applying an optimization as a specialization.  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.

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

I don't know if I've answered your questions or not.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/users/attachments/20120308/ffae69f8/attachment.sig>