[mercury-users] Mercury programming by optimization

[Peter Stuckey]

The key idea for programming with optimizaiton is that the author develops multiple implementaitons
for the same predicate and mode.  The compiler trys to work out the best combination of
implementations for particular test data.  So its not like Mercury compiler optimizations where
the compiler picks the most type/mode specific version of a predicate. 

In the PWO case there would be 5 implementations with identical type/mode.

With mercury you might be able to extend PWO by using different instances of a type class.

On 08/03/2012, at 12:14 PM, Paul Bone wrote:

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

Peter Stuckey
pjs at csse.unimelb.edu.au

-------------- next part --------------
A non-text attachment was scrubbed...
Name: email_logo.png
Type: image/png
Size: 9480 bytes
Desc: not available
URL: <http://lists.mercurylang.org/archives/users/attachments/20120308/5bf2f496/attachment.png>
-------------- next part --------------